代碼如下：

/*若棧不空，則刪除S的棧頂元素，用e返回其值，并返回OK；否則返回ERROR*/
Status Pop(SqDoubleStack *S, ElemType *e, int stackNumber){
    if(stackNumber == 0){
        if(S->top0 == -1){
            return ERROR;   //說(shuō)明棧0已經(jīng)是空棧，溢出
        }
        *e = S->data[S->top0--]; //將棧0的棧頂元素出棧，隨后棧頂指針減1
    }else if(stackNumber == 1){
        if(S->top1 == MAXSIZE){
            return ERROR;   //說(shuō)明棧1是空棧，溢出
        }
        *e = S->data[S->top1++];    //將棧1的棧頂元素出棧，隨后棧頂指針加1
    }
    return OK;
}

三、棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

1、鏈棧

采用鏈?zhǔn)酱鎯?chǔ)的棧稱為鏈棧，鏈棧的優(yōu)點(diǎn)是便于多個(gè)棧共享存儲(chǔ)空間和提高其效率，且不存在棧滿上溢的情況。通常采用單鏈表實(shí)現(xiàn)，并規(guī)定所有操作都是在單鏈表的表頭進(jìn)行的。這里規(guī)定鏈棧沒(méi)有頭節(jié)點(diǎn)，Lhead指向棧頂元素，如下圖所示。

對(duì)于空棧來(lái)說(shuō)，鏈表原定義是頭指針指向空，那么鏈棧的空其實(shí)就是top=NULL的時(shí)候。

鏈棧的結(jié)構(gòu)代碼如下：

/*棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)*/
/*構(gòu)造節(jié)點(diǎn)*/
typedef struct StackNode{
    ElemType data;
    struct StackNode *next;
}StackNode, *LinkStackPrt;
/*構(gòu)造鏈棧*/
typedef struct LinkStack{
    LinkStackPrt top;
    int count;
}LinkStack;

2、鏈棧的基本算法

（1）鏈棧的進(jìn)棧

對(duì)于鏈棧的進(jìn)棧push操作，假設(shè)元素值為e的新節(jié)點(diǎn)是s，top為棧頂指針，示意圖如下：

代碼如下：

/*插入元素e為新的棧頂元素*/
Status Push(LinkStack *S, ElemType e){
    LinkStackPrt p = (LinkStackPrt)malloc(sizeof(StackNode));
    p->data = e;
    p->next = S->top;    //把當(dāng)前的棧頂元素賦值給新節(jié)點(diǎn)的直接后繼
    S->top = p; //將新的結(jié)點(diǎn)S賦值給棧頂指針
    S->count++;
    return OK;
}

（2）鏈棧的出棧

鏈棧的出棧pop操作，也是很簡(jiǎn)單的三句操作。假設(shè)變量p用來(lái)存儲(chǔ)要?jiǎng)h除的棧頂結(jié)點(diǎn)，將棧頂指針下移以為，最后釋放p即可，

如下圖所示：

代碼如下：

/*若棧不空，則刪除S的棧頂元素，用e返回其值，并返回OK；否則返回ERROR*/
Status Pop(LinkStack *S, ElemType *e){
    LinkStackPtr p;
    if(StackEmpty(*S)){
        return ERROR;
    }
    *e = S->top->data;
    p = S->top; //將棧頂結(jié)點(diǎn)賦值給p
    S->top = S->top->next;  //使得棧頂指針下移一位，指向后一結(jié)點(diǎn)
    free(p);    //釋放結(jié)點(diǎn)p
    S->count--;
    return OK;
}

3、性能分析

鏈棧的進(jìn)棧push和出棧pop操作都很簡(jiǎn)單，時(shí)間復(fù)雜度均為O(1)。
對(duì)比一下順序棧與鏈棧,它們?cè)跁r(shí)間復(fù)雜度上是一樣的,均為O(1)。對(duì)于空間性能,順序棧需要事先確定一個(gè)固定的長(zhǎng)度,可能會(huì)存在內(nèi)存空間浪費(fèi)的問(wèn)題,但它的優(yōu)勢(shì)是存取時(shí)定位很方便,而鏈棧則要求每個(gè)元素都有指針域,這同時(shí)也增加了一些內(nèi)存開(kāi)銷,但對(duì)于棧的長(zhǎng)度無(wú)限制。所以它們的區(qū)別和線性表中討論的一樣,如果棧的使用過(guò)程中元素變化不可預(yù)料,有時(shí)很小,有時(shí)非常大,那么最好是用鏈棧,反之,如果它的變化在可控范圍內(nèi),建議使用順序棧會(huì)更好一些。

