1.棧

1.1.棧的定義

棧（stack）是限定僅在表尾（棧頂 top）進(jìn)行插入和刪除操作的后進(jìn)先出的線性表。

push、pop 操作在棧頂進(jìn)行。

ADT 棧(stack)
Data
    同線性表。元素具有相同的類型，相鄰元素具有前驅(qū)和后繼關(guān)系。
Operation
    InitStack(*S):    初始化操作，建立一個(gè)空棧S。
    DestroyStack(*S): 若棧存在，則銷毀它。
    ClearStack(*S):   將棧清空。
    StackEmpty(S):    若棧為空，返回true，否則返回false。
    GetTop(S, *e):    若棧存在且非空，用e返回S的棧頂元素。
    Push(*S, e):      若棧S存在，插入新元素e到棧S中并成為棧頂元素。
    Pop(*S, *e):      刪除棧S中棧頂元素，并用e返回其值。
    StackLength(S):   返回棧S的元素個(gè)數(shù)。
endADT

1.2. 棧的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)

棧的結(jié)構(gòu)定義

/* SElemType類型根據(jù)實(shí)際情況而定，這里假設(shè)為int */
typedef int SElemType;    
typedef struct
{
    SElemType data[MAXSIZE];
    /* 用于棧頂指針 */
    int top;              
}SqStack; 

棧普通3種狀態(tài)

現(xiàn)在有一個(gè)棧，StackSize是5，則棧普通情況、空棧和棧滿的情況、空棧和棧滿的情況示意圖如上

進(jìn)棧(push)：

/* 插入元素e為新的棧頂元素 */
Status Push(SqStack *S, SElemType e)
{
    /* 棧滿 */
    if (S->top == MAXSIZE - 1)    
    {
        return ERROR;
    }
    /* 棧頂指針增加一 */
    S->top++;                     
    /* 將新插入元素賦值給棧頂空間 */
    S->data[S->top] = e;          
    
    return OK;
}

出棧(pop):

/* 若棧不空，則刪除S的棧頂元素，用e返回其值，
   并返回OK；否則返回ERROR */
Status Pop(SqStack *S, SElemType *e)
{
    if (S->top == -1)
        return ERROR;
    /* 將要?jiǎng)h除的棧頂元素賦值給e */
    *e = S->data[S->top];    
    /* 棧頂指針減一 */
    S->top--;  
                  
    return OK;
}

1.3.兩棧共享空間

兩棧共享空間

數(shù)組有兩個(gè)端點(diǎn)，兩個(gè)棧有兩個(gè)棧底，讓一個(gè)棧的棧底為數(shù)組的始端，即下標(biāo)為0處，另一個(gè)棧為數(shù)組的末端，即下標(biāo)為數(shù)組長(zhǎng)度n-1處。這樣，兩個(gè)棧如果增加元素，就是兩端點(diǎn)向中間延伸。（只針對(duì)兩個(gè)具有相同數(shù)據(jù)類型的棧）

棧1為空時(shí)，即top1等于-1時(shí)；棧2為空時(shí)，即top2等于n時(shí)；棧滿時(shí)，即top1+1==top2時(shí)。

兩棧共享空間的結(jié)構(gòu)的代碼:

/* 兩棧共享空間結(jié)構(gòu) */
typedef struct
{
    SElemType data[MAXSIZE];
    int top1;    /* 棧1棧頂指針 */
    int top2;    /* 棧2棧頂指針 */
} SqDoubleStack;

對(duì)于兩棧共享空間的push方法，除了要插入元素值參數(shù)外，還需要有一個(gè)判斷是棧1還是棧2的棧號(hào)參數(shù)stackNumber。插入元素的代碼如下：

/* 插入元素e為新的棧頂元素 */
Status Push(SqDoubleStack *S, SElemType e, 
int stackNumber)
{
    /* 棧已滿，不能再push新元素了 */
    if (S->top1 + 1 == S->top2)    
        return ERROR;
    /* 棧1有元素進(jìn)棧 */
    if (stackNumber == 1)          
        /* 若棧1則先top1+1后給數(shù)組元素賦值 */
        S->data[++S->top1] = e;    
    /* 棧2有元素進(jìn)棧 */
    else if (stackNumber == 2)     
        /* 若棧2則先top2-1后給數(shù)組元素賦值 */
        S->data[--S->top2] = e;    
        
    return OK;
}

