1．棧

1.1?棧的定義

棧是一種特殊的線性表。其特殊性在于限定插入和刪除數據元素的操作只能在線性表的一端進行。如下所示：

結論：后進先出（Last In First Out），簡稱為LIFO線性表。

棧的基本運算有六種：

構造空棧：InitStack(S)、

判棧空: StackEmpty(S)、

判棧滿：?StackFull(S)、

進棧：?Push(S,x)、可形象地理解為壓入，這時棧中會多一個元素

退棧：?Pop(S) 、 可形象地理解為彈出，彈出后棧中就無此元素了。

取棧頂元素：StackTop(S),不同與彈出，只是使用棧頂元素的值，該元素仍在棧頂不會改變。

? ? 由于棧也是線性表，因此線性表的存儲結構對棧也適用，通常棧有順序棧和鏈棧兩種存儲結構，這兩種存儲結構的不同，則使得實現棧的基本運算的算法也有所不同。

我們要了解的是，在順序棧中有"上溢"和"下溢"的概念。順序棧好比一個盒子，我們在里頭放了一疊書，當我們要用書的話只能從第一本開始拿(你會把盒子翻過來嗎?真聰明^^)，那么當我們把書本放到這個棧中超過盒子的頂部時就放不下了(疊上去的不算，哼哼)，這時就是"上溢","上溢"也就是棧頂指針指出棧的外面，顯然是出錯了。反之，當棧中已沒有書時，我們再去拿，看看沒書，把盒子拎起來看看盒底，還是沒有，這就是"下溢"。"下溢"本身可以表示棧為空棧,因此可以用它來作為控制轉移的條件。

鏈棧則沒有上溢的限制，它就象是一條一頭固定的鏈子，可以在活動的一頭自由地增加鏈環(結點)而不會溢出，鏈棧不需要在頭部附加頭結點，因為棧都是在頭部進行操作的，如果加了頭結點，等于要在頭結點之后的結點進行操作，反而使算法更復雜，所以只要有鏈表的頭指針就可以了。

代碼：

// Test.cpp : Defines the entry point for the console application. // #include "stdafx.h" #include <iostream> using namespace std; #define MAX 10 // MAXIMUM STACK CONTENT class stack { private: int arr[MAX]; int top; public: stack() { inItStack(); }/************************************************************************//* 初始化棧 *//************************************************************************/void inItStack() { top=-1; } /************************************************************************//* 入棧 *//************************************************************************/void push(int a) { top++;if(top < MAX) { arr[top]=a; } else { cout<<"STACK FULL!!"<<top; } } /************************************************************************//* 出棧 *//************************************************************************/int pop(){ if(isEmpty()) { cout<<"STACK IS EMPTY ";return NULL; } else { int data=arr[top]; arr[top]=NULL; top--;return data; } } /************************************************************************//* 是否為空 *//************************************************************************/bool isEmpty(){if(top == -1) return true;else return false;} }; int main() { stack a; a.push(3); a.push(10); a.push(1); cout<<"Pop:"<<a.pop(); return 0; }
結論：由于棧的插入和刪除操作具有它的特殊性，所以用順序存儲結構表示的棧并不存在插入刪除數據元素時需要移動的問題，但棧容量難以擴充的弱點仍就沒有擺脫。

1.3 棧的鏈式存儲
若是棧中元素的數目變化范圍較大或不清楚棧元素的數目，就應該考慮使用鏈式存儲結構。人們將用鏈式存儲結構表示的棧稱作"鏈棧"。鏈棧通常用一個無頭結點的單鏈表表示。如圖所示：

棧的操作是線性表操作的特例。

簡單用c實現：

// Test.cpp : Defines the entry point for the console application. // #include "stdafx.h" #include <stdio.h> #include "stdlib.h" #include <iostream> using namespace std; //宏定義 #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2 #define STACKEMPTY -3 #define LT(a,b) ((a)<(b)) #define N = 100 typedef int Status; typedef int ElemType; typedef struct LNode{ ElemType data; struct LNode *next; }LNode, *LinkList; typedef struct stack{LinkList top; } STACK;/************************************************************************/ /* 接口： */ /************************************************************************/ void InitStack(STACK &S); void Push(STACK &S,ElemType e); void Pop(STACK &S, ElemType *e); ElemType GetTop(STACK S,ElemType *e); int StackEmpty(STACK S);/************************************************************************/ /* */ /************************************************************************/ void InitStack(STACK &S) {S.top=NULL; }/************************************************************************/ /* 入棧 */ /************************************************************************/ void Push(STACK &S,ElemType e) {LinkList p;p = (LinkList )malloc(sizeof(LNode));if (!p) exit(OVERFLOW);p->data = e;p->next = S.top;S.top = p; } /************************************************************************/ /* 出棧 */ /************************************************************************/ void Pop(STACK &S, ElemType *e) {LinkList p;if(StackEmpty(S)) exit(STACKEMPTY);*e = S.top->data;p = S.top;S.top = p->next; free(p); } /************************************************************************/ /* 獲取棧頂元素內容 */ /************************************************************************/ ElemType GetTop(STACK S, ElemType *e) {if(StackEmpty(S)) exit(STACKEMPTY);*e = S.top->data; }/************************************************************************/ /* 判斷棧S是否空 */ /************************************************************************/ int StackEmpty(STACK S) {if(S.top==NULL) return TRUE;return FALSE; }void main() { STACK S;InitStack( S);Push(S, 3);Push(S, 4);ElemType e;Pop(S,&e);cout<<"Pop elem:"<<e; }

