2.1棧

棧是限定僅在表尾進(jìn)行插入或刪除操作的線性表，因此，對棧來說，表尾端有其特殊含義，稱為棧頂（top），相應(yīng)地，表頭稱為棧底。

E為棧底元素，A為棧頂元素。也就意味著，棧的修改是按后進(jìn)先出的原則進(jìn)行的。因此棧又稱為后進(jìn)先出線性表（簡稱LIFO結(jié)構(gòu)）。

2.1.1棧的表示和實(shí)現(xiàn)

和線性表類似，棧也有兩種存儲表示方式。
順序棧，即棧的順序存儲結(jié)構(gòu)是利用一組地址連續(xù)的存儲單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素，同時附設(shè)指針top指示棧頂元素在順序棧中的位置。通常的習(xí)慣做法是top=0表示空棧，鑒于C語言中數(shù)組的下標(biāo)約定從0開始，則當(dāng)以C作描述語言時，如設(shè)定會帶來很大不便；另一方面，由于棧在使用過程中所需最大空間的大小很難估計，一般來說，在初始化設(shè)空棧時不應(yīng)限定棧的最大容量。一個較合理的做法是；先分配一個基本容量，然后在應(yīng)用過程中，當(dāng)棧的空間不夠使用時再逐段擴(kuò)大。為此可設(shè)定兩個常量：STACK_INIT_SIZE（存儲空間初始分配量）和STACKINCREMENT（存儲空間分配增量）。

top 并不是棧頂元素，而是指向棧頂元素的下一個位置。
top - 1 才是真正的棧頂元素位置。

typedef struct{SElemType *base; //棧底指針SElemType *top;  //棧頂指針,其初值指向棧底int stacksize;   //棧當(dāng)前可使用的最大容量//每當(dāng)插入心得棧頂元素時,指針top+1
};

順序棧所有操作匯總：

#include<stdio.h>
#include<stdlib.h>#define SElemType  int
#define STACK_INIT_SIZE 100 //存儲空間初始分配量 
#define STACKINCREMENT 10   //存儲空間分配增量
#define Status inttypedef struct{SElemType *base;SElemType *top;int stacksize;
} SqStack; Status InitStack (SqStack &S){//構(gòu)造一個空棧S.base = (SElemType *) malloc(STACK_INIT_SIZE * sizeof(SElemType));if(!S.base) exit(0); //存儲分配失敗S.top = S.base;S.stacksize =  STACK_INIT_SIZE;return 1;
}Status Push(SqStack &S, SElemType e){//插入元素e為新的棧頂元素if(S.top - S.base >= S.stacksize){ //棧滿.追加存儲空間 S.base = (SElemType *) realloc(S.base, (S.stacksize + STACKINCREMENT) * sizeof(SElemType));if(!S.base) exit(0); //存儲分配失敗S.top = S.base + S.stacksize;S.stacksize += STACKINCREMENT; } *S.top++ = e;return 1;
}Status Pop(SqStack &S, SElemType &e){//若棧不為空,則刪除S的棧頂元素,用e返回其值if(S.top == S.base) return 0; //空棧e = * --S.top; //先將S.top賦值給e,再自減return 1; 
}Status GetTop(SqStack &S, SElemType &e){//若棧不為空,則用e返回S的棧頂元素if(S.top == S.base) return 0;e = *(S.top - 1);return 1; 
}int StackLength(SqStack &S){//返回棧的元素個數(shù),即棧的長度 return S.top - S.base;
}int StackEmpty(SqStack &S){//返回棧是否為空,為空返回0,不為空返回1if(!StackLength(S)) return 0;return 1; 
}void ClearStack(SqStack &S){//把S置為空棧S.top = S.base; 
}void DestroyStack(SqStack &S){//銷毀棧 if(S.base){free(S.base);S.base = S.top = NULL;S.stacksize = 0;}
}int main()
{SqStack S;InitStack(S);Push(S, 1);Push(S, 2);int e; Pop(S, e);printf("%d\n", e);GetTop(S, e);printf("%d\n", e);int l = StackLength(S);printf("length: %d\n", l);return 0; 
}

2.1.2棧的應(yīng)用舉例

數(shù)制轉(zhuǎn)換