對(duì)于兩棧共享空間的pop方法，參數(shù)就只是判斷棧1棧2的參數(shù)stackNumber，代碼如下：

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

1.4.棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)（鏈棧）及實(shí)現(xiàn)

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

typedef struct StackNode
{
    SElemType data;
    struct StackNode *next;
} StackNode, *LinkStackPtr;

typedef struct LinkStack
{
    LinkStackPtr top;
    int count;
} LinkStack;

進(jìn)棧：

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

出棧：

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

2.棧的應(yīng)用－－遞歸

2.1.斐波那契數(shù)列（Fibonacci）實(shí)現(xiàn)

問：如果兔子在出生兩個(gè)月后，就有繁殖能力，一對(duì)兔子每個(gè)月能生出一對(duì)小兔子來。假設(shè)所有兔都不死，那么一年以后可以繁殖多少對(duì)兔子呢？

分析：拿新出生的一對(duì)小兔子分析一下：第一個(gè)月小兔子沒有繁殖能力，所以還是一對(duì)；兩個(gè)月后，生下一對(duì)小兔子數(shù)共有兩對(duì)；三個(gè)月以后，老兔子又生下一對(duì)，因?yàn)樾⊥米舆€沒有繁殖能力，所以一共是三對(duì)……

依次類推可以列出下表：

表中數(shù)字1，1，2，3，5，8，13……構(gòu)成了一個(gè)序列。這個(gè)數(shù)列有個(gè)十分明顯的特點(diǎn)，前面相鄰兩項(xiàng)之和，構(gòu)成了后一項(xiàng)

如下圖：

對(duì)應(yīng)的數(shù)學(xué)函數(shù)：

打印出前40位的斐波那契數(shù)列數(shù):

int main()
{
    int i;
    int a[40];
    a[0] = 0;
    a[1] = 1;
    printf("%d ", a[0]);
    printf("%d ", a[1]);
    for (i = 2; i < 40; i++)
    {
        a[i] = a[i - 1] + a[i - 2];
        printf("%d ", a[i]);
    }
    return 0;
}

其實(shí)我們的代碼，如果用遞歸來實(shí)現(xiàn)，還可以更簡(jiǎn)單:

/* 斐波那契的遞歸函數(shù) */ 
int Fbi(int i)
{
    if (i < 2)
        return i == 0 ? 0 : 1;
    /* 這里Fbi就是函數(shù)自己，它在調(diào)用自己 */
    return Fbi(i - 1) + Fbi(i - 2);    
}
int main()
{
    int i;
    for (i = 0; i < 40; i++)
        printf("%d ", Fbi(i));
    return  0;
}

相比較迭代的代碼，是不是干凈很多。
那么這段遞歸是怎么執(zhí)行的呢？我們來模擬代碼種的 Fbi(i) 函數(shù)當(dāng) i=5 的執(zhí)行過程，如下圖：

Fbi(5)執(zhí)行過程

2.2.遞歸定義

迭代和遞歸的區(qū)別是：
迭代使用的是循環(huán)結(jié)構(gòu)，遞歸使用的是選擇結(jié)構(gòu)。遞歸能使程序的結(jié)構(gòu)更清晰、更簡(jiǎn)潔、更容易讓人理解，從而減少讀懂代碼的時(shí)間。但是大量的遞歸調(diào)用會(huì)建立函數(shù)的副本，會(huì)耗費(fèi)大量的時(shí)間和內(nèi)存。迭代則不需要反復(fù)調(diào)用函數(shù)和占用額外的內(nèi)存。

遞歸與棧有什么關(guān)系？
這得從計(jì)算機(jī)系統(tǒng)的內(nèi)部說起，前面我們已經(jīng)看到遞歸是如何執(zhí)行它的前行(Fbi(i))和退回(return)階段的。遞歸過程退回的順序是它前行順序的逆序。在退回過程中，可能要執(zhí)行某些動(dòng)作，包括恢復(fù)在前行過程中存儲(chǔ)起來的某些數(shù)據(jù)。