四、棧的應(yīng)用——遞歸

1、遞歸的定義

遞歸是一種重要的程序設(shè)計(jì)方法。簡(jiǎn)單地說(shuō),若在一個(gè)函數(shù)、過(guò)程或數(shù)據(jù)結(jié)構(gòu)的定義中又應(yīng)用了它自身,則這個(gè)函數(shù)、過(guò)程或數(shù)據(jù)結(jié)構(gòu)稱為是遞歸定義的,簡(jiǎn)稱遞歸。
它通常把一個(gè)大型的復(fù)雜問(wèn)題層層轉(zhuǎn)化為一個(gè)與原問(wèn)題相似的規(guī)模較小的問(wèn)題來(lái)求解,遞歸策略只需少量的代碼就可以描述岀解題過(guò)程所需要的多次重復(fù)計(jì)算,大大減少了程序的代碼量但在通常情況下,它的效率并不是太高。

2、斐波那契數(shù)列

在解釋斐波那契數(shù)列之前，我們想看經(jīng)典的兔子繁殖的問(wèn)題：

說(shuō)如果兔子在出生兩個(gè)月后,就有繁殖能力,一對(duì)兔子每個(gè)月能生出一對(duì)小兔子 來(lái)。假設(shè)所有兔都不死,那么一年以后可以繁殖多少對(duì)兔子呢?

• 第一個(gè)月初有一對(duì)剛誕生的兔子第
• 二個(gè)月之后（第三個(gè)月初）它們可以生育
• 每月每對(duì)可生育的兔子會(huì)誕生下一對(duì)新兔子
• 兔子永不死去

我們拿新出生的一對(duì)小兔子分析一下:第一個(gè)月小兔子沒(méi)有繁殖能力,所以還是一對(duì);兩個(gè)月后,生下一對(duì)小兔子數(shù)共有兩對(duì);三個(gè)月以后,老兔子又生下一對(duì),因?yàn)樾⊥米舆€沒(méi)有繁殖能力,所以一共是三對(duì)…依次類推得出這樣一個(gè)圖：

從這個(gè)圖可以看出，斐波那契數(shù)列數(shù)列有一個(gè)明顯的特點(diǎn)，即：前面兩項(xiàng)之和，構(gòu)成了后一項(xiàng)。
如果用數(shù)學(xué)函數(shù)定義斐波那契數(shù)列，那就是：

而這個(gè)，就是遞歸的一個(gè)典型例子，用程序?qū)崿F(xiàn)時(shí)如下：

/*斐波那契數(shù)列的實(shí)現(xiàn)*/
int Fib(int n){
    if(n == 0){
        return 0;   //邊界條件
    }else if(n == 1){
        return 1;	//邊界條件
    }else{
        return Fib(n-1) + Fib(n-2); //遞歸表達(dá)式
    }
}

必須注意遞歸模型不能是循環(huán)定義的,其必須滿足下面的兩個(gè)條件

• 遞歸表達(dá)式(遞歸體)
• 邊界條件(遞歸出口)

遞歸的精髓在于能否將原始問(wèn)題轉(zhuǎn)換為屬性相同但規(guī)模較小的問(wèn)題
在遞歸調(diào)用的過(guò)程中,系統(tǒng)為每一層的返回點(diǎn)、局部變量、傳入實(shí)參等開(kāi)辟了遞歸工作棧來(lái)進(jìn)行數(shù)據(jù)存儲(chǔ),遞歸次數(shù)過(guò)多容易造成棧溢出等。而其效率不高的原因是遞歸調(diào)用過(guò)程中包含很多重復(fù)的計(jì)算。下面以n=5為例,列出遞歸調(diào)用執(zhí)行過(guò)程,如圖所示：

如圖可知，程序每往下遞歸一次，就會(huì)把運(yùn)算結(jié)果放到棧中保存，直到程序執(zhí)行到臨界條件，然后便會(huì)把保存在棧中的值按照先進(jìn)后出的順序一個(gè)個(gè)返回，最終得出結(jié)果。

