堆栈

维基百科，自由的百科全书

(重定向自堆疊)

堆栈(stack)，又稱堆疊,在電腦科學中，是一種特殊的串列形式的資料結構，它的特殊之處在於只能允許在鏈結串列或陣列的一端（稱為堆疊頂端指標，英文為top）進行加入資料(push)和輸出資料(pop)的運算。另外堆疊也可以用一維陣列或鏈結串列的形式來完成。堆疊的另外一個相對的操作方式稱為佇列。

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

堆疊資料結構使用兩種基本操作：推入（push）和彈出（pop）：

推入（push）：將數據放入堆疊的頂端(陣列形式或串列形式)，堆疊頂端top指標加一。

彈出（pop）：將頂端數據資料輸出(回傳)，堆疊頂端資料減一。

[编辑] 陣列堆疊

#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));//宣告資料結構空間
  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

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