1.4 棧的應用

1) ?數制轉換

2）語法詞法分析

3）表達式求值等

1.5 棧的遞歸和實現

漢諾塔的問題：

解決：

1）如果有一個盤子，直接從X移到Z即可。
2）如果有n個盤子要從X移到Z，Y作為輔助。問題可以轉化為，先將上面n-1個從X移動到Y，Z作為輔助，然后將第n個從X移動到Z，最后將剩余的n-1個從Y移動到Z，X作為輔助。

完整實現代碼，包括棧的實現：

/ Test.cpp : Defines the entry point for the console application. // #include "stdafx.h" #include <stdio.h> #include "stdlib.h" #include <iostream> using namespace std; //宏定義 #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2 #define STACKEMPTY -3 #define LT(a,b) ((a)<(b)) #define N = 100 typedef int Status; typedef int ElemType; typedef struct LNode{ ElemType data; struct LNode *next; }LNode, *LinkList; typedef struct stack{LinkList top; } STACK;/************************************************************************/ /* 接口： */ /************************************************************************/ void InitStack(STACK &S); void Push(STACK &S,ElemType e); void Pop(STACK &S, ElemType *e); ElemType GetTop(STACK S,ElemType *e); int StackEmpty(STACK S);/************************************************************************/ /* */ /************************************************************************/ void InitStack(STACK &S) {S.top=NULL; }/************************************************************************/ /* 入棧 */ /************************************************************************/ void Push(STACK &S,ElemType e) {LinkList p;p = (LinkList )malloc(sizeof(LNode));if (!p) exit(OVERFLOW);p->data = e;p->next = S.top;S.top = p; } /************************************************************************/ /* 出棧 */ /************************************************************************/ void Pop(STACK &S, ElemType *e) {LinkList p;if(StackEmpty(S)) exit(STACKEMPTY);*e = S.top->data;p = S.top;S.top = p->next; free(p); } /************************************************************************/ /* 獲取棧頂元素內容 */ /************************************************************************/ ElemType GetTop(STACK S, ElemType *e) {if(StackEmpty(S)) exit(STACKEMPTY);*e = S.top->data; } void printStack(STACK S){LinkList p;p = S.top;printf("棧： ");while (p) {printf("%d ", p->data);p = p->next;} } /************************************************************************/ /* 如果有一個盤子，直接從X移到Z即可。 如果有n個盤子要從X移到Z，Y作為輔助。問題可以轉化為，先將上面n-1個從X移動到Y，Z作為輔助，然后將第n個從X移動到Z，最后將剩余的n-1個從Y移動到Z，X作為輔助。 */ /************************************************************************/void move(STACK &Sa,STACK &Sb) { ElemType e;Pop(Sa,&e);Push(Sb, e); } void hanoi(int n,STACK &X,STACK &Y,STACK &Z) {if(n==1) return move(X, Z); //將圓盤1號直接移到zhanoi(n-1,X,Z,Y); //將x上的1大n-1圓盤移到y，z做輔助塔move(X, Z); //將編號為n的圓盤移zhanoi(n-1,Y,X,Z); //將y上的1大n-1圓盤移到z，x做輔助塔 }/************************************************************************/ /* 判斷棧S是否空 */ /************************************************************************/ int StackEmpty(STACK S) {if(S.top==NULL) return TRUE;return FALSE; }void main() { STACK Sx, Sy,Sz;InitStack( Sx);InitStack( Sy);InitStack( Sz);int i, n = 10;for (i = 10 ; i>=1 ;i--) {Push(Sx, i);}printStack(Sx);hanoi(n, Sx,Sy,Sz);printStack(Sz); }

總結

以上是生活随笔為你收集整理的数据结构-----栈的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。