堆栈

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

堆栈英语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>
 /*堆疊資料結構*/
 struct Stack
 {
   int Array[10];//陣列空間
   int Top;//堆疊頂端指標       
 };
 /*檢查堆疊是否為空*/
 bool stack_empty(Stack *Stack1)
 {
   if(Stack1->Top==0)
   {
     return true;            
   }     
   else
   {
     return false;    
   }
 }
 /*推入資料*/
 void push(Stack *Stack1,int x)
 {
   Stack1->Top=Stack1->Top+1;
   Stack1->Array[Stack1->Top]=x;         
 }
 /*彈出資料*/
 int pop(Stack *Stack1)
 {
   if(stack_empty(Stack1))
   {
     printf("underflow");
   }
   else
   {
     Stack1->Top=Stack1->Top-1;
     return Stack1->Array[Stack1->Top+1];    
   }
 
 }
 int main()
 {
   struct Stack *Stack1=(struct Stack *)malloc(sizeof(struct Stack));//宣告資料結構空間
   Stack1->Top=0;//初始化
   push(Stack1,3);//推入3
   push(Stack1,4);//推入4
   push(Stack1,1);//推入1
   push(Stack1,10);//推入10
   printf("%d ",pop(Stack1));//彈出10
   printf("%d ",pop(Stack1));//彈出1
   printf("%d ",pop(Stack1));//彈出4
   system("pause");    
 }

串列堆疊[编辑]

 /*链栈的结构定义*/
 typedef struct { 
   SLink top;    // 栈顶指针 
   int length;   // 栈中元素个数
 }Stack;
 
 void InitStack ( Stack &S )
 { 
   // 构造一个空栈S
   S.top = NULL;   // 设栈顶指针的初值为"空" 
   S.length = 0;   // 空栈中元素个数为0
 } // InitStack
 /*能否将链栈中的指针方向反过来,从栈底到栈顶?  
  不行,如果反过来的话,删除栈顶元素时,为修改其前驱指针,需要从栈底一直找到栈顶。*/ 
 
 
 void Push ( Stack &S, ElemType e )
 {
   // 在栈顶之上插入元素e为新的栈顶元素
   p = new LNode;   // 建新的结点
   if(!p) exit(1);  // 存储分配失败
   p -> data = e;
   p -> next = S.top; // 链接到原来的栈顶
   S.top = p;     // 移动栈顶指针
   ++S.length;     // 栈的长度增1
 } // Push
 /*在链栈的类型定义中设立"栈中元素个数"的成员是为了便于求得栈的长度。*/
 
 bool Pop ( Stack &S, SElemType &e )
 { 
   // 若栈不空,则删除S的栈顶元素,用e返回其值,
   // 并返回TRUE;否则返回FALSE
   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;
     }
 } // Pop

堆栈有时候也常用来指代堆栈段

硬件堆栈[编辑]

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

硬件支持[编辑]

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

堆疊的應用[编辑]

参见[编辑]

脚注[编辑]

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