编辑“堆栈”

'''堆栈'''（英文：stack），也可直接称栈。在[[计算机科学]]中，是一种特殊的串行形式的[[数据结构]]，它的特殊之处在于只能允许在链结串行或阵列的一端（称为堆栈顶端指标，英文为top）进行加入资料（push）和输出资料（pop）的运算。另外堆栈也可以用一维阵列或连结串行的形式来完成。堆栈的另外一个相对的操作方式称为伫列。由于堆栈数据结构只允许在一端进行操作，因而按照后进先出（LIFO, Last In First Out）的原理运作。它是一种存储部件，即[[数据]]的写入跟读出不需要提供地址，而是根据写入的顺序决定读出的顺序。
堆栈数据结构使用两种基本操作：推入（push）和弹出（pop）
*推入（push）：将数据放入堆栈的顶端（阵列形式或串行形式），堆栈顶端top指标加一。 
*弹出（pop）：将顶端数据资料输出（回传），堆栈顶端资料减一。
==堆栈简介==
[[动态数据]]区一般就是“堆栈”。“栈(stack)”和“堆(heap)”是两种不同的动态数据区，栈是一种线性结构，堆是一种链式结构。进程的每个线程都有私有的“栈”，所以每个线程虽然[[代码]]一样，但本地变量的数据都是互不干扰。一个堆栈可以通过“基地址”和“栈顶”地址来描述。全局变量和静态变量分配在静态数据区，本地变量分配在动态数据区，即堆栈中。[[程序]]通过堆栈的基地址和偏移量来访问本地变量。
==堆栈原理==
堆栈是一种执行“后进先出”[[算法]]的[[数据结构]]。 
它是在内存中开辟一个存储区域，[[数据]]一个一个顺序地存入（也就是“ 推入——push”）这个区域之中。有一个地址指针总指向最后一个压入堆栈的数据所在的数据单元，存放这个地址指针的寄存器就叫做堆栈指示器。开始放入数据的单元叫做“栈底”。数据一个一个地存入，这个过程叫做“压栈”。在压栈的过程中，每有一个数据压入堆栈，就放在和前一个单元相连的后面一个单元中，堆栈指示器中的地址自动加1。读取这些数据时，按照堆栈指示器中的地址读取数据，堆栈指示器中的地址数自动减1。这个过程叫做“弹出pop”。
==堆栈分类==
*'''阵列堆栈'''
<pre>#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");    
 }</pre>
*'''串行堆栈'''
<pre>/*链栈的结构定义*/
 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
</pre>
==相关词条==
*[[数据]]
*[[数据结构]]
*[[内存]]
*[[程序]]
*[[算法]]
==参考来源==
*http://zh.wikipedia.org/wiki/%E5%A0%86%E6%A0%88#.E5.A0.86.E7.96.8A.E7.9A.84.E6.87.89.E7.94.A8
*http://blog.sina.com.cn/s/blog_4127ebcb0100096r.html
*http://baike.baidu.com/view/93201.htm
[[category:数据结构|D]]
[[category:计算机术语|D]]