線性結(jié)構(gòu)的兩種常見應(yīng)用之一棧
定義：一種可以實(shí)現(xiàn)”先進(jìn)后出”的存儲(chǔ)結(jié)構(gòu)，棧類似于箱子
分類：靜態(tài)棧、動(dòng)態(tài)棧
算法：出棧、壓棧

?

棧的定義：

棧（stack）又名堆棧，它是一種運(yùn)算受限的線性表。限定僅在表尾進(jìn)行插入和刪除操作的線性表。這一端被稱為棧頂，相對(duì)地，把另一端稱為棧底。向一個(gè)棧插入新元素又稱作進(jìn)棧、入棧或壓棧，它是把新元素放到棧頂元素的上面，使之成為新的棧頂元素；從一個(gè)棧刪除元素又稱作出棧或退棧，它是把棧頂元素刪除掉，使其相鄰的元素成為新的棧頂元素。

棧的邏輯定義、特點(diǎn)及運(yùn)算：

棧是限定在表的一端進(jìn)行插入和刪除的運(yùn)算的線性表，通常將插入、刪除的一端稱為棧頂，另一端稱為棧底。不含元素的空表稱為空棧。棧的操作具有先進(jìn)后出或后進(jìn)先出的特點(diǎn)。棧的運(yùn)算主要有置空棧、判棧空、判棧滿、進(jìn)棧、退棧、和取棧頂元素6種。

基本概念

要搞清楚這個(gè)概念，首先要明白”棧“原來的意思，如此才能把握本質(zhì)。"棧“者,存儲(chǔ)貨物或供旅客住宿的地方,可引申為倉庫、中轉(zhuǎn)站，所以引入到計(jì)算機(jī)領(lǐng)域里，就是指數(shù)據(jù)暫時(shí)存儲(chǔ)的地方，所以才有進(jìn)棧、出棧的說法。

首先系統(tǒng)或者數(shù)據(jù)結(jié)構(gòu)棧中數(shù)據(jù)內(nèi)容的讀取與插入（壓入push和 彈出pop）是兩回事！壓入是增加數(shù)據(jù)，彈出是刪除數(shù)據(jù) ，這些操作只能從棧頂即最低地址作為約束的接口界面入手操作 ，但讀取棧中的數(shù)據(jù)是隨便的沒有接口約束之說。很多人都誤解這個(gè)理念從而對(duì)棧產(chǎn)生困惑。而系統(tǒng)棧在計(jì)算機(jī)體系結(jié)構(gòu)中又起到一個(gè)跨部件交互的媒介區(qū)域的作用 即 cpu 與內(nèi)存的交流通道 ，cpu只從系統(tǒng)給我們自己編寫的應(yīng)用程序所規(guī)定的棧入口線性地讀取執(zhí)行指令， 用一個(gè)形象的詞來形容它就是pipeline（管道線、流水線）。cpu內(nèi)部交互具體參見 EU與BIU的概念介紹。

棧作為一種數(shù)據(jù)結(jié)構(gòu)，是一種只能在一端進(jìn)行插入和刪除操作的特殊線性表。它按照先進(jìn)后出的原則存儲(chǔ)數(shù)據(jù)，先進(jìn)入的數(shù)據(jù)被壓入棧底，最后的數(shù)據(jù)在棧頂，需要讀數(shù)據(jù)的時(shí)候從棧頂開始彈出數(shù)據(jù)（最后一個(gè)數(shù)據(jù)被第一個(gè)讀出來）。棧具有記憶作用，對(duì)棧的插入與刪除操作中，不需要改變棧底指針。

棧是允許在同一端進(jìn)行插入和刪除操作的特殊線性表。允許進(jìn)行插入和刪除操作的一端稱為棧頂(top)，另一端為棧底(bottom)；棧底固定，而棧頂浮動(dòng)；棧中元素個(gè)數(shù)為零時(shí)稱為空棧。插入一般稱為進(jìn)棧（PUSH），刪除則稱為退棧（POP）。棧也稱為先進(jìn)后出表。

棧可以用來在函數(shù)調(diào)用的時(shí)候存儲(chǔ)斷點(diǎn)，做遞歸時(shí)要用到棧！

以上定義是在經(jīng)典計(jì)算機(jī)科學(xué)中的解釋。

在計(jì)算機(jī)系統(tǒng)中，棧則是一個(gè)具有以上屬性的動(dòng)態(tài)內(nèi)存區(qū)域。程序可以將數(shù)據(jù)壓入棧中，也可以將數(shù)據(jù)從棧頂彈出。在i386機(jī)器中，棧頂由稱為esp的寄存器進(jìn)行定位。壓棧的操作使得棧頂?shù)牡刂窚p小，彈出的操作使得棧頂?shù)牡刂吩龃蟆?/p>

棧在程序的運(yùn)行中有著舉足輕重的作用。最重要的是棧保存了一個(gè)函數(shù)調(diào)用時(shí)所需要的維護(hù)信息，這常常稱之為堆棧幀或者活動(dòng)記錄。堆棧幀一般包含如下幾方面的信息：

1．函數(shù)的返回地址和參數(shù)

2． 臨時(shí)變量：包括函數(shù)的非靜態(tài)局部變量以及編譯器自動(dòng)生成的其他臨時(shí)變量。

基本算法

1．進(jìn)棧（PUSH）算法