這種存儲(chǔ)某些數(shù)據(jù)，并在后面又以存儲(chǔ)的逆序恢復(fù)這些數(shù)據(jù)，以提供之后使用的需求，顯然很符合棧這樣的數(shù)據(jù)結(jié)構(gòu)，因此，編譯器使用棧實(shí)現(xiàn)遞歸就沒什么好驚訝的了。

簡(jiǎn)單的說，就是在前行階段，對(duì)于每一層遞歸，函數(shù)的局部變量、參數(shù)值以及返回地址都被壓入棧中。在退回階段，位于棧頂?shù)木植孔兞?、參?shù)值和返回地址被彈出，用于返回調(diào)用層次中執(zhí)行代碼的其余部分，也就是恢復(fù)了調(diào)用的狀態(tài)。

3.棧的應(yīng)用－－四則運(yùn)算表達(dá)式求值

3.1.后綴（逆波蘭）表示法應(yīng)用

對(duì)于“9+(3-1)×3+10÷2”，如果要用后綴表示法應(yīng)該是什么樣子：“9 3 1-3*+102/+”，這樣的表達(dá)式稱為后綴表達(dá)式，叫后綴的原因在于所有的符號(hào)都是在要運(yùn)算數(shù)字的后面出現(xiàn)。

舉例：
后綴表達(dá)式：9 3 1-3*+10 2/+

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

1．初始化一個(gè)空棧。此棧用來對(duì)要運(yùn)算的數(shù)字進(jìn)出使用；
2．后綴表達(dá)式中前三個(gè)都是數(shù)字，所以9、3、1進(jìn)棧；

3．接下來是“-”，所以將棧中的1出棧作為減數(shù)，3出棧作為被減數(shù)，并運(yùn)算3-1得到2，再將2進(jìn)棧；
4．接著是數(shù)字3進(jìn)棧；

7．接著是10與2兩數(shù)字進(jìn)棧；
8．接下來是符號(hào)“/”，因此，棧頂?shù)?與10出棧，10與2相除，得到5，將5進(jìn)棧；

很順利的解決了計(jì)算的問題，那么如何讓“9+(3-1)×3+10÷2”轉(zhuǎn)化為“9 3 1-3+10 2/+”呢？

3.2.中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式

“9+(3-1)×3+10÷2”這樣平時(shí)所用的標(biāo)準(zhǔn)四則運(yùn)算表達(dá)式，因?yàn)樗械倪\(yùn)算符號(hào)都在兩數(shù)字之間，所以叫做中綴表達(dá)式。

中綴表達(dá)式“9+(3-1)×3+10÷2”轉(zhuǎn)化為后綴表達(dá)式“9 3 1-3*+10 2/+”

規(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á)式為止。

1．初始化一空棧，用來對(duì)符號(hào)進(jìn)出棧使用；

”進(jìn)棧。接著是數(shù)字3，輸出，總的表達(dá)式為 9 3 1-3；

7．之后是符號(hào)“+”，此時(shí)當(dāng)前棧頂元素“”比這個(gè)“+”的優(yōu)先級(jí)高，因此棧中元素出棧并輸出（沒有比“+”號(hào)更低的優(yōu)先級(jí)，所以全部出棧），總輸出表達(dá)式為9 3 1-3+。然后將當(dāng)前這個(gè)符號(hào)“+”進(jìn)棧。也就是說，前6張圖的棧底的“+”是指中綴表達(dá)式中開頭的9后面那個(gè)“+”，而圖4-9-9左圖中的棧底（也是棧頂）的“+”是指“9+(3-1)×3+”中的最后一個(gè)“+”；
8．緊接著數(shù)字10，輸出，總表達(dá)式變?yōu)? 31-3

4.隊(duì)列

4.1.隊(duì)列定義

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

ADT 隊(duì)列(Queue)
Data
    同線性表。元素具有相同的類型，相鄰元素具有前驅(qū)和后繼關(guān)系。