將十進(jìn)制數(shù)N和其他d進(jìn)制數(shù)的轉(zhuǎn)換。算法原理如下：
$N=(N/d)?d+Nmodd$
要求： 對于輸入的任意一個非負(fù)十進(jìn)制整數(shù)，打印與其等值的八進(jìn)制數(shù)。

//棧的操作與2.1.1中代碼相同
int main()
{SqStack S;InitStack(S);printf("請輸入一個非負(fù)的十進(jìn)制數(shù): ");int numT;scanf("%d", &numT);while(numT){Push(S, numT % 8);numT /= 8;} int e;while(StackEmpty(S)){Pop(S, e);printf("%d", e);}return 0; 
}

括號匹配檢驗(yàn)

假設(shè)表達(dá)式中允許包含兩種括號：圓括號和方括號，其嵌套順序隨意，即()為正確格式，[{]為不正確格式。
要求： 輸入只含圓括號和方括號的字符串，判斷其是否是正確的格式。

//要加上#include<string.h> 
int main()
{SqStack S;InitStack(S);char str[100];printf("輸入只含圓括號和方括號的字符串: ");scanf("%s", str);int length = strlen(str), i, flag = 1, e;//(為1, )為2, [為3, ]為4 for(i = 0; i < length; i ++){if(str[i] == '[') Push(S, 3);if(str[i] == '(') Push(S, 1);if(str[i] == ')') {GetTop(S, e);if(e == 1) Pop(S, e);} if(str[i] == ']') {GetTop(S, e);if(e == 3) Pop(S, e);}}if(!StackEmpty(S)) printf("%s是合法字符串\n", str);else printf("%s不是合法字符串\n", str);return 0; 
}

迷宮給求解

鏈接: C語言 嚴(yán)蔚敏 數(shù)據(jù)結(jié)構(gòu) 迷宮求解_順序棧應(yīng)用

類似于深度優(yōu)先搜索，用棧去模擬這個過程。

表達(dá)式求值

鏈接: C語言 嚴(yán)蔚敏 數(shù)據(jù)結(jié)構(gòu) 表達(dá)式求值_順序棧應(yīng)用
類似于括號匹配檢驗(yàn)。

2.1.3鏈棧的表示和實(shí)現(xiàn)

鏈棧是指采用鏈?zhǔn)酱鎯Y(jié)構(gòu)實(shí)現(xiàn)的棧。通常鏈棧用單鏈表來實(shí)現(xiàn)。

由于棧的主要操作是在棧頂插入和刪除，顯然以鏈表的頭部作為棧頂是最方便的。

#include<stdio.h>
#include<stdlib.h>#define List_Init_Size 100 //線性表存儲空間的初始分配量
#define ListIncreMent 10   //線性表存儲空間的分配增量
#define ElemType int
#define Status inttypedef struct StackNode{ElemType data;struct StackNode *next;
}StackNode, *LinkStack;Status InitStack(LinkStack &S) {// 構(gòu)造一個空棧,棧頂指針為空S = NULL;return 1;
}Status Push(LinkStack &S, ElemType e) {//和順序棧的入棧不同,鏈棧的入棧前不需要判斷棧是否滿,只需要為入棧動態(tài)分配一個節(jié)點(diǎn)空間StackNode *p = (StackNode *)malloc(sizeof(StackNode)); // 使用 malloc 分配內(nèi)存if (p == NULL) {// 內(nèi)存分配失敗的處理return 0;}p->data = e;p->next = S;S = p;  // 棧頂指針指向新節(jié)點(diǎn)return 1;
}Status Pop(LinkStack &S, ElemType &e) {if (S == NULL) {return 0;  // 空棧，返回失敗}e = S->data;  // 獲取棧頂元素StackNode *p = S;  // 聲明指針 p，指向棧頂元素S = S->next;  // 將棧頂指針指向下一個元素free(p);  // 釋放棧頂元素的內(nèi)存return 1;  // 返回成功
}ElemType GetTop(LinkStack S){//返回S的棧頂元素 if(S != NULL) return S->data;
}int main()
{LinkStack S;InitStack(S);int i, e;for(i = 1; i <= 10; i ++){Push(S, i);}Pop(S, e);printf("%d\n", e);
} 

2.1.4棧與遞歸的實(shí)現(xiàn)

對于鏈表,其結(jié)點(diǎn)LNode的定義由數(shù)據(jù)域data和指針域next組成,而指針域next是一種指向LNode類型的指針,即LNode的定義中又用到了其自身所以鏈表是一種遞歸的數(shù)據(jù)結(jié)構(gòu)。

遍歷輸出鏈表中各個結(jié)點(diǎn)的遞歸算法

算法從前向后遍歷輸出鏈表結(jié)點(diǎn)的遞歸算法，直到p為NULL時遞歸結(jié)束，在遞歸過程中，p不斷指向后續(xù)節(jié)點(diǎn)。

#include<stdio.h>
#include<stdlib.h>#define List_Init_Size 100 //線性表存儲空間的初始分配量
#define ListIncreMent 10   //線性表存儲空間的分配增量
#define ElemType int
#define Status inttypedef struct LNode{ElemType      data;struct LNode  *next;
}LNode, *LinkList;void CreateList_L(LinkList &L, int n)
{// 尾插法L = (LinkList) malloc(sizeof (LNode));L->next = NULL;    LinkList tail = L;  // tail指向鏈表的尾部printf("請輸入\n");                                 //先建立一個帶頭結(jié)點(diǎn)的單鏈表for (int i = n; i > 0; --i){LinkList p = (LinkList) malloc(sizeof (LNode)); //生成新結(jié)點(diǎn)scanf("%d", &p->data);p->next = NULL;tail->next = p;tail = p;}
}
void TraverseList(LinkList p){if(p == NULL) return;else{printf("%d\n", p->data);TraverseList(p->next);}
}
int main()
{LinkList L;int i, e;CreateList_L(L, 10);TraverseList(L->next);return 0;
} 

