棧和隊(duì)列

目錄

• • • 棧
    • • 順序棧
      • • 順序棧定義
        • 順序棧初始化
        • 入棧
        • 出棧
        • 讀棧頂元素
        • 判斷棧是否為空
      • 共享?xiàng)?/li>
      • • 定義
        • 初始化
        • 入棧
        • 出棧
      • 鏈棧
    • 隊(duì)列
    • • 順序隊(duì)列
      • • 定義
        • 初始化
        • 入隊(duì)
        • 出隊(duì)
        • 獲取隊(duì)頭元素
        • 判斷隊(duì)列是否為空
      • 隊(duì)列鏈?zhǔn)酱鎯?chǔ)
      • • 定義
        • 初始化
        • 入隊(duì)
        • 出隊(duì)
        • 判斷隊(duì)列是否為空
      • 隊(duì)列鏈?zhǔn)酱鎯?chǔ)（不帶頭結(jié)點(diǎn)）
      • • 定義
        • 初始化
        • 入隊(duì)
        • 出隊(duì)
        • 判斷隊(duì)列是否為空

棧

• 定義：是只允許在一端進(jìn)行插入或刪除的線性表。首先棧是一種線性表，但限定這種線性表只能在某一端進(jìn)行插入和刪除操作

順序棧

順序棧定義

• 采用順序存儲(chǔ)的棧稱為順序棧，它利用一組地址連續(xù)的存儲(chǔ)單元存放自棧底到棧頂?shù)臄?shù)據(jù)元素，同時(shí)附設(shè)一個(gè)指針（top）指示當(dāng)前棧頂元素的位置

#define MaxSize 10 typedef struct {int data[MaxSize];int top; }SqStack;

順序棧初始化

//初始化 void InitStack(SqStack& S) {S.top = -1; //data[0]還沒(méi)有放數(shù)據(jù)元素 }

入棧

//入棧 bool Push(SqStack& S, int x) {if (S.top == MaxSize - 1)return false;S.top = S.top + 1;//初始指向data[-1]S.data[S.top] = x;//等價(jià)于//S.data[++S.top] = x;return true; }

出棧

//出棧 bool Pop(SqStack& S, int& x) {if (S.top == -1)return false;x = S.data[S.top];S.top = S.top - 1;//等價(jià)于//x = S.data[S.top--];return true; }

讀棧頂元素

//讀棧頂元素 bool GetTop(SqStack S, int& x) {if (S.top == -1)return false;x = S.data[S.top];return true; }

判斷棧是否為空

//判斷棧是否為空 bool StackEmpty(SqStack S) {if (S.top == -1) //棧空return true;elsereturn false; }

共享?xiàng)?/h4>

定義

• 利用棧底位置相對(duì)不變的特征，可讓兩個(gè)順序棧共享一個(gè)一維數(shù)組空間，將兩個(gè)棧的棧底分別設(shè)置在共享空間的兩端，兩個(gè)棧頂向共享空間的中間延伸

#define MaxSize 10typedef struct {int data[MaxSize];int top0;int top1; }ShStack;ShStack s; //全局變量

初始化

//初始化棧 void InitStack(ShStack& s) {s.top1 = MaxSize; //上s.top0 = -1;//下 }

入棧

//入棧 int push(int i, int x) {if (i < 0 || i>1) {cout << "棧號(hào)輸入不對(duì)" << endl;exit(0);}if (s.top1 - s.top0 == 1) {cout << "棧滿了" << endl;return 0;}switch (i){case 0:s.data[++s.top0] = x;break;case 1:s.data[--s.top1] = x;break;} }

出棧

//出棧 int pop(int i) {if (i < 0 || i>1) {cout << "棧號(hào)輸入錯(cuò)誤" << endl;exit(0);}switch (i) {case 0:if (s.top0 == -1) {cout << "棧空" << endl;}else {//return s.data[s.top0--];cout << s.data[s.top0--] << endl;}break;case 1:if (s.top1 == MaxSize) {cout << "棧空" << endl;}else {//return s.data[s.top1++];cout << s.data[s.top1++] << endl;}break;} }

鏈棧

• 采用鏈?zhǔn)酱鎯?chǔ)的棧稱為鏈棧，鏈棧的優(yōu)點(diǎn)是便于多個(gè)棧共享存儲(chǔ)空間和提高其效率，且不存在棧滿上溢的情況。

類似單鏈表的頭插法

隊(duì)列

順序隊(duì)列

定義

• 隊(duì)列的順序?qū)崿F(xiàn)是指分配一塊連續(xù)的存儲(chǔ)單元存放隊(duì)列中的元素，并附設(shè)兩個(gè)指針：隊(duì)頭指針 front指向隊(duì)頭元素，隊(duì)尾指針 rear 指向隊(duì)尾元素的下一個(gè)位置

#define MaxSize 10 typedef struct {int data[MaxSize];int front, rear; //隊(duì)頭和隊(duì)尾指針 }SqQueue;