五、棧的應(yīng)用——四則運(yùn)算表達(dá)式求值

1、后綴表達(dá)式計(jì)算結(jié)果

表達(dá)式求值是程序設(shè)計(jì)語(yǔ)言編譯中一個(gè)最基本的問(wèn)題,它的實(shí)現(xiàn)是棧應(yīng)用的一個(gè)典型范例。中綴表達(dá)式不僅依賴運(yùn)算符的優(yōu)先級(jí),而且還要處理括號(hào)。后綴表達(dá)式的運(yùn)算符在操作數(shù)后面，在后綴表達(dá)式中已考慮了運(yùn)算符的優(yōu)先級(jí),沒(méi)有括號(hào),只有操作數(shù)和運(yùn)算符。例如中綴表達(dá)式 A + B ∗ ( C − D ) − E / F A+B*(C-D)-E/F A+B∗(C−D)−E/F所對(duì)應(yīng)的后綴表達(dá)式為 A B C D − ∗ + E F / − ABCD-*+EF/- ABCD−∗+EF/−。

后綴表達(dá)式計(jì)算規(guī)則：從左到右遍歷表達(dá)式的每個(gè)數(shù)字和符號(hào)，遇到是數(shù)字就進(jìn)棧，遇到是符號(hào)，就將處于棧頂兩個(gè)數(shù)字出棧，進(jìn)項(xiàng)運(yùn)算，運(yùn)算結(jié)果進(jìn)棧，一直到最終獲得結(jié)果。

后綴表達(dá)式 A B C D − ∗ + E F / − ABCD-*+EF/- ABCD−∗+EF/−求值的過(guò)程需要12步，如下表所示：

讀者也可將后綴表達(dá)式與原運(yùn)算式對(duì)應(yīng)的表達(dá)式樹(shù)(用來(lái)表示算術(shù)表達(dá)式的二元樹(shù))的后序遍歷進(jìn)行比較,可以發(fā)現(xiàn)它們有異曲同工之妙。
如下圖則是 A + B ∗ ( C − D ) − E / F A+B*(C-D)-E/F A+B∗(C−D)−E/F對(duì)應(yīng)的表達(dá)式，它的后序遍歷即是表達(dá)式 A B C D − ∗ + E F / − ABCD-*+EF/- ABCD−∗+EF/−。

2、中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式

我們把平時(shí)所用的標(biāo)準(zhǔn)四則運(yùn)算表達(dá)式,即 a + b − a ∗ ( ( c + d ) / e − f ) + g a+b-a*((c+d)/e-f)+g a+b−a∗((c+d)/e−f)+g叫做中綴
表達(dá)式。因?yàn)樗械倪\(yùn)算符號(hào)都在兩數(shù)字的中間,現(xiàn)在我們的問(wèn)題就是中綴到后綴的轉(zhuǎn)化。

規(guī)則:從左到右遍歷中綴表達(dá)式的每個(gè)數(shù)字和符號(hào),若是數(shù)字就輸出,即成為后
綴表達(dá)式的一部分;若是符號(hào),則判斷其與棧頂符號(hào)的優(yōu)先級(jí),是右括號(hào)或優(yōu)先級(jí)低于棧頂符號(hào)(乘除優(yōu)先加減)則棧頂元素依次出棧并輸出,并將當(dāng)前符號(hào)進(jìn)棧,一直到最終輸出后綴表達(dá)式為止。

例：將中綴表達(dá)式 a + b − a ∗ ( ( c + d ) / e − f ) + g a+b-a*((c+d)/e-f)+g a+b−a∗((c+d)/e−f)+g轉(zhuǎn)化為相應(yīng)的后綴表達(dá)式。

分析：需要根據(jù)操作符

的優(yōu)先級(jí)來(lái)進(jìn)行棧的變化,我們用icp來(lái)表示當(dāng)前掃描到的運(yùn)算符ch的優(yōu)先級(jí),該運(yùn)算符進(jìn)棧后的優(yōu)先級(jí)為isp,則運(yùn)算符的優(yōu)先級(jí)如下表所示[isp是棧內(nèi)優(yōu)先( in stack priority)數(shù),icp是棧外優(yōu)先( in coming priority)數(shù)]。

我們?cè)诒磉_(dá)式后面加上符號(hào)‘#’,表示表達(dá)式結(jié)束。

