堆棧：修訂間差異

堆棧（英文：stack），也可直接稱棧。在計算機科學(xué)中，是一種特殊的串行形式的數(shù)據(jù)結(jié)構(gòu)，它的特殊之處在于只能允許在鏈結(jié)串行或陣列的一端（稱為堆棧頂端指標(biāo)，英文為top）進(jìn)行加入資料（push）和輸出資料（pop）的運算。另外堆棧也可以用一維陣列或連結(jié)串行的形式來完成。堆棧的另外一個相對的操作方式稱為佇列。由于堆棧數(shù)據(jù)結(jié)構(gòu)只允許在一端進(jìn)行操作，因而按照后進(jìn)先出（LIFO, Last In First Out）的原理運作。它是一種存儲部件，即數(shù)據(jù)的寫入跟讀出不需要提供地址，而是根據(jù)寫入的順序決定讀出的順序。 堆棧數(shù)據(jù)結(jié)構(gòu)使用兩種基本操作：推入（push）和彈出（pop）

• 推入（push）：將數(shù)據(jù)放入堆棧的頂端（陣列形式或串行形式），堆棧頂端top指標(biāo)加一。
• 彈出（pop）：將頂端數(shù)據(jù)資料輸出（回傳），堆棧頂端資料減一。

目錄

• 1 堆棧簡介
• 2 堆棧原理
• 3 堆棧分類
• 4 相關(guān)詞條
• 5 參考來源

堆棧簡介

動態(tài)數(shù)據(jù)區(qū)一般就是“堆?！??！皸?stack)”和“堆(heap)”是兩種不同的動態(tài)數(shù)據(jù)區(qū)，棧是一種線性結(jié)構(gòu)，堆是一種鏈?zhǔn)浇Y(jié)構(gòu)。進(jìn)程的每個線程都有私有的“棧”，所以每個線程雖然代碼一樣，但本地變量的數(shù)據(jù)都是互不干擾。一個堆棧可以通過“基地址”和“棧頂”地址來描述。全局變量和靜態(tài)變量分配在靜態(tài)數(shù)據(jù)區(qū)，本地變量分配在動態(tài)數(shù)據(jù)區(qū)，即堆棧中。程序通過堆棧的基地址和偏移量來訪問本地變量。

堆棧原理

堆棧是一種執(zhí)行“后進(jìn)先出”算法的數(shù)據(jù)結(jié)構(gòu)。 它是在內(nèi)存中開辟一個存儲區(qū)域，數(shù)據(jù)一個一個順序地存入（也就是“ 推入——push”）這個區(qū)域之中。有一個地址指針總指向最后一個壓入堆棧的數(shù)據(jù)所在的數(shù)據(jù)單元，存放這個地址指針的寄存器就叫做堆棧指示器。開始放入數(shù)據(jù)的單元叫做“棧底”。數(shù)據(jù)一個一個地存入，這個過程叫做“壓?！?。在壓棧的過程中，每有一個數(shù)據(jù)壓入堆棧，就放在和前一個單元相連的后面一個單元中，堆棧指示器中的地址自動加1。讀取這些數(shù)據(jù)時，按照堆棧指示器中的地址讀取數(shù)據(jù)，堆棧指示器中的地址數(shù)自動減1。這個過程叫做“彈出pop”。

堆棧分類

• 陣列堆棧

#include <stdio.h>
 #include <stdlib.h>
 /*堆疊資料結(jié)構(gòu)*/
 struct Stack
 {
   int Array[10];//陣列空間
   int Top;//堆疊頂端指標(biāo)       
 };
 /*檢查堆疊是否為空*/
 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));//宣告資料結(jié)構(gòu)空間
   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");    
 }

• 串行堆棧

/*鏈棧的結(jié)構(gòu)定義*/
 typedef struct { 
   SLink top; 　 　// 棧頂指針 
   int length; 　 // 棧中元素個數(shù)
 }Stack;
 
 void InitStack ( Stack &S )
 { 
   // 構(gòu)造一個空棧 S
   S.top = NULL; 　　// 設(shè)棧頂指針的初值為"空" 
   S.length = 0; 　　// 空棧中元素個數(shù)為0
 } // InitStack
 /*能否將鏈棧中的指針方向反過來，不行，如果反過來的話，刪除棧頂元素時，為修改其前驅(qū)指針，需要從棧底一直找到棧頂。*/ 
 
 
 void Push ( Stack &S, ElemType e )
 {
   // 在棧頂之上插入元素 e 為新的棧頂元素
   p = new LNode; 　　// 建新的結(jié)點
   if(!p) exit(1);　　// 存儲分配失敗
   p -> data = e;
   p -> next = S.top;　// 鏈接到原來的棧頂
   S.top = p; 　　　　// 移動棧頂指針
   ++S.length;　　　　 // 棧的長度增1
 } // Push
 /*在鏈棧的類型定義中設(shè)立"棧中元素個數(shù)"的成員是為了便于求得棧的長度。*/
 
 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;　　　　　 　// 釋放被刪除的結(jié)點空間
       return TRUE;
     }
 } // Pop

相關(guān)詞條

• 數(shù)據(jù)
• 數(shù)據(jù)結(jié)構(gòu)
• 內(nèi)存
• 程序
• 算法

參考來源

• 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