初始化

//初始化 void InitQueue(SqQueue& Q) {Q.rear = Q.front = 0; }

入隊(duì)

//入隊(duì) bool EnQueue(SqQueue& Q, int x) {if ((Q.rear + 1) % MaxSize == Q.front) //犧牲一個(gè)節(jié)點(diǎn)空間return false;Q.data[Q.rear] = x;Q.rear = (Q.rear + 1) % MaxSize;return true; }

出隊(duì)

//出隊(duì) bool DeQueue(SqQueue& Q, int& x) {if (Q.rear == Q.front) //判斷隊(duì)空return false;x = Q.data[Q.front];Q.front = (Q.front + 1) % MaxSize;return true; }

獲取隊(duì)頭元素

//獲取隊(duì)頭元素 bool GetHead(SqQueue Q, int& x) {if (Q.rear == Q.front)return false;x = Q.data[Q.front];return true; }

判斷隊(duì)列是否為空

//判斷隊(duì)列是否為空 bool QueueEmpty(SqQueue Q) {if (Q.rear == Q.front) //對(duì)空條件return true;elsereturn false; }

隊(duì)列鏈?zhǔn)酱鎯?chǔ)

定義

• 隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)表示為鏈隊(duì)列，它實(shí)際上是一個(gè)同時(shí)帶有隊(duì)頭指針和隊(duì)尾指針的單鏈表，只不過(guò)它只能尾進(jìn)頭出而已

typedef struct LinkNode {int data;struct LinkNode* next; }LinkNode;typedef struct {LinkNode* front, * rear; //隊(duì)頭和隊(duì)尾指針 }LinkQueue;

初始化

//初始化 void InitQueue(LinkQueue& Q) {Q.front = Q.rear = (LinkNode*)malloc(sizeof(LinkNode));Q.front->next = NULL; }

入隊(duì)

//入隊(duì) void EnQueue(LinkQueue& Q, int x) {LinkNode* s = (LinkNode*)malloc(sizeof(LinkNode));s->data = x;s->next = NULL;Q.rear->next = s;Q.rear = s; }

出隊(duì)

//出隊(duì) bool DeQueue(LinkQueue& Q, int& x) {if (Q.front == Q.rear)return false; //空隊(duì)LinkNode* p = Q.front->next;x = p->data;Q.front->next = p->next;if (Q.rear == p)Q.rear = Q.front;free(p);return true; }

判斷隊(duì)列是否為空

//判斷隊(duì)列是否為空 bool IsEmpty(LinkQueue Q) {if (Q.front == Q.rear)return true;elsereturn false; }

隊(duì)列鏈?zhǔn)酱鎯?chǔ)（不帶頭結(jié)點(diǎn)）

定義

typedef struct LinkNode {int data;struct LinkNode* next; }LinkNode;typedef struct {LinkNode* front, * rear; //隊(duì)頭和隊(duì)尾指針 }LinkQueue;

初始化

//初始化 void InitQueue(LinkQueue& Q) {Q.front = NULL;Q.rear = NULL; }

入隊(duì)

//入隊(duì)(不帶頭結(jié)點(diǎn)) void EnQueue(LinkQueue& Q, int x) {LinkNode* s = (LinkNode*)malloc(sizeof(LinkNode));s->data = x;s->next = NULL;if (Q.front == NULL) {Q.front = s;Q.rear = s;} else {Q.rear->next = s;Q.rear = s;} }

出隊(duì)

//出隊(duì)(不帶頭結(jié)點(diǎn)) bool DeQueue(LinkQueue& Q, int& x) {if (Q.front == NULL)return false;LinkNode* p = Q.front;x = p->data;Q.front = p->next;if (Q.rear == p) { //此次是最后一個(gè)節(jié)點(diǎn)出隊(duì)Q.front = NULL;Q.rear = NULL;}free(p);return true; }

判斷隊(duì)列是否為空

//判斷隊(duì)列是否為空 bool IsEmpty(LinkQueue Q) {if (Q.rear == NULL)return true;elsereturn false; }

此博文的分享就到此啦，點(diǎn)個(gè)關(guān)注再走吧
?你好啊，我是“ 滿級(jí)小白”，是一名在校大學(xué)生。
🌍主頁(yè)鏈接：滿級(jí)小白的博客
??博文主更方向?yàn)?#xff1a;計(jì)算機(jī)408，數(shù)據(jù)庫(kù)，javaEE隨著專業(yè)的深入會(huì)越來(lái)越廣哦…一起期待。
??人生的每一次成長(zhǎng)，都是從“覺(jué)得自己是個(gè)傻逼”開(kāi)始的，人生每一次的陷入困境，都是從“覺(jué)得別人是個(gè)傻逼”開(kāi)始的。
💪很高興與你相遇，一起加油！！！！

總結(jié)

以上是生活随笔為你收集整理的我爷爷都看的懂的《栈和队列》，学不会来打我的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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