具體轉(zhuǎn)換過(guò)程如下：

即相應(yīng)的后綴表達(dá)式為 a b + a c d + e / f − ∗ − g + ab+acd+e/f-*-g+ ab+acd+e/f−∗−g+。

隊(duì)列

一、隊(duì)列的基本概念

1、隊(duì)列的定義

隊(duì)列（queue）是只允許在一端進(jìn)行插入操作，而在另一端進(jìn)行刪除操作的線性表。
隊(duì)列是一種先進(jìn)先出（First In First Out）的線性表，簡(jiǎn)稱FIFO。允許插入的一端稱為隊(duì)尾，允許刪除的一端稱為隊(duì)頭。

隊(duì)頭（Front）：允許刪除的一端，又稱隊(duì)首。
隊(duì)尾（Rear）：允許插入的一端。
空隊(duì)列：不包含任何元素的空表。

2、隊(duì)列的常見(jiàn)基本操作

• InitQueue(&Q)：初始化隊(duì)列，構(gòu)造一個(gè)空隊(duì)列Q。
• QueueEmpty(Q)：判隊(duì)列空，若隊(duì)列Q為空返回true，否則返回
• false。EnQueue(&Q, x)：入隊(duì)，若隊(duì)列Q未滿，將x加入，使之成為新的隊(duì)尾。
• DeQueue(&Q, &x)：出隊(duì)，若隊(duì)列Q非空，刪除隊(duì)頭元素，并用x返回。
• GetHead(Q, &x)：讀隊(duì)頭元素，若隊(duì)列Q非空，則將隊(duì)頭元素賦值給x

二、隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)

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

1、順序隊(duì)列

隊(duì)列的順序存儲(chǔ)類型可描述為:

#define MAXSIZE 50	//定義隊(duì)列中元素的最大個(gè)數(shù)
typedef struct{
	ElemType data[MAXSIZE];	//存放隊(duì)列元素
	int front,rear;
}SqQueue;

初始狀態(tài)（隊(duì)空條件）：Q->front == Q->rear == 0。
進(jìn)隊(duì)操作：隊(duì)不滿時(shí)，先送值到隊(duì)尾元素，再將隊(duì)尾指針加1。
出隊(duì)操作：隊(duì)不空時(shí)，先取隊(duì)頭元素值，再將隊(duì)頭指針加1。

如圖d，隊(duì)列出現(xiàn)“上溢出”，然而卻又不是真正的溢出，所以是一種“假溢出”。

2、循環(huán)隊(duì)列

解決假溢出的方法就是后面滿了，就再?gòu)念^開(kāi)始，也就是頭尾相接的循環(huán)。我們把隊(duì)列的這種頭尾相接的順序存儲(chǔ)結(jié)構(gòu)稱為循環(huán)隊(duì)列。
當(dāng)隊(duì)首指針Q->front = MAXSIZE-1后，再前進(jìn)一個(gè)位置就自動(dòng)到0，這可以利用除法取余運(yùn)算（%）來(lái)實(shí)現(xiàn)。

初始時(shí)：Q->front = Q->rear=0。隊(duì)首指針進(jìn)1：Q->front = (Q->front + 1) % MAXSIZE。隊(duì)尾指針進(jìn)1：Q->rear = (Q->rear + 1) % MAXSIZE。隊(duì)列長(zhǎng)度：(Q->rear - Q->front + MAXSIZE) % MAXSIZE。

出隊(duì)入隊(duì)時(shí)，指針都按照順時(shí)針?lè)较蚯斑M(jìn)1，如下圖所示：

