疊

疊（stack）閣叫做棧抑是堆棧，是電腦科學中的一種抽象資料型別，只允准佇有序的線性資料集合的一端（講號做堆疊頂頭，top）加入資料（push）佮徙掉資料（pop）的運算。因為按照以後會先出（LIFO , Last In First Out）彼號原理的運作，疊捷用一維陣列抑是相連結鬥起來實現。定佮另外一種長輩的線性的資料集合佇咧列相提並且論。

操作

疊使用兩種基本操作：推入（硩棧，push）佮彈出（彈棧，pop）：

• 推入：共資料囥入去疊頂懸，疊頂懸徙到新囥入來的資料。
• 彈出：會疊頂懸的資料來徙掉，疊頂懸徙到徙掉的後一筆資料。

特點

疊起來的基本特點：

一 . 先入後出，後入先出。 二 . 除頭尾節點以外，逐个元素有一个前驅，一个後繼。

抽象定義

以下是疊的 VDM（_ Vienna Development Method _）：

函式來簽章：

` ` ` init :-> Stack push : N x Stack-> Stack top : Stack-> ( N $ \ cup $ ERROR ) pop : Stack-> Stack isempty : Stack-> Boolean ` ` `

此處的 N 代表某一个元素（如自然數）， 而且 $ \ cup $ 表示集合求並。

語意：

` ` ` top ( init ( ) )=ERROR top ( push ( i , s ) )=i pop ( init ( ) )=init ( ) pop ( push ( i , s ) )=s isempty ( init ( ) )=true isempty ( push ( i , s ) )=false ` ` `

軟體疊

疊會當用陣列佮規堆囥起來兩種方式實現，一般為一个疊預先分配一个大細固定而且較合適合的空間並非難事，所以較流行的做法就是講 ` Stack ` 結構下含一个陣列。若空間實在緊張，嘛會當用連結串列實現，而且你若去踅頭。

遮的常式是以 C 語言實現的。

疊起來

連結串列基本操作

堆棧有時仔嘛定定用來指代堆棧段。

硬體疊

架構層次頂的疊通常被用申請佮存取記憶體。

硬體支援

大多數啦 CPU 攏有用疊指標的暫存器。

疊疊的應用

• 回溯
• 遞迴
• 深度優先搜揣

參見

• 連結串列
• 在列