棧（stack）又名堆疊，它是一種運算受限的線性表。其限制是僅允許在表的一端進行插入和刪除運算。這一端被稱為棧頂，相對地，把另一端稱為棧底。向一個棧插入新元素又稱作進棧、入棧或壓棧，它是把新元素放到棧頂元素的上面，使之成為新的棧頂元素；從一個棧刪除元素又稱作出棧或退棧，它是把棧頂元素刪除掉，使其相鄰的元素成為新的棧頂元素。
基本介紹
基本概念,基本算法,實現,pascal,C++代碼,C代碼,
基本概念
定義：棧是限定僅在表頭進行插入和刪除操作的線性表。要搞清楚這個概念，首先要明白”棧“原來的意思，如此才能把握本質。"棧“者,存儲貨物或供旅客住宿的地方,可引申為倉庫、中轉站，所以引入到計算機領域裡，就是指數據暫時存儲的地方，所以才有進棧、出棧的說法。
首先系統或者數據結構棧中數據內容的讀取與插入（壓入push和 彈出pop）是兩回事！插入是增加數據，彈出是刪除數據 ，這些操作只能從棧頂即最低地址作為約束的接口界面入手操作 ，但讀取棧中的數據是隨便的沒有接口約束之說。很多人都誤解這個理念從而對棧產生困惑。而系統棧在計算機體系結構中又起到一個跨部件互動的媒介區域的作用 即 cpu 與記憶體的交流通道 ，cpu只從系統給我們自己編寫的應用程式所規定的棧入口線性地讀取執行指令， 用一個形象的詞來形容它就是pipeline（管道線、流水線）。cpu內部互動具體參見 EU與BIU的概念介紹。
棧作為一種數據結構，是一種只能在一端進行插入和刪除操作的特殊線性表。它按照先進後出的原則存儲數據，先進入的數據被壓入棧底，最後的數據在棧頂，需要讀數據的時候從棧頂開始彈出數據（最後一個數據被第一個讀出來）。棧具有記憶作用，對棧的插入與刪除操作中，不需要改變棧底指針。
棧是允許在同一端進行插入和刪除操作的特殊線性表。允許進行插入和刪除操作的一端稱為棧頂(top)，另一端為棧底(bottom)；棧底固定，而棧頂浮動；棧中元素個數為零時稱為空棧。插入一般稱為進棧（PUSH），刪除則稱為退棧（POP）。棧也稱為後進先出表。
以上定義是在經典計算機科學中的解釋。
在計算機系統中，棧則是一個具有以上屬性的動態記憶體區域。程式可以將數據壓入棧中，也可以將數據從棧頂彈出。在i386機器中，棧頂由稱為esp的暫存器進行定位。壓棧的操作使得棧頂的地址減小，彈出的操作使得棧頂的地址增大。
1．函式的返回地址和參數
棧的模型基本算法
1．進棧（PUSH）算法
①若TOP≥n時，則給出溢出信息，作出錯處理（進棧前首先檢查棧是否已滿，滿則溢出；不滿則作②）；
③S(TOP)=X，結束（X為新進棧的元素）；
2．退棧（POP）算法
①若TOP≤0，則給出下溢信息，作出錯處理(退棧前先檢查是否已為空棧， 空則下溢；不空則作②)；
②X=S(TOP)，（退棧後的元素賦給X）：
③TOP=TOP-1，結束（棧指針減1，指向棧頂）。
實現
棧分順序棧和鏈式棧，下面程式介紹了順序棧的實現。
pascal
1．數組型
Const
m=棧表目數的上限；
Type
stack=array[1..m] of stype; {棧類型}
Var
s:stack;{棧}
top:integer;
2．記錄型
const
m=棧表目數的上限；
type
stack=record
elem: array[1..m] of elemtp;
top:0..m; {棧頂指針}
end;
Var
s:stack;{棧}
C++代碼
#include<iostream>classSqStack{private:enum{MaxSize=100};intdata[MaxSize];inttop;public:SqStack();~SqStack();boolisEmpty();voidpushInt(intx);intpopInt();intgetTop();voiddisplay();};SqStack::SqStack(){top=-1;}SqStack::~SqStack(){}boolSqStack::isEmpty()//判斷棧為空{return(top==-1);}voidSqStack::pushInt(intx)//元素進棧{if(top==MaxSize-1){std::cout<<"棧上溢出！"<<std::endl;}else{++top;data[top]=x;}}intSqStack::popInt()//退棧{inttmp=0;if(top==-1){std::cout<<"棧已空！"<<std::endl;}else{tmp=data[top--];}returntmp;}intSqStack::getTop()//獲得棧頂元素{inttmp=0;if(top==-1){std::cout<<"棧空！"<<std::endl;}else{tmp=data[top];}returntmp;}voidSqStack::display()//列印棧里元素{std::cout<<"棧中元素："<<std::endl;for(intindex=top;index>=0;--index){std::cout<<data[index]<<std::endl;}}intmain(){SqStackst;std::cout<<"棧空："<<st.isEmpty()<<std::endl;for(inti=1;i<10;i++){st.pushInt(i);}st.display();std::cout<<"退一次棧"<<std::endl;st.popInt();std::cout<<"棧頂元素:"<<st.getTop()<<std::endl;st.popInt();st.display();return0;}C代碼
#include<stdio.h>#include<malloc.h>#defineDataTypeint#defineMAXSIZE1024typedefstruct{DataTypedata[MAXSIZE];inttop;}SeqStack;SeqStack*Init_SeqStack()//棧初始化{SeqStack*s;s=(SeqStack*)malloc(sizeof(SeqStack));if(!s){printf("空間不足\n");returnNULL;}else{s->top=-1;returns;}}intEmpty_SeqStack(SeqStack*s)//判棧空{if(s->top==-1)return1;elsereturn0;}intPush_SeqStack(SeqStack*s,DataTypex)//入棧{if(s->top==MAXSIZE-1)return0;//棧滿不能入棧else{s->top++;s->data[s->top]=x;return1;}}intPop_SeqStack(SeqStack*s,DataType*x)//出棧{if(Empty_SeqStack(s))return0;//棧空不能出棧else{*x=s->data[s->top];s->top--;return1;}//棧頂元素存入*x，返回}DataTypeTop_SeqStack(SeqStack*s)//取棧頂元素{if(Empty_SeqStack(s))return0;//棧空elsereturns->data[s->top];}intPrint_SeqStack(SeqStack*s){inti;printf("當前棧中的元素:\n");for(i=s->top;i>=0;i--)printf("%3d",s->data[i]);printf("\n");return0;}intmain(){SeqStack*L;intn,num,m;inti;L=Init_SeqStack();printf("初始化完成\n");printf("棧空：%d\n",Empty_SeqStack(L));printf("請輸入入棧元素個數：\n");scanf("%d",&n);printf("請輸入要入棧的%d個元素：\n",n);for(i=0;i<n;i++){scanf("%d",&num);Push_SeqStack(L,num);}Print_SeqStack(L);printf("棧頂元素：%d\n",Top_SeqStack(L));printf("請輸入要出棧的元素個數（不能超過%d個）：\n",n);scanf("%d",&n);printf("依次出棧的%d個元素：\n",n);for(i=0;i<n;i++){Pop_SeqStack(L,&m);printf("%3d",m);}printf("\n");Print_SeqStack(L);printf("棧頂元素：%d\n",Top_SeqStack(L));return0;}定義stack的簡單代碼：
stack<int> sta;
入棧：sta.push(x);
出棧：sta.pop();
判斷棧的大小： sta.size();
判斷棧是否為空：sta.empty();
