数据结构--堆栈-布布扣-bubuko.com

堆栈（英语：stack），也可直接称栈。台湾作堆叠，在计算机科学中，是一种特殊的串行形式的数据结构，它的特殊之处在于只能允许在链结串行或阵列的一端（称为堆栈顶端指标，英语：top）进行加入资料（英语：push）和输出资料（英语：pop）的运算。另外堆栈也可以用一维阵列或连结串行的形式来完成。堆栈的另外一个相对的操作方式称为伫列。

由于堆栈数据结构只允许在一端进行操作，因而按照后进先出（LIFO, Last In First Out）的原理运作。

堆栈数据结构使用两种基本操作：推入（push）和弹出（pop）：

抽象定义

软件堆栈

阵列堆栈

堆栈可以用链表和数组两种方式实现，一般为一个堆栈预先分配一个大小固定且较合适的空间并非难事，所以较流行的做法是 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

数据结构--堆栈

堆栈

抽象定义

软件堆栈

阵列堆栈

串行堆栈[编辑]

硬件堆栈

硬件支持