那么，循環(huán)隊(duì)列隊(duì)空和隊(duì)滿的判斷條件是什么呢？
顯然，隊(duì)空的條件是 Q->front == Q->rear 。若入隊(duì)元素的速度快于出隊(duì)元素的速度，則隊(duì)尾指針很快就會(huì)趕上隊(duì)首指針，如圖( d1 ）所示，此時(shí)可以看出隊(duì)滿時(shí)也有 Q ->front == Q -> rear 。
為了區(qū)分隊(duì)空還是隊(duì)滿的情況，有三種處理方式：
（1）犧牲一個(gè)單元來(lái)區(qū)分隊(duì)空和隊(duì)滿，入隊(duì)時(shí)少用一個(gè)隊(duì)列單元，這是種較為普遍的做法，約定以“隊(duì)頭指針在隊(duì)尾指針的下一位置作為隊(duì)滿的標(biāo)志”，如圖 ( d2 ）所示。

• 隊(duì)滿條件： (Q->rear + 1)%Maxsize == Q->front
• 隊(duì)空條件仍： Q->front == Q->rear
• 隊(duì)列中元素的個(gè)數(shù)： (Q->rear - Q ->front + Maxsize)% Maxsize

（2）類型中增設(shè)表示元素個(gè)數(shù)的數(shù)據(jù)成員。這樣，隊(duì)空的條件為 Q->size == O ；隊(duì)滿的條件為 Q->size == Maxsize 。這兩種情況都有 Q->front == Q->rear
（3）類型中增設(shè)tag 數(shù)據(jù)成員，以區(qū)分是隊(duì)滿還是隊(duì)空。tag 等于0時(shí)，若因刪除導(dǎo)致 Q->front == Q->rear ，則為隊(duì)空；tag 等于 1 時(shí)，若因插入導(dǎo)致 Q ->front == Q->rear ，則為隊(duì)滿。

我們重點(diǎn)討論第一種方法

3、循環(huán)隊(duì)列常見(jiàn)基本算法

（1）循環(huán)隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)

typedef int ElemType;   //ElemType的類型根據(jù)實(shí)際情況而定，這里假定為int
#define MAXSIZE 50  //定義元素的最大個(gè)數(shù)
/*循環(huán)隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)*/
typedef struct{
    ElemType data[MAXSIZE];
    int front;  //頭指針
    int rear;   //尾指針,若隊(duì)列不空，指向隊(duì)列尾元素的下一個(gè)位置
}SqQueue;

（2）循環(huán)隊(duì)列的初始化

/*初始化一個(gè)空隊(duì)列Q*/
Status InitQueue(SqQueue *Q){
    Q->front = 0;
    Q->rear = 0;
    return OK;
}

（3）循環(huán)隊(duì)列判隊(duì)空

/*判隊(duì)空*/
bool isEmpty(SqQueue Q){
    if(Q.rear == Q.front){
        return true;
    }else{
        return false;
    }
}

（4）求循環(huán)隊(duì)列長(zhǎng)度

/*返回Q的元素個(gè)數(shù)，也就是隊(duì)列的當(dāng)前長(zhǎng)度*/
int QueueLength(SqQueue Q){
    return (Q.rear - Q.front + MAXSIZE) % MAXSIZE;
}

（5）循環(huán)隊(duì)列入隊(duì)

/*若隊(duì)列未滿，則插入元素e為Q新的隊(duì)尾元素*/
Status EnQueue(SqQueue *Q, ElemType e){
    if((Q->real + 1) % MAXSIZE == Q->front){
        return ERROR;   //隊(duì)滿
    }
    Q->data[Q->rear] = e;   //將元素e賦值給隊(duì)尾
    Q->rear = (Q->rear + 1) % MAXSIZE;  //rear指針向后移一位置，若到最后則轉(zhuǎn)到數(shù)組頭部
    return OK;
}

（6）循環(huán)隊(duì)列出隊(duì)

/*若隊(duì)列不空，則刪除Q中隊(duì)頭元素，用e返回其值*/
Status DeQueue(SqQueue *Q, ElemType *e){
    if(isEmpty(Q)){
        return REEOR;   //隊(duì)列空的判斷
    }
    *e = Q->data[Q->front]; //將隊(duì)頭元素賦值給e
    Q->front = (Q->front + 1) % MAXSIZE;    //front指針向后移一位置，若到最后則轉(zhuǎn)到數(shù)組頭部
}

三、隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

1、鏈隊(duì)列

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

空隊(duì)列時(shí)，front和real都指向頭結(jié)點(diǎn)。

2、鏈隊(duì)列常見(jiàn)基本算法

（1）鏈隊(duì)列存儲(chǔ)類型

/*鏈?zhǔn)疥?duì)列結(jié)點(diǎn)*/
typedef struct {
	ElemType data;
	struct LinkNode *next;
}LinkNode;
/*鏈?zhǔn)疥?duì)列*/
typedef struct{
	LinkNode *front, *rear;	//隊(duì)列的隊(duì)頭和隊(duì)尾指針
}LinkQueue;

當(dāng)Q->front == NULL 并且 Q->rear == NULL 時(shí)，鏈隊(duì)列為空。

（2）鏈隊(duì)列初始化

void InitQueue(LinkQueue *Q){
	Q->front = Q->rear = (LinkNode)malloc(sizeof(LinkNode));	//建立頭結(jié)點(diǎn)
	Q->front->next = NULL;	//初始為空
}

（3）鏈隊(duì)列入隊(duì)

Status EnQueue(LinkQueue *Q, ElemType e){
	LinkNode s = (LinkNode)malloc(sizeof(LinkNode));
	s->data = e;
	s->next = NULL;
	Q->rear->next = s;	//把擁有元素e新結(jié)點(diǎn)s賦值給原隊(duì)尾結(jié)點(diǎn)的后繼
	Q->rear = s;	//把當(dāng)前的s設(shè)置為新的隊(duì)尾結(jié)點(diǎn)
	return OK;
}

（4）鏈隊(duì)列出隊(duì)

出隊(duì)操作時(shí)，就是頭結(jié)點(diǎn)的后繼結(jié)點(diǎn)出隊(duì)，將頭結(jié)點(diǎn)的后繼改為它后面的結(jié)點(diǎn)，若鏈表除頭結(jié)點(diǎn)外只剩一個(gè)元素時(shí)，則需將rear指向頭結(jié)點(diǎn)。

/*若隊(duì)列不空，刪除Q的隊(duì)頭元素，用e返回其值，并返回OK，否則返回ERROR*/
Status DeQueue(LinkQueue *Q, Elemtype *e){
	LinkNode p;
	if(Q->front == Q->rear){
		return ERROR;
	}
	p = Q->front->next;	//將欲刪除的隊(duì)頭結(jié)點(diǎn)暫存給p
	*e = p->data;	//將欲刪除的隊(duì)頭結(jié)點(diǎn)的值賦值給e
	Q->front->next = p->next;	//將原隊(duì)頭結(jié)點(diǎn)的后繼賦值給頭結(jié)點(diǎn)后繼
	//若刪除的隊(duì)頭是隊(duì)尾，則刪除后將rear指向頭結(jié)點(diǎn)
	if(Q->rear == p){
		Q->rear = Q->front;
	}
	free(p);
	return OK;
}

四、雙端隊(duì)列

1、定義

雙端隊(duì)列是指允許兩端都可以進(jìn)行入隊(duì)和出隊(duì)操作的隊(duì)列，如下圖所示。其元素的邏輯結(jié)構(gòu)仍是線性結(jié)構(gòu)。將隊(duì)列的兩端分別稱為前端和后端，兩端都可以入隊(duì)和出隊(duì)。

在雙端隊(duì)列進(jìn)隊(duì)時(shí)，前端進(jìn)的元素排列在隊(duì)列中后端進(jìn)的元素的前面，后端進(jìn)的元素排列在隊(duì)列中前端進(jìn)的元素的后面。在雙端隊(duì)列出隊(duì)時(shí)，無(wú)論是前端還是后端出隊(duì)，先出的元素排列在后出的元素的前面。

2、特殊的雙端隊(duì)列

在實(shí)際使用中，根據(jù)使用場(chǎng)景的不同，存在某些特殊的雙端隊(duì)列。

輸出受限的雙端隊(duì)列：允許在一端進(jìn)行插入和刪除， 但在另一端只允許插入的雙端隊(duì)列稱為輸出受限的雙端隊(duì)列，如下圖所示。

輸入受限的雙端隊(duì)列：允許在一端進(jìn)行插入和刪除，但在另一端只允許刪除的雙端隊(duì)列稱為輸入受限的雙端隊(duì)列，如下圖所示。若限定雙端隊(duì)列從某個(gè)端點(diǎn)插入的元素只能從該端點(diǎn)刪除，則該雙端隊(duì)列就蛻變?yōu)閮蓚€(gè)棧底相鄰接的棧。

到此這篇關(guān)于c語(yǔ)言數(shù)據(jù)結(jié)構(gòu)之棧和隊(duì)列詳解(Stack & Queue)的文章就介紹到這了,更多相關(guān)c語(yǔ)言據(jù)結(jié)構(gòu)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！