①若TOP≥n時(shí)，則給出溢出信息，作出錯(cuò)處理（進(jìn)棧前首先檢查棧是否已滿，滿則溢出；不滿則作②）；

②置TOP=TOP+1（棧指針加1，指向進(jìn)棧地址）；

③S(TOP)=X，結(jié)束（X為新進(jìn)棧的元素）；

2．退棧（POP）算法

①若TOP≤0，則給出下溢信息，作出錯(cuò)處理(退棧前先檢查是否已為空棧， 空則下溢；不空則作②)；

②X=S(TOP)，（退棧后的元素賦給X）：

③TOP=TOP-1，結(jié)束（棧指針減1，指向棧頂）。

?

棧分順序棧和鏈?zhǔn)綏?#xff0c;下面程序介紹了順序棧的實(shí)現(xiàn)。

pascal

1．數(shù)組型

Const

m=棧表目數(shù)的上限；

Type

stack=array[1..m] of stype; {棧類型}

Var

s:stack;{棧}

top:integer;

2．記錄型

const

m=棧表目數(shù)的上限；

type

stack=record

elem: array[1..m] of elemtp;

top:0..m; {棧頂指針}

end;

Var

s:stack;{棧}

C++代碼

#include <iostream> #include <stdio.h> #include <malloc.h>class SqStack{private: enum { MaxSize = 100 };int data[MaxSize];int top;public:SqStack();~SqStack();bool isEmpty();void pushInt(int x);int popInt();int getTop();void display();};SqStack::SqStack(){top = -1;}SqStack::~SqStack() {}bool SqStack::isEmpty(){ //判斷棧為空return(top == -1);}void SqStack::pushInt(int x){ //元素進(jìn)棧if (top == MaxSize - 1){std::cout << "棧上溢出！" << std::endl;}else{++top;data[top] = x;} }int SqStack::popInt(){ //退棧int tmp = 0;if (top == -1){std::cout << "棧已空！" << std::endl;}else{tmp = data[top--];}return tmp; }int SqStack::getTop(){ //獲得棧頂元素int tmp = 0;if (top == -1){std::cout << "棧空！" << std::endl;}else{tmp = data[top];}return tmp;}void SqStack::display(){ //打印棧里元素std::cout << "棧中元素：" << std::endl;for (int index = top; index >= 0; --index){std::cout << data[index] << std::endl;}}int main(){SqStack st;std::cout << "棧空：" << st.isEmpty() << std::endl;for (int i = 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();return 0;}

?

C代碼

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102

#include?<stdio.h> #include?<malloc.h> ? #define?DataType?int #define?MAXSIZE?1024 ? typedef?struct{ ????DataType?data[MAXSIZE]; ????int?top; }SeqStack; ? SeqStack*?Init_SeqStack(){??//棧初始化 ????SeqStack*?s; ????s?=?(SeqStack*)malloc(sizeof(SeqStack)); ????if(!s){ ????????printf("空間不足\n"); ????????return?NULL; ????}else{ ????????s->top?=?-1; ????????return?s; ????} } ? int?Empty_SeqStack(SeqStack*?s){??//判棧空 ????if(s->top?==?-1) ????????return?1; ????else ????????return?0; } ? int?Push_SeqStack(SeqStack*?s,?DataType?x){??//入棧 ????if(s->top?==?MAXSIZE?-?1) ????????return?0;//棧滿不能入棧 ????else{ ????????s->top++; ????????s->data[s->top]?=?x; ????????return?1; ????} } ? int?Pop_SeqStack(SeqStack*?s,?DataType*?x){??//出棧 ????if(Empty_SeqStack(s)) ????????return?0;//棧空不能出棧 ????else{ ????????*x?=?s->data[s->top]; ????????s->top--; ????????return?1; ????}//棧頂元素存入*x，返回 } ? DataType?Top_SeqStack(SeqStack*?s){??//取棧頂元素 ????if(Empty_SeqStack(s)) ????????return?0;//棧空 ????else ????????return?s->data[s->top]; } ? int?Print_SeqStack(SeqStack*?s){ ????int?i; ????printf("當(dāng)前棧中的元素:\n"); ????for(i?=?s->top;?i?>=?0;?i--) ????????printf("%3d",?s->data[i]); ????printf("\n"); ????return?0; } ? int?main(){ ????SeqStack*?L; ????int?n,?num,?m; ????int?i; ????? ????L?=?Init_SeqStack(); ????? ????printf("初始化完成\n"); ????printf("棧空：%d\n",?Empty_SeqStack(L)); ????printf("請(qǐng)輸入入棧元素個(gè)數(shù)：\n"); ????scanf("%d",?&n); ????printf("請(qǐng)輸入要入棧的%d個(gè)元素：\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("請(qǐng)輸入要出棧的元素個(gè)數(shù)（不能超過%d個(gè)）：\n",?n); ????scanf("%d",?&n); ????printf("依次出棧的%d個(gè)元素：\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)); ????? ????return?0; }

定義stack的簡(jiǎn)單代碼：

stack<int> sta;

入棧：sta.push(x);

出棧：sta.pop();

判斷棧的大小： sta.size();

判斷棧是否為空：sta.empty();

?

?左棧有堆（靜態(tài)分配的是在棧里，動(dòng)態(tài)分配的是在堆里）

#include <stdio.h> #include <malloc.h> void f(int k) {int m;double * q = (double *)malloc(200); } int main(void) {int i = 10;int * p= (int *)malloc(100);return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的栈入门的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。