Operation
    InitQueue(*Q):    初始化操作，建立一個(gè)空隊(duì)列Q。
    DestroyQueue(*Q): 若隊(duì)列Q存在，則銷毀它。
    ClearQueue(*Q):   將隊(duì)列Q清空。
    QueueEmpty(Q):    若隊(duì)列Q為空，返回true，否則返回false。
    GetHead(Q, *e):   若隊(duì)列Q存在且非空，用e返回隊(duì)列Q的隊(duì)頭元素。
    EnQueue(*Q, e):   若隊(duì)列Q存在，插入新元素e到隊(duì)列Q中并成為隊(duì)尾元素。
    DeQueue(*Q, *e):  刪除隊(duì)列Q中隊(duì)頭元素，并用e返回其值。
    QueueLength(Q):   返回隊(duì)列Q的元素個(gè)數(shù)
endADT

4.2.循環(huán)對(duì)列

4.2.1.循環(huán)對(duì)列

首先了解下，什么是假溢出：

假設(shè)這個(gè)隊(duì)列的總個(gè)數(shù)不超過5個(gè)，但目前如果接著入隊(duì)的話，因數(shù)組末尾元素已經(jīng)占用，再向后加，就會(huì)產(chǎn)生數(shù)組越界的錯(cuò)誤，可實(shí)際上，我們的隊(duì)列在下標(biāo)為0和1的地方還是空閑的。我們把這種現(xiàn)象叫做“假溢出”。

解決假溢出的辦法就是后面滿了，就再從頭開始，也就是頭尾相接的循環(huán)。這種頭尾相接的順序存儲(chǔ)結(jié)構(gòu)就是循環(huán)隊(duì)列。

此時(shí)問題出來了，空隊(duì)列時(shí)，front等于rear，現(xiàn)在當(dāng)隊(duì)列滿時(shí)，也是front等于rear，那么如何判斷此時(shí)的隊(duì)列究竟是空還是滿呢？

• 辦法一是設(shè)置一個(gè)標(biāo)志變量flag，當(dāng)front==rear，且flag=0時(shí)為隊(duì)列空，當(dāng)front==rear，且flag=1時(shí)為隊(duì)列滿。

• 辦法二是當(dāng)隊(duì)列空時(shí)，條件就是front=rear，當(dāng)隊(duì)列滿時(shí)，我們修改其條件，保留一個(gè)元素空間。也就是說，隊(duì)列滿時(shí)，數(shù)組中還有一個(gè)空閑單元。例如圖4-12-8所示，我們就認(rèn)為此隊(duì)列已經(jīng)滿了，也就是說，我們不允許圖4-12-7的右圖情況出現(xiàn)。

  
  

問題又來了，第二種方法，由于rear可能比front大，也可能比front小，所以盡管它們只相差一個(gè)位置時(shí)就是滿的情況，但也可能是相差整整一圈。
若隊(duì)列的最大尺寸為QueueSize，那么隊(duì)列滿的條件是(rear+1)%QueueSize==front（取?！?”的目的就是為了整合rear與front大小為一個(gè)問題）。

另外，當(dāng)rear>front時(shí)，此時(shí)隊(duì)列的長(zhǎng)度為rear-front。但當(dāng)rear<front時(shí)，隊(duì)列長(zhǎng)度分為兩段，一段是QueueSize-front，另一段是0+rear，加在一起，隊(duì)列長(zhǎng)度為rear-front+QueueSize。
因此通用的計(jì)算隊(duì)列長(zhǎng)度公式為：

(rear-front+QueueSize)%QueueSize

有了這些講解，現(xiàn)在實(shí)現(xiàn)循環(huán)隊(duì)列就不難了。

循環(huán)隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)代碼如下：

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

循環(huán)隊(duì)列的初始化代碼如下：

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

循環(huán)隊(duì)列求隊(duì)列長(zhǎng)度代碼如下：

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

循環(huán)隊(duì)列的入隊(duì)列操作代碼如下：

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

循環(huán)隊(duì)列的出隊(duì)列操作代碼如下：

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