*Hanoi塔問題的遞歸算法

#include<stdio.h>
#include<stdlib.h>int m = 0;void move(char A, int n, char C){ //將編號為n的圓盤從A移到C printf("%d, %d, %c, %c\n", ++m, n, A, C);
}void Hanoi(int n, char A, char B, char C){if(n == 1) move(A, 1, C); //將編號為1的圓盤從A移到Celse{Hanoi(n-1, A, C, B); //將A上編號1~n-1的圓盤移到B, C做輔助塔move(A, n, C);       //將編號為n的圓盤從A到CHanoi(n-1, B, A, C); //將B上編號為1~n-1的圓盤移到C, A做輔助塔	} 
}int main()
{int n = 3;Hanoi(n, 'A', 'B', 'C');return 0;
} 

遞歸算法的時間復(fù)雜度為$O(2^n)$，空間復(fù)雜度則為$O(n)$

2.2隊列

隊列的操作與棧的操作類似，不同的是，刪除實(shí)在表的頭部（即隊頭）進(jìn)行。

隊列（Queue）是一種 先進(jìn)先出（FIFO，First-In-First-Out）的線性數(shù)據(jù)結(jié)構(gòu)，它的基本特點(diǎn)是元素的插入發(fā)生在隊尾，而元素的刪除發(fā)生在隊頭。隊列通常用來處理需要按照順序處理的數(shù)據(jù)，類似于排隊的過程。

2.2.1循環(huán)隊列——隊列的順序表示和實(shí)現(xiàn)

隊列也有兩種表示，順序表示和鏈?zhǔn)奖硎尽?/p>

在隊列的順序存儲結(jié)構(gòu)中，除了用一組連續(xù)的存儲單元依次存放從隊列頭到隊列尾的元素外，尚需要附設(shè)兩個整型變量front和rear分別指示隊列頭元素和隊列尾元素的位置。在初始化創(chuàng)建空隊列時，令front = rear = 0，每當(dāng)插入新的隊列尾元素，尾指針+1，每當(dāng)刪除隊列頭元素
時，頭指針front+1。在非空隊列中頭指針始終指向隊列頭元素，而尾指針始終指向隊列尾元素的下一個位置。

為了避免隊列實(shí)際空間并未占滿而出現(xiàn)“假溢出現(xiàn)象”，我們將順序隊列變?yōu)橐粋€環(huán)狀的空間，稱為循環(huán)隊列。頭尾指針以及隊列元素之間關(guān)系不變，只是在循環(huán)隊列中，頭尾指針“依環(huán)狀態(tài)增1”的操作可用“?！边\(yùn)算來實(shí)現(xiàn)。通過取模，頭指針和尾指針就可以在順序表空間內(nèi)以頭尾銜接的方式“循環(huán)移到”。

