數據結構與算法——棧和隊列

                        🚀前言

                        棧和隊列是兩種重要的線性結構。從數據結構角度看,棧和隊列也是線性表,其特殊性在于棧和隊列的基本操作是線性表操作的子集,它們是操作受限的線性表,因此,可稱為限定性的數據結構。

                        在這里插入圖片描述

                        但是從數據類型角度看,棧和隊列是和線性表大不相同的兩種重要的抽象數據類型。棧和隊列的運用比較廣泛,屬于多型數據類型。



                        🚀棧(satck)


                        🚢棧的定義

                        (stack)是限定僅在表尾進行插入或刪除操作的線性表。因此,對于棧來說,表尾端有其特殊的含義,稱為棧頂(top),相應地,表頭端稱為棧底(bottom)。不包含元素的空表稱為空棧

                        在這里插入圖片描述

                        假設 S = ( a 1 , a 2 , . . . . a n ) S=(a1, a2,....an) S=(a1,a2,....an),則稱 a 1 a1 a1為棧底元素, a n an an為棧頂元素。棧中元素按 a 1 , a 2 , . . . a n a1,a2,...an a1,a2,...an的次序進棧,那么出棧的第一個元素應為棧頂元素

                        棧的修改是按照后進先出的原則進行的,因此,棧又稱為后進先出(last in first out)的線性表(簡稱LIFO)結構


                        🚢共享棧(節省空間)

                        兩個棧共享一個存儲空間,意義在于高效利用存儲空間

                        📌第二種說法:兩個棧底分別設置在一個空間的兩端,棧頂向中間延伸


                        共享棧的定義

                        typedef struct Linknode{
                            ElemType data;      //數據域
                            struct Linknode *next;      //指針域
                        }LiStack;                   //棧類型定義
                        
                        

                        📌共享棧的棧滿情況:當兩個棧的top在空間中某一位置相遇時


                        🚢棧的表示和實現(順序棧)

                        和線性表類似,棧也有兩種存儲表示方法——順序棧和鏈棧

                        順序棧,即棧的順序存儲結構是利用一組地址連續的存儲單元依次存放自棧底到棧頂的數據元素,同時附加指針top表示棧頂元素在順序棧中的位置。通常當top=-1時,表示此棧為空棧。


                        👻順序棧的定義

                        # define MaxSize 10         //定義棧中元素的最大個數
                        typedef struct{
                            ElemType data[MaxSize];    //靜態數組存放棧中元素 
                            int top;                   //棧頂指針
                        }SqStack;
                        
                        void testStack(){
                            SqStack S;      //聲明一個順序棧(分配空間)
                            .....
                            //后續操作
                        }
                        

                        由于棧在使用過程中所需要最大空間的大小很難估計,所以,一般來說,在初始化設空棧時不應限定棧的最大容量,常規做法是:先為棧分配一個基本容量,然后在應用過程中,當棧的空間不夠使用時再逐步擴大容量


                        👻初始化操作

                        構造一個空棧,分配內存空間

                        # define MaxSize 10         //定義棧中元素的最大個數
                        typedef struct{
                            ElemType data[MaxSize];    //靜態數組存放棧中元素 
                            int top;                   //棧頂指針
                        }SqStack;
                        
                        
                        void InitStack(SqStack &S){
                            S.top = -1;             //初始化棧頂指針
                        }
                        
                        void testStack(){
                            SqStack S;      //聲明一個順序棧(分配空間)
                            InitStack(S);
                            .....
                            //后續操作
                        }
                        
                        
                        //棧的判空操作
                        bool StackEmpty(SqStack S){
                            if(S.top == -1){
                                return true;        //棧空
                            }
                            else{
                                return false;       //不為空
                            }
                        }
                        

                        第二種定義

                        在這里插入圖片描述

                        按設定的初始分配量進行第一次存儲分配,base可稱為是棧底指針,在順序占中,它始終指向棧底的位置,若base的值為NULL,則表明棧結構不存在,top表示棧頂指針,其初始值指向棧底,即top==base空棧可以表示為top==base。每當插入新的棧頂元素時,指針top增加1,刪除棧頂元素時,指針top減1,因此,非空棧中的棧頂指針始終在棧頂元素的下一個位置上

                        #define STACK_INIT_SIZE 100;        //存儲空間初始分配量
                        #define STACKINCREMENT 10;          //存儲空間分配增量
                        typedef struct{
                            SElemType *base;        //棧底指針
                            SElemType *top;         //棧頂指針
                            int stacksize;          //當前已分配的空間
                        }SqStack;
                        
                        void InitStack(SqStack &S){
                            //構造一個空棧
                            S.base = (SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType));
                            if(!S.base) exit(OVERFLOW);         //存儲分配失敗
                            S.top = S.base;
                            S.stacksize = STACK_INIT_SIZE;
                        }
                        
                        void testStack(){
                            SqStack S;          //聲明一個順序棧
                            InitStack(S);
                            ....
                            //后續操作
                        }
                        

                        👻進棧操作

                        若棧未滿,則將x加入使之成為新棧頂

                        #define MaxSize 10;     //定義棧中元素的最大個數
                        typedef struct{
                            ElemType data[MaxSize];     //靜態數組存放棧中元素
                            int top;                    //棧頂指針
                        }SqStack;
                        
                        
                        //新元素入棧
                        bool Push(SqStack &S, ElemType x){
                            if(S.top == MaxSize-1){     //表示棧滿了
                                return false;
                            }
                            S.top = S.top + 1;          //指針先加一
                            S.data[S.top] = x;          //新元素入棧
                            return true;
                        }
                        

                        👻出棧操作

                        若棧非空,則釋放棧頂元素,并返回。

                        #define MaxSize 10;     //定義棧中元素的最大個數
                        typedef struct{
                            ElemType data[MaxSize];     //靜態數組存放棧中元素
                            int top;                    //棧頂指針
                        }SqStack;
                        
                        
                        //出棧操作
                        bool Pop(SqStack &S, ElemType &x){
                            if(S.top == -1){        //棧空,報錯
                                return false;
                            }
                            x = S.data[S.top];      //棧頂元素先出棧
                            S.top = S.top - 1;      //指針再減1
                            return true;
                        }
                        

                        👻讀取棧頂元素

                        若棧非空,則用x返回棧頂元素

                        #define MaxSize 10;     //定義棧中元素的最大個數
                        typedef struct{
                            ElemType data[MaxSize];     //靜態數組存放棧中元素
                            int top;                    //棧頂指針
                        }SqStack;
                        
                        
                        //讀取棧頂元素
                        bool GetTop(SqStack &S, ElemType &x){
                            if(S.top == -1){        //棧空,報錯
                                return false;
                            }
                            x = S.data[S.top];      //記錄棧頂元素
                            return true;
                        }
                        

                        🚢棧的表示和實現(鏈棧)

                        對于鏈棧的基本操作來說,和單鏈表的插入刪除很類似,所以就不在贅述,鏈棧的入棧和出棧操作,其實就對應單鏈表的插入和刪除操作


                        👻鏈棧的定義

                        typedef struct Linknode{
                            ElemType data;      //數據域
                            struct Linknode *next;      //指針域
                        }LiStack;                   //棧類型定義
                        

                        棧的非法操作
                        📌上溢:當棧滿了的情況下再次放入元素會造成此情況
                        📌下溢:當棧空了的情況下再次刪除元素會造成此情況



                        🚀隊列(queue)


                        🚢隊列的定義


                        和棧相反,隊列(queue)是一種先進先出(first in first out)的線性表縮寫為FIFO)。它只允許在表的一端進行插入,在另一端進行刪除元素。這種數據結構概括起來就和我們平時排隊是一樣的道理,最早進入到的隊列的元素最先離開。

                        在這里插入圖片描述


                        在隊列中,只允許插入的一端叫做隊尾(rear),允許刪除的一端則稱為隊頭(front)。假設隊列為 q = ( a 1 , a 2 , . . . a n ) , q=(a1,a2,...an), q=(a1,a2,...an)那么, a 1 a1 a1就是隊頭元素, a n an an就是隊尾元素。隊列中的元素是按照 a 1 , a 2 , a 3.... a n a1,a2,a3....an a1,a2,a3....an的順序進入的,退出隊列也只能按照這個次序依次退出,也就是說,只有在 a 1 , a 2 , a 3... a n ? 1 a1,a2,a3...an-1 a1,a2,a3...an?1都離開隊列之后, a n an an才能退出隊列


                        • 📌隊首隊尾指針的兩種指法
                          • ?隊首指針(front)指向:隊頭元素的前一個存儲位置

                          • ?隊尾指針(rear)指向:隊尾元素

                          • ?隊首指針(front)指向:隊頭元素

                          • ?隊尾指針(rear)指向:隊尾元素的下一個存儲位置

                        📌假溢出:隊中有空間,元素無法入隊


                        🚢隊列的順序表示和實現(順序隊列)


                        和順序棧類似,在隊列的順序存儲結構中,除了用一組地址連續的存儲單元依次存放隊列頭到隊列尾的元素之外,還需要附設兩個指針frontrear分別指示隊列頭元素以及隊列尾元素的位置。基本操作基于循環隊列,循環隊列的引出是為了解決假溢出的問題。


                        • 📌循環隊列的性質
                          • ?數組實現
                            • 空隊列:front == rear
                            • 滿隊列:犧牲一個單元判滿(不犧牲的話隊空隊滿無法區分)
                            • (rear+1)% maxSize == front
                            • 進隊:rear新 = (rear舊+1)% maxSize
                            • 出隊:front新 = (front舊+1)% maxSize
                            • 隊中元素個數/長度:(rear - front + maxSize) % maxSize

                        👻初始化操作

                        初始化隊列,構造一個空隊列

                        #define MaxSize 10         //定義隊列中元素的最大個數
                        typedef struct{
                            ElemType data[MaxSize];     //用靜態數組存放隊列元素
                            int front, rear;            //隊頭指針和隊尾指針
                        }SqQueue;
                        
                        //初始化隊列
                        void InitQueue(SqQueue &Q){
                            //初始化 隊頭、隊尾指針指向0
                            Q.rear = Q.front = 0;
                        }
                        
                        void testQueue(){
                            //聲明一個隊列(順序存儲)
                            SqQueue Q;
                            InitQueue(Q);
                            ...
                            //后續操作
                        }
                        
                        
                        //判斷隊列是否為空
                        bool QueueEmpty(SqQueue Q){
                            if(Q.rear == Q.front){  //隊空條件
                                return true;
                            }else{
                                return false;
                            }
                        }
                        

                        👻入隊操作

                        若隊列未滿,將x加入,使之稱為新的隊尾

                        #define MaxSize 10         //定義隊列中元素的最大個數
                        typedef struct{
                            ElemType data[MaxSize];     //用靜態數組存放隊列元素
                            int front, rear;            //隊頭指針和隊尾指針
                        }SqQueue;
                        
                        //入隊
                        bool EnQueue(SqQueue &Q, ElemType x){
                            if((Q.rear+1)%MaxSize == Q.front){       //判斷隊列是否已滿
                                return false;       //對滿則報錯
                            }
                            Q.data[Q.rear] = x;     //將x插入隊尾
                            Q.rear = (Q.rear + 1) % MaxSize;    //隊尾指針后移
                            return true;
                        }
                        

                        👻出隊操作

                        若隊列非空,刪除隊頭元素并返回x

                        #define MaxSize 10         //定義隊列中元素的最大個數
                        typedef struct{
                            ElemType data[MaxSize];     //用靜態數組存放隊列元素
                            int front, rear;            //隊頭指針和隊尾指針
                        }SqQueue;
                        
                        //出隊(刪除一個隊頭元素,并返回x)
                        bool DeQueue(SqQueue &Q, ElemType &x){
                            if(Q.rear == Q.front){      //判斷隊空
                                return false;           //隊空則報錯
                            }
                            x = Q.data[Q.front];
                            Q.front = (Q.front+1)%MaxSize;
                            return true;
                        }
                        

                        👻獲取隊頭元素操作

                        讀隊頭元素,若隊列非空,則將隊頭元素賦值給x

                        #define MaxSize 10         //定義隊列中元素的最大個數
                        typedef struct{
                            ElemType data[MaxSize];     //用靜態數組存放隊列元素
                            int front, rear;            //隊頭指針和隊尾指針
                        }SqQueue;
                        
                        //獲得隊頭元素的值,用x返回
                        bool GetHead(SqQueue Q, ElemType &x){
                            if(Q.rear == Q.front){
                                return false;       //隊空報錯
                            }
                            x = Q.data[Q.front];
                            return true;
                        }
                        
                        

                        🚢隊列的鏈式表示和實現(鏈隊列)


                        和線性表類似,隊列也可以有兩種存儲表示

                        用鏈表表示的隊列簡稱為鏈隊列,一個鏈隊列顯然需要兩個分別指示隊頭和隊尾的指針(分別稱為頭指針和尾指針)才能唯一確定。

                        鏈隊列的操作即為單鏈表的插入和刪除操作的特殊情況,只是需要修改尾指針或頭指針

                        一般情況下,刪除隊列頭元素時僅需修改頭結點中的指針,但當隊列中最后一個元素被刪除后,隊列表尾指針也丟失了,因此需對隊尾指針重新賦值(指向頭結點)


                        👻初始化操作

                        初始化隊列,構造一個空隊列

                        📌帶頭結點:

                        typedef struct LinkNode{        //鏈式隊列結點
                            ElemType data;
                            struct LinkNode *next;
                        }LinkNode;
                        
                        typedef struct{     //鏈式隊列
                            LinkNode *front, *rear  //隊列的隊頭和隊尾指針
                        }LinkQueue;
                        
                        //初始化隊列(帶頭結點)
                        void InitQueue(LinkQueue &Q){
                            //初始化 front、rear都指向頭結點
                            Q.front = Q.rear = (LinkNode*)malloc(sizeof(LinkNode));
                            Q.front -> next = NULL;
                        }
                        
                        viod testLinkQueue(){
                            LinkQueue Q;        //聲明一個隊列
                            InitQueue(Q);       //初始化隊列
                        }
                        
                        //判斷隊列是否為空
                        bool IsEmpty(LinkQueue Q){
                            if(Q.front == Q.rear){
                                return true;
                            }else{
                                return false;
                            }
                        }
                        

                        📌不帶頭結點:

                        typedef struct LinkNode{        //鏈式隊列結點
                            ElemType data;
                            struct LinkNode *next;
                        }LinkNode;
                        
                        typedef struct{     //鏈式隊列
                            LinkNode *front, *rear  //隊列的隊頭和隊尾指針
                        }LinkQueue;
                        
                        //初始化隊列(不帶頭結點)
                        void InitQueue(LinkQueue &Q){
                            //初始化 front、rear都指向頭結點
                            Q.front = NULL;
                            Q.rear = NULL;
                        }
                        
                        viod testLinkQueue(){
                            LinkQueue Q;        //聲明一個隊列
                            InitQueue(Q);       //初始化隊列
                        }
                        
                        //判斷隊列是否為空
                        bool IsEmpty(LinkQueue Q){
                            if(Q.front == NULL){
                                return true;
                            }else{
                                return false;
                            }
                        }
                        

                        👻入隊操作

                        若隊列未滿,將x加入,使之稱為新的隊尾
                        📌帶頭結點:

                        typedef struct LinkNode{        //鏈式隊列結點
                            ElemType data;
                            struct LinkNode *next;
                        }LinkNode;
                        
                        typedef struct{     //鏈式隊列
                            LinkNode *front, *rear  //隊列的隊頭和隊尾指針
                        }LinkQueue;
                        
                        //新元素入隊(帶頭結點)
                        void EnQueue(LinkQueue &Q, ElemType x){
                            LinkNode *s = (LinkNode *)malloc(sizeof(LinkNode));
                            s->data = x;
                            s->next = NULL;
                            Q.rear->next = s;       //新結點插入到rear之后
                            Q.rear = s;             //修改表尾指針
                        }
                        

                        📌不帶頭結點:

                        typedef struct LinkNode{        //鏈式隊列結點
                            ElemType data;
                            struct LinkNode *next;
                        }LinkNode;
                        
                        typedef struct{     //鏈式隊列
                            LinkNode *front, *rear  //隊列的隊頭和隊尾指針
                        }LinkQueue;
                        
                        //新元素入隊(不帶頭結點)
                        void EnQueue(LinkQueue &Q, ElemType 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;       //新結點插入到rear結點之后
                                Q.rear = s;             //修改rear指針
                            }
                        }
                        

                        👻出隊操作

                        若隊列非空,刪除隊頭元素并返回x

                        📌帶頭結點:

                        typedef struct LinkNode{        //鏈式隊列結點
                            ElemType data;
                            struct LinkNode *next;
                        }LinkNode;
                        
                        typedef struct{     //鏈式隊列
                            LinkNode *front, *rear  //隊列的隊頭和隊尾指針
                        }LinkQueue;
                        
                        //隊頭元素出隊操作(帶頭結點)
                        bool DEQueue(LinkQueue &Q, ElemType &x){
                            if(Q.front == Q.rear){
                                return      //空隊列
                            }
                            LinkNode *p = Q.front->next;
                            x = p->data;        //用變量x返回隊頭元素
                            Q.front->nexy = p->nexy;        //修改頭結點的next指針
                            if(Q.rear == p){                //此次是最后一個結點出隊
                                Q.rear = Q.front            //修改rear指針
                            }
                            free(p);                        //釋放結點空間
                            return true;
                        }
                        

                        📌不帶頭結點:

                        typedef struct LinkNode{        //鏈式隊列結點
                            ElemType data;
                            struct LinkNode *next;
                        }LinkNode;
                        
                        typedef struct{     //鏈式隊列
                            LinkNode *front, *rear  //隊列的隊頭和隊尾指針
                        }LinkQueue;
                        
                        //隊頭元素出隊操作(不帶頭結點)
                        bool DEQueue(LinkQueue &Q, ElemType &x){
                            if(Q.front == Q.rear){
                                return      //空隊列
                            }
                            LinkNode *p = Q.front;      //p指向此次出隊的結點
                            x=p->data;                  //用變量x返回隊頭結點元素
                            Q.front = p->next;          //修改front指針
                            if(Q.rear == p){            //此次是最后一個結點出隊
                                Q.front = NULL;         //front指向NULL
                                Q.rear = NULL;          //rear 指向NULL
                            }
                            free(p);                    //釋放結點空間
                            return true;
                        }
                        

                        🚢雙端隊列

                        除了棧和隊列之外,還有一種限定性數據結構——雙端隊列(deque)

                        雙端隊列是限定插入和刪除操作在表的兩端進行的線性表。著兩端分別稱作端點1端點2

                        在這里插入圖片描述


                        在實際使用中,還可以有輸出受限的雙端隊列(即一個端點允許插入和刪除,另一個端點只允許插入的雙端隊列)和輸入受限的雙端隊列(即一個端點允許插入和刪除,另一個端點只允許刪除的雙端隊列)。而如果限定雙端隊列從某個端點插入的元素只能從該端點刪除,則該雙端隊列就蛻變為了兩個棧底相鄰接的棧了



                        💻總結

                        本節文章到這里就結束啦,以上內容涵蓋數據結構與算法中棧和隊列的基本概念以及基本操作,結合代碼片段分析各基本操作的具體實現,在本文中,棧的鏈式存儲以及循環隊列是理解較為不易的點,需結合具體操作認真分析,希望各位小伙伴都能有所收獲,一如既往希望我的文章能給各位小伙伴們帶來幫助,數據結構與算法專欄也在持續更細中!!!

                        🎨覺得不錯的話記得點贊收藏呀!!🎨

                        😀別忘了給我關注~~😀

                        評論 74 您還未登錄,請先 登錄 后發表或查看評論

                        “相關推薦”對你有幫助么?

                        • 非常沒幫助
                        • 沒幫助
                        • 一般
                        • 有幫助
                        • 非常有幫助
                        提交
                        ??2022 CSDN 皮膚主題:數字50 設計師:CSDN官方博客 返回首頁

                        打賞作者

                        小田『開心館』

                        各位看官,覺得不錯就多支持喲!

                        ¥2 ¥4 ¥6 ¥10 ¥20
                        輸入1-500的整數
                        余額支付 (余額:-- )
                        掃碼支付
                        掃碼支付:¥2
                        獲取中
                        掃碼支付

                        您的余額不足,請更換掃碼支付或充值

                        打賞作者

                        實付
                        使用余額支付
                        點擊重新獲取
                        掃碼支付
                        錢包余額 0

                        抵扣說明:

                        1.余額是錢包充值的虛擬貨幣,按照1:1的比例進行支付金額的抵扣。
                        2.余額無法直接購買下載,可以購買VIP、C幣套餐、付費專欄及課程。

                        余額充值
                        久久悠悠精品综合网