到這里可以看出單是順序存儲(chǔ)，若不是循環(huán)隊(duì)列，算法的時(shí)間性能是不高的，但循環(huán)隊(duì)列又面臨著數(shù)組可能會(huì)溢出的問題，所以我們還需要研究一下不需要擔(dān)心隊(duì)列長(zhǎng)度的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。

4.2.2.對(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及實(shí)現(xiàn)

鏈對(duì)列的結(jié)構(gòu)：

/* QElemType類型根據(jù)實(shí)際情況而定，這里假設(shè)為int */
typedef int QElemType;       
/* 結(jié)點(diǎn)結(jié)構(gòu) */
typedef struct QNode         
{
    QElemType data;
    struct QNode *next;
} QNode, *QueuePtr;

/* 隊(duì)列的鏈表結(jié)構(gòu) */
typedef struct               
{
    /* 隊(duì)頭、隊(duì)尾指針 */
    QueuePtr front, rear;    
} LinkQueue;

入對(duì)列：

/* 插入元素e為Q的新的隊(duì)尾元素 */
Status EnQueue(LinkQueue *Q, QElemType e)
{
    QueuePtr s = 
(QueuePtr)malloc(sizeof(QNode));
    /* 存儲(chǔ)分配失敗 */
    if (!s)               
        exit(OVERFLOW);
    s->data = e;
    s->next = NULL;
    /* 把擁有元素e新結(jié)點(diǎn)s賦值給原隊(duì)尾結(jié)點(diǎn)的后繼， */
    Q->rear->next = s;    
    /* 見上圖中① */
    /* 把當(dāng)前的s設(shè)置為隊(duì)尾結(jié)點(diǎn)，rear指向s，見上圖中② */
    Q->rear = s;  
            
    return OK;
}

出對(duì)列：

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

對(duì)于循環(huán)隊(duì)列與鏈隊(duì)列的比較，可以從兩方面來考慮，從時(shí)間上，其實(shí)它們的基本操作都是常數(shù)時(shí)間，即都為O(1)的，不過循環(huán)隊(duì)列是事先申請(qǐng)好空間，使用期間不釋放，而對(duì)于鏈隊(duì)列，每次申請(qǐng)和釋放結(jié)點(diǎn)也會(huì)存在一些時(shí)間開銷，如果入隊(duì)出隊(duì)頻繁，則兩者還是有細(xì)微差異。對(duì)于空間上來說，循環(huán)隊(duì)列必須有一個(gè)固定的長(zhǎng)度，所以就有了存儲(chǔ)元素個(gè)數(shù)和空間浪費(fèi)的問題。而鏈隊(duì)列不存在這個(gè)問題，盡管它需要一個(gè)指針域，會(huì)產(chǎn)生一些空間上的開銷，但也可以接受。所以在空間上，鏈隊(duì)列更加靈活。

總的來說，在可以確定隊(duì)列長(zhǎng)度最大值的情況下，可以用循環(huán)隊(duì)列，如果無法預(yù)估隊(duì)列的長(zhǎng)度時(shí)，則用鏈隊(duì)列。

5.總結(jié)

棧（stack）是限定僅在表尾進(jìn)行插入和刪除操作的線性表。

隊(duì)列（queue）是只允許在一端進(jìn)行插入操作，而在另一端進(jìn)行刪除操作的線性表。

它們均可以用線性表的順序存儲(chǔ)結(jié)構(gòu)來實(shí)現(xiàn)，但都存在著順序存儲(chǔ)的一些弊端。因此它們各自有各自的技巧來解決這個(gè)問題。

對(duì)于棧來說，如果是兩個(gè)相同數(shù)據(jù)類型的棧，則可以用數(shù)組的兩端作棧底的方法來讓兩個(gè)棧共享數(shù)據(jù)，這就可以最大化地利用數(shù)組的空間。

對(duì)于隊(duì)列來說，為了避免數(shù)組插入和刪除時(shí)需要移動(dòng)數(shù)據(jù)，于是就引入了循環(huán)隊(duì)列，使得隊(duì)頭和隊(duì)尾可以在數(shù)組中循環(huán)變化。解決了移動(dòng)數(shù)據(jù)的時(shí)間損耗，使得本來插入和刪除是O(n)的時(shí)間復(fù)雜度變成了O(1)。