假溢出現(xiàn)象解釋：就是因?yàn)閯h除操作會讓頭指針+1，導(dǎo)致頭指針之前的空間就不會被利用起來，而當(dāng)尾指針的值到達(dá)隊列的空間最大值時，就會產(chǎn)生假溢出了。

如何判斷隊列是否為空或者隊列是否已滿
少用一個元素空間，即隊列空間大小為m時，有m-1個元素就認(rèn)為是隊滿。即當(dāng)頭尾指針的值相同時，則認(rèn)為隊空；而當(dāng)尾指針在循環(huán)意義上+1后是等于頭指針則認(rèn)為隊滿。
隊空的條件：$Q.front=Q.rear$
隊滿的條件：$ Q.front = (Q.rear+1)%MAXQSIZE $

#include<iostream>#define MAXQSIZE 100
#define QElemType int
#define Status intusing namespace std;typedef struct{QElemType *base;  // 存儲空間的基地址int front;         // 隊頭指針int rear;          // 隊尾指針
} SqQueue;Status InitQueue(SqQueue &Q) {// 構(gòu)造一個空隊列QQ.base = new QElemType[MAXQSIZE];if(!Q.base) exit(0);Q.front = Q.rear = 0;return 1;  // 返回成功
}int QueueLength(SqQueue Q){//返回Q的元素個數(shù)return (Q.rear - Q.front + MAXQSIZE) % MAXQSIZE;
}Status EnQueue(SqQueue &Q, QElemType e){//插入元素e為Q的新的隊尾元素if((Q.rear + 1) % MAXQSIZE == Q.front){ //隊滿return 0;}Q.base[Q.rear] = e;Q.rear = (Q.rear + 1) % MAXQSIZE;return 1;
}Status DeQueue(SqQueue &Q, QElemType &e){//刪除Q的隊頭元素，用e返回其值if(Q.front == Q.rear) return 0; //隊空e = Q.base[Q.front];Q.front = (Q.front + 1) %MAXQSIZE;return 1;
}QElemType GetHead(SqQueue Q){//返回Q的隊頭元素，不修改隊頭指針if(Q.front != Q.rear) return Q.base[Q.front];
}int main()
{SqQueue Q;InitQueue(Q);for(int i = 1; i <= 10; i ++){EnQueue(Q, i);}int e = GetHead(Q);cout << e << endl;return 0;} 

2.2.2鏈隊——隊列的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)

一個鏈隊需要兩個分別指示隊頭和隊尾的指針才能唯一確定，給鏈隊添加一個頭結(jié)點(diǎn)，并令指針始終指向頭結(jié)點(diǎn)。
鏈隊的操作即為單鏈表插入和刪除操作的特殊情況，只是需進(jìn)一步修改尾指針或頭指針。

這個圖對于理解鏈隊很重要

#include<iostream>#define MAXQSIZE 100
#define QElemType int
#define Status intusing namespace std;typedef struct QNode{QElemType data;struct QNode *next;
} QNode, *QueuePtr; //鏈隊的每個結(jié)點(diǎn)typedef struct{QueuePtr front;QueuePtr rear;
}LinkQueue; //這就是鏈隊的頭指針Status InitQueue(LinkQueue &Q){//構(gòu)造一個空隊列QQ.front = Q.rear = new QNode;Q.front->next = NULL;return 1;
}Status EnQueue(LinkQueue &Q, QElemType e){//插入元素e為Q的隊尾元素QueuePtr p = new QNode; //新節(jié)點(diǎn)分配內(nèi)存 **p->data = e;p->next = NULL;Q.rear->next = p;Q.rear = p;  //類似尾插法return 1;
}Status DeQUeue(LinkQueue &Q, QElemType &e){//刪除Q的隊頭元素if(Q.front == Q.rear) return 0; //空隊QueuePtr p = Q.front;e = p->data;Q.front->next = p->next;  //修改頭指針if(Q.rear == p) Q.rear = Q.front; //刪除的最后一個元素delete p;return 1;
}QElemType GetHead(LinkQueue Q){//返回Q的隊頭元素，不修改隊頭指針if(Q.front != Q.rear)return Q.front->next->data;
}int main()
{LinkQueue Q;InitQueue(Q);for(int i = 1; i <= 10; i ++){EnQueue(Q, i);}cout << GetHead(Q) << endl;return 0;}