堆栈

维基百科,自由的百科全书
跳转至: 导航搜索
堆栈的简单示意图

堆栈英语stack),也可直接称中国大陆作堆栈,台湾作堆叠,在计算机科學中,是一種特殊的串列形式的資料結構,它的特殊之處在於只能允許在鏈結串列或陣列的一端(稱為堆疊頂端指標,英语top)進行加入資料(英语push)和輸出資料(英语pop)的運算。另外堆疊也可以用一維陣列連結串列的形式來完成。堆疊的另外一個相對的操作方式稱為佇列

由於堆疊資料結構只允許在一端進行操作,因而按照後進先出(LIFO, Last In First Out)的原理運作。

堆疊資料結構使用兩種基本操作:推入(push)和彈出(pop):

  • 推入:將數據放入堆疊的頂端(陣列形式或串列形式),堆疊頂端top指標加一。
  • 彈出:將頂端數據資料輸出(回傳),堆疊頂端資料減一。

抽象定义[编辑]

以下是堆栈的VDM(Vienna Development Method英语Vienna Development Method):[1]

函数签名:

  init: -> Stack
  push: N x Stack -> Stack
  top: Stack -> (N U ERROR)
  pop: Stack -> Stack
  isempty: Stack -> Boolean

此处的N代表某个元素(如自然数),而U表示集合求交。

语义:

  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结构下含一个数组。如果空间实在紧张,也可用链表实现,且去掉表头。这里的例程是以数组实现的。

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define stack struct Stack
#define STACK_POP_ERR 42
/* 堆疊資料結構 堆栈数据结构 */
struct Stack
{
  int val[10]; // 陣列空間
  int top;     // 堆疊頂端指標(栈顶)
};
/* 檢查堆疊是否為空 */
bool empty(stack *stk) { return stk->top == 0; }
/* 推入資料 */
void push(stack *stk, int x)
{
  stk->top=stk->top+1;
  stk->val[stk->top]=x;
}
/* 彈出并返回資料 */
int pop(stack *stk) 
{
  if(empty(stk)) 
    return STACK_POP_ERR; // 不能彈出
  else
  {
    stk->top=stk->top-1;
    return stk->val[stk->top+1];
  }
}
int main()
{
  // 宣告并初始化資料結構空間
  stack stk;
  stk.top=0;
  // 推入四个
  push(&stk, 3);
  push(&stk, 4);
  push(&stk, 1);
  push(&stk, 9);
  // 弹出三个
  printf("%d ", pop(&stk));
  printf("%d ", pop(&stk));
  printf("%d ", pop(&stk));
  return 0;
}

串列堆疊[编辑]

/*链栈的结构定义*/
typedef struct {
  SLink top;    // 棧頂指針
  int len​​gth;   // 棧中元素個數
} Stack;

// 构造空栈 S
void InitStack (Stack &S)
{
  S.top = NULL;   // 設棧頂指針的初值為"空"
  S.length = 0;   // 空棧中元素個數為0
}
// 如果指针反过来从栈底到栈顶的话,删除栈顶元素时,为修改其前驱指针,需要从栈底一直找到栈顶。

// 在棧頂S 之上插入元素e為新的棧頂元素,並返回成功與否
bool Push (Stack &S, ElemType e) {
 p = new LNode;   // 建新的結點
 if(!p)
   return false;  // 存儲分配失敗
 p -> data = e;
 p -> next = S.top;// 鏈接到原來的棧頂
 S.top = p;     // 移動棧頂指針
 ++S.length;     // 棧的長度增1
}
// 在链栈的类型定义中设立“栈中元素个数”的成员是为了便于求得栈的长度。

// 刪除S 棧頂且以e 返回其數值,返回成功與否
bool Pop (Stack &S, SElemType &e)
{
  if (!S.top)
    return false;
  else
  {
     e = S.top -> data;    // 返回棧頂元素
     q = S.top;
     S.top = S.top -> next; // 修改棧頂指針
     --S.length;       // 棧的長度減1
     delete q;       // 釋放被刪除的結點空間
     return true;
   }
}

堆棧有時候也常用來指代堆棧段

硬件堆栈[编辑]

架构层次上的堆栈通常被用以申请和访问内存。

硬件支持[编辑]

大多数CPU都有用作堆栈指针的寄存器。

堆疊的應用[编辑]

参见[编辑]

脚注[编辑]

  1. ^ Jones: "Systematic Software Development Using VDM"