棧的實(shí)際應(yīng)用（棧的實(shí)際應(yīng)用舉例）

大家好！今天讓創(chuàng)意嶺的小編來大家介紹下關(guān)于棧的實(shí)際應(yīng)用的問題，以下是小編對(duì)此問題的歸納整理，讓我們一起來看看吧。

創(chuàng)意嶺作為行業(yè)內(nèi)優(yōu)秀的企業(yè)，服務(wù)客戶遍布全球各地，相關(guān)業(yè)務(wù)請(qǐng)撥打電話：175-8598-2043，或添加微信：1454722008

本文目錄:

• 1、堆棧有什么作用嗎，請(qǐng)舉幾個(gè)具體的例子

• 2、在什么情況下可以用棧來存儲(chǔ)數(shù)據(jù)？

• 3、求救：棧和隊(duì)列在程序設(shè)計(jì)中的作用

• 4、c語言 棧是怎么應(yīng)用的 哪位大神能說的好理解點(diǎn)

一、堆棧有什么作用嗎，請(qǐng)舉幾個(gè)具體的例子

堆棧應(yīng)用非常廣的

二、在什么情況下可以用棧來存儲(chǔ)數(shù)據(jù)？

堆棧的特點(diǎn)是先進(jìn)后出，速度快！在單片機(jī)設(shè)計(jì)中主要用于保留現(xiàn)場(chǎng)和恢復(fù)現(xiàn)場(chǎng)。在函數(shù)的跳轉(zhuǎn)和中斷中，堆棧的優(yōu)點(diǎn)表現(xiàn)得淋漓盡致。

下面是關(guān)于堆棧的一些詳細(xì)講述：

堆棧都是一種數(shù)據(jù)項(xiàng)按序排列的數(shù)據(jù)結(jié)構(gòu)，只能在一端(稱為棧頂(top))對(duì)數(shù)據(jù)項(xiàng)進(jìn)行插入和刪除。

要點(diǎn)：

堆：順序隨意

棧：后進(jìn)先出(Last-In/First-Out)

編輯本段堆和棧的區(qū)別

一、預(yù)備知識(shí)—程序的內(nèi)存分配

一個(gè)由c/C++編譯的程序占用的內(nèi)存分為以下幾個(gè)部分

1、棧區(qū)（stack）— 由編譯器自動(dòng)分配釋放 ，存放函數(shù)的參數(shù)值，局部變量的值等。其操作方式類似于數(shù)據(jù)結(jié)構(gòu)中的棧。

2、堆區(qū)（heap） — 一般由程序員分配釋放， 若程序員不釋放，程序結(jié)束時(shí)可能由OS回收 。注意它與數(shù)據(jù)結(jié)構(gòu)中的堆是兩回事，分配方式倒是類似于鏈表。

3、全局區(qū)（靜態(tài)區(qū)）（static）—，全局變量和靜態(tài)變量的存儲(chǔ)是放在一塊的，初始化的全局變量和靜態(tài)變量在一塊區(qū)域， 未初始化的全局變量和未初始化的靜態(tài)變量在相鄰的另一塊區(qū)域。 - 程序結(jié)束后由系統(tǒng)釋放。

4、文字常量區(qū) —常量字符串就是放在這里的。 程序結(jié)束后由系統(tǒng)釋放 。

5、程序代碼區(qū)—存放函數(shù)體的二進(jìn)制代碼。

二、例子程序

這是一個(gè)前輩寫的，非常詳細(xì)

//main.cpp

int a = 0; 全局初始化區(qū)

char *p1; 全局未初始化區(qū)

main()

{

int b; 棧

char s[] = "abc"; 棧

char *p2; 棧

char *p3 = "123456"; 123456\0在常量區(qū)，p3在棧上。

static int c =0； 全局（靜態(tài)）初始化區(qū)

p1 = (char *)malloc(10);

p2 = (char *)malloc(20);

}

分配得來得10和20字節(jié)的區(qū)域就在堆區(qū)。

strcpy(p1, "123456"); 123456\0放在常量區(qū)，編譯器可能會(huì)將它與p3所指向的"123456"優(yōu)化成一個(gè)地方。

編輯本段堆和棧的理論知識(shí)

1.申請(qǐng)方式

stack:

由系統(tǒng)自動(dòng)分配。 例如，聲明在函數(shù)中一個(gè)局部變量 int b; 系統(tǒng)自動(dòng)在棧中為b開辟空間

heap:

需要程序員自己申請(qǐng)，并指明大小，在c中malloc函數(shù)

如p1 = (char *)malloc(10);

在C++中用new運(yùn)算符

如p2 = new char[20];//(char *)malloc(10);

但是注意p1、p2本身是在棧中的。

2.申請(qǐng)后系統(tǒng)的響應(yīng)

棧：只要棧的剩余空間大于所申請(qǐng)空間，系統(tǒng)將為程序提供內(nèi)存，否則將報(bào)異常提示棧溢出。

堆：首先應(yīng)該知道操作系統(tǒng)有一個(gè)記錄空閑內(nèi)存地址的鏈表，當(dāng)系統(tǒng)收到程序的申請(qǐng)時(shí)，會(huì)遍歷該鏈表，尋找第一個(gè)空間大于所申請(qǐng)空間的堆結(jié)點(diǎn)，然后將該結(jié)點(diǎn)從空閑結(jié)點(diǎn)鏈表中刪除，并將該結(jié)點(diǎn)的空間分配給程序，另外，對(duì)于大多數(shù)系統(tǒng)，會(huì)在這塊內(nèi)存空間中的首地址處記錄本次分配的大小，這樣，代碼中的delete語句才能正確的釋放本內(nèi)存空間。另外，由于找到的堆結(jié)點(diǎn)的大小不一定正好等于申請(qǐng)的大小，系統(tǒng)會(huì)自動(dòng)的將多余的那部分重新放入空閑鏈表中。

3.申請(qǐng)大小的限制

棧：在Windows下,棧是向低地址擴(kuò)展的數(shù)據(jù)結(jié)構(gòu)，是一塊連續(xù)的內(nèi)存的區(qū)域。這句話的意思是棧頂?shù)牡刂泛蜅５淖畲笕萘渴窍到y(tǒng)預(yù)先規(guī)定好的，在 WINDOWS下，棧的大小是2M（也有的說是1M，總之是一個(gè)編譯時(shí)就確定的常數(shù)），如果申請(qǐng)的空間超過棧的剩余空間時(shí)，將提示overflow。因此，能從棧獲得的空間較小。

堆：堆是向高地址擴(kuò)展的數(shù)據(jù)結(jié)構(gòu)，是不連續(xù)的內(nèi)存區(qū)域。這是由于系統(tǒng)是用鏈表來存儲(chǔ)的空閑內(nèi)存地址的，自然是不連續(xù)的，而鏈表的遍歷方向是由低地址向高地址。堆的大小受限于計(jì)算機(jī)系統(tǒng)中有效的虛擬內(nèi)存。由此可見，堆獲得的空間比較靈活，也比較大。

4.申請(qǐng)效率的比較

棧由系統(tǒng)自動(dòng)分配，速度較快。但程序員是無法控制的。

堆是由new分配的內(nèi)存，一般速度比較慢，而且容易產(chǎn)生內(nèi)存碎片,不過用起來最方便.

另外，在WINDOWS下，最好的方式是用VirtualAlloc分配內(nèi)存，他不是在堆，也不是在棧,而是直接在進(jìn)程的地址空間中保留一快內(nèi)存，雖然用起來最不方便。但是速度快，也最靈活

5.堆和棧中的存儲(chǔ)內(nèi)容

棧： 在函數(shù)調(diào)用時(shí)，第一個(gè)進(jìn)棧的是主函數(shù)中函數(shù)調(diào)用后的下一條指令（函數(shù)調(diào)用語句的下一條可執(zhí)行語句）的地址，然后是函數(shù)的各個(gè)參數(shù)，在大多數(shù)的C編譯器中，參數(shù)是由右往左入棧的，然后是函數(shù)中的局部變量。注意靜態(tài)變量是不入棧的。

當(dāng)本次函數(shù)調(diào)用結(jié)束后，局部變量先出棧，然后是參數(shù)，最后棧頂指針指向最開始存的地址，也就是主函數(shù)中的下一條指令，程序由該點(diǎn)繼續(xù)運(yùn)行。

堆：一般是在堆的頭部用一個(gè)字節(jié)存放堆的大小。堆中的具體內(nèi)容有程序員安排。

6.存取效率的比較

char s1[] = "aaaaaaaaaaaaaaa";

char *s2 = "bbbbbbbbbbbbbbbbb";

aaaaaaaaaaa是在運(yùn)行時(shí)刻賦值的；

而bbbbbbbbbbb是在編譯時(shí)就確定的；

但是，在以后的存取中，在棧上的數(shù)組比指針?biāo)赶虻淖址?例如堆)快。

比如：

#include

void main()

{

char a = 1;

char c[] = "1234567890";

char *p ="1234567890";

a = c[1];

a = p[1];

return;

}

對(duì)應(yīng)的匯編代碼

10: a = c[1];

00401067 8A 4D F1 mov cl,byte ptr [ebp-0Fh]

0040106A 88 4D FC mov byte ptr [ebp-4],cl

11: a = p[1];

0040106D 8B 55 EC mov edx,dword ptr [ebp-14h]

00401070 8A 42 01 mov al,byte ptr [edx+1]

00401073 88 45 FC mov byte ptr [ebp-4],al

第一種在讀取時(shí)直接就把字符串中的元素讀到寄存器cl中，而第二種則要先把指針值讀到edx中，在根據(jù)edx讀取字符，顯然慢了。

7.小結(jié)：

堆和棧的區(qū)別可以用如下的比喻來看出：

使用棧就象我們?nèi)ワ堭^里吃飯，只管點(diǎn)菜（發(fā)出申請(qǐng)）、付錢、和吃（使用），吃飽了就走，不必理會(huì)切菜、洗菜等準(zhǔn)備工作和洗碗、刷鍋等掃尾工作，他的好處是快捷，但是自由度小。

使用堆就象是自己動(dòng)手做喜歡吃的菜肴，比較麻煩，但是比較符合自己的口味，而且自由度大。

編輯本段堆和棧的區(qū)別主要分：

操作系統(tǒng)方面的堆和棧，如上面說的那些，不多說了。

還有就是數(shù)據(jù)結(jié)構(gòu)方面的堆和棧，這些都是不同的概念。這里的堆實(shí)際上指的就是（滿足堆性質(zhì)的）優(yōu)先隊(duì)列的一種數(shù)據(jù)結(jié)構(gòu)，第1個(gè)元素有最高的優(yōu)先權(quán)；棧實(shí)際上就是滿足先進(jìn)后出的性質(zhì)的數(shù)學(xué)或數(shù)據(jù)結(jié)構(gòu)。

雖然堆棧，堆棧的說法是連起來叫，但是他們還是有很大區(qū)別的，連著叫只是由于歷史的原因。

三、求救：棧和隊(duì)列在程序設(shè)計(jì)中的作用

棧和隊(duì)列是兩種特殊的線性表，它們的邏輯結(jié)構(gòu)和線性表相同，只是其運(yùn)算規(guī)則較線性表有更多的限制，

故又稱它們?yōu)檫\(yùn)算受限的線性表。棧和隊(duì)列被廣泛應(yīng)用于各種程序設(shè)計(jì)中。

棧的定義及基本運(yùn)算

1、棧的定義

棧（Stack）是限制僅在表的一端進(jìn)行插入和刪除運(yùn)算的線性表。

(1)通常稱插入、刪除的這一端為棧頂（Top），另一端稱為棧底（Bottom）。

(2)當(dāng)表中沒有元素時(shí)稱為空棧。

(3)棧為后進(jìn)先出（Last In First Out）的線性表，簡(jiǎn)稱為LIFO 表。

棧的修改是按后進(jìn)先出的原則進(jìn)行。每次刪除（退棧）的總是當(dāng)前棧中"最新"的元素，即最后插入

（進(jìn)棧）的元素，而最先插入的是被放在棧的底部，要到最后才能刪除。

【示例】元素是以a1，a2，…，an 的順序進(jìn)棧，退棧的次序卻是an，an-1，…，a1。

2、棧的基本運(yùn)算

（1）InitStack（S）

構(gòu)造一個(gè)空棧S。

（2）StackEmpty（S）

判?？铡Ｈ鬝 為空棧，則返回TRUE，否則返回FALSE。

（3）StackFull（S）

判棧滿。若S 為滿棧，則返回TRUE，否則返回FALSE。

注意：

該運(yùn)算只適用于棧的順序存儲(chǔ)結(jié)構(gòu)。

（4）Push（S，x）

進(jìn)棧。若棧S 不滿，則將元素x 插入S 的棧頂。

（5）Pop（S）

退棧。若棧S 非空，則將S 的棧頂元素刪去，并返回該元素。

（6）StackTop（S）

取棧頂元素。若棧S 非空，則返回棧頂元素，但不改變棧的狀態(tài)。

順序棧

棧的順序存儲(chǔ)結(jié)構(gòu)簡(jiǎn)稱為順序棧,它是運(yùn)算受限的順序表。

1、順序棧的類型定義

#define StackSize 100 //假定預(yù)分配的?？臻g最多為100 個(gè)元素

typedef char DataType;//假定棧元素的數(shù)據(jù)類型為字符

typedef struct{

DataType data[StackSize];

int top;

}SeqStack;

注意：

①順序棧中元素用向量存放

②棧底位置是固定不變的，可設(shè)置在向量兩端的任意一個(gè)端點(diǎn)

③棧頂位置是隨著進(jìn)棧和退棧操作而變化的，用一個(gè)整型量top（通常稱top 為棧頂指針）來指示

當(dāng)前棧頂位置

2、順序棧的基本操作

前提條件：

設(shè)S 是SeqStack 類型的指針變量。若棧底位置在向量的低端，即S-＞data[0]是棧底元素。

（1） 進(jìn)棧操作

進(jìn)棧時(shí)，需要將S-＞top 加1

注意：

①S-＞top==StackSize-1 表示棧滿

②"上溢"現(xiàn)象--當(dāng)棧滿時(shí)，再做進(jìn)棧運(yùn)算產(chǎn)生空間溢出的現(xiàn)象。

上溢是一種出錯(cuò)狀態(tài)，應(yīng)設(shè)法避免。

（2） 退棧操作

退棧時(shí)，需將S-＞top 減1

注意：

①S-＞top<0 表示空棧

②"下溢"現(xiàn)象——當(dāng)?？諘r(shí)，做退棧運(yùn)算產(chǎn)生的溢出現(xiàn)象。

下溢是正?，F(xiàn)象，常用作程序控制轉(zhuǎn)移的條件。

順序棧在進(jìn)棧和退棧操作時(shí)的具體變化情況【參見動(dòng)畫演示】

3、順序棧的基本運(yùn)算

（1） 置?？?/p>

void InitStack（SeqStack *S）

{//將順序棧置空

S->top=-1;

}

（2） 判?？?/p>

int StackEmpty（SeqStack *S）

{

return S->top==-1;

}

（3） 判棧滿

int StackFull（SeqStack *SS）

{

return S->top==StackSize-1;

}

（4） 進(jìn)棧

void Push（S，x）

{

if (StackFull(S))

Error("Stack overflow"); //上溢，退出運(yùn)行

S->data[++S->top]=x;//棧頂指針加1 后將x 入棧

}

（5） 退棧

DataType Pop（S）

{

if(StackEmpty(S))

Error("Stack underflow"); //下溢，退出運(yùn)行

return S->data[S->top--];//棧頂元素返回后將棧頂指針減1

}

（6） 取棧頂元素

DataType StackTop（S）

{

if(StackEmpty(S))

Error("Stack is empty");

return S->data[S->top];

}

4、兩個(gè)棧共享同一存儲(chǔ)空間

當(dāng)程序中同時(shí)使用兩個(gè)棧時(shí)，可以將兩個(gè)棧的棧底設(shè)在向量空間的兩端，讓兩個(gè)棧各自向中間延伸。

當(dāng)一個(gè)棧里的元素較多，超過向量空間的一半時(shí)，只要另一個(gè)棧的元素不多，那么前者就可以占用后者的

部分存儲(chǔ)空間。

只有當(dāng)整個(gè)向量空間被兩個(gè)棧占滿（即兩個(gè)棧頂相遇）時(shí)，才會(huì)發(fā)生上溢。因此，兩個(gè)棧共享一個(gè)長

度為m 的向量空間和兩個(gè)棧分別占用兩個(gè)長度為└ m/2┘和┌m/2┐的向量空間比較，前者發(fā)生上溢的概

率比后者要小得多。

鏈棧

棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱為鏈棧。

1、鏈棧的類型定義

鏈棧是沒有附加頭結(jié)點(diǎn)的運(yùn)算受限的單鏈表。棧頂指針就是鏈表的頭指針。

鏈棧的類型說明如下：

typedef struct stacknode{

DataType data

struct stacknode *next

}StackNode;

typedef struct{

StackNode *top; //棧頂指針

}LinkStack;

注意：

①LinkStack 結(jié)構(gòu)類型的定義是為了方便在函數(shù)體中修改top 指針本身

②若要記錄棧中元素個(gè)數(shù)，可將元素個(gè)數(shù)屬性放在LinkStack 類型中定義。

2、鏈棧的基本運(yùn)算

（1） 置棧空

Void InitStack(LinkStack *S)

{

S->top=NULL;

}

（2） 判?？?/p>

int StackEmpty(LinkStack *S)

{

return S->top==NULL;

}

（3） 進(jìn)棧

void Push(LinkStack *S,DataType x)

{//將元素x 插入鏈棧頭部

StackNode *p=(StackNode *)malloc(sizeof(StackNode));

p->data=x;

p->next=S->top;//將新結(jié)點(diǎn)*p 插入鏈棧頭部

S->top=p;

}

（4） 退棧

DataType Pop(LinkStack *S)

{

DataType x;

StackNode *p=S->top;//保存棧頂指針

if(StackEmpty(S))

Error("Stack underflow."); //下溢

x=p->data; //保存棧頂結(jié)點(diǎn)數(shù)據(jù)

S->top=p->next; //將棧頂結(jié)點(diǎn)從鏈上摘下

free(p);

return x;

}

（5） 取棧頂元素

DataType StackTop(LinkStack *S)

{

if(StackEmpty(S))

Error("Stack is empty.")

return S->top->data;

}

注意：

鏈棧中的結(jié)點(diǎn)是動(dòng)態(tài)分配的，所以可以不考慮上溢，無須定義StackFull 運(yùn)算。

--------------------------------------------------------------------------------------------

-----------------

隊(duì)列的定義及基本運(yùn)算

1、定義

隊(duì)列（Queue）是只允許在一端進(jìn)行插入，而在另一端進(jìn)行刪除的運(yùn)算受限的線性表

（1）允許刪除的一端稱為隊(duì)頭（Front）。

（2）允許插入的一端稱為隊(duì)尾（Rear）。

（3）當(dāng)隊(duì)列中沒有元素時(shí)稱為空隊(duì)列。

（4）隊(duì)列亦稱作先進(jìn)先出（First In First Out）的線性表，簡(jiǎn)稱為FIFO 表。

隊(duì)列的修改是依先進(jìn)先出的原則進(jìn)行的。新來的成員總是加入隊(duì)尾（即不允許"加塞"），每次離開的

成員總是隊(duì)列頭上的（不允許中途離隊(duì)），即當(dāng)前"最老的"成員離隊(duì)。

【例】在隊(duì)列中依次加入元素a1，a2，… ，an 之后，a1 是隊(duì)頭元素，an 是隊(duì)尾元素。退出隊(duì)列的次序

只能是a1，a2，… ，an。

2、隊(duì)列的基本邏輯運(yùn)算

（1）InitQueue（Q）

置空隊(duì)。構(gòu)造一個(gè)空隊(duì)列Q。

（2）QueueEmpty（Q）

判隊(duì)空。若隊(duì)列Q 為空，則返回真值，否則返回假值。

（3） QueueFull（Q）

判隊(duì)滿。若隊(duì)列Q 為滿，則返回真值，否則返回假值。

注意：

此操作只適用于隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)。

（4） EnQueue（Q，x）

若隊(duì)列Q 非滿，則將元素x 插入Q 的隊(duì)尾。此操作簡(jiǎn)稱入隊(duì)。

（5） DeQueue（Q）

若隊(duì)列Q 非空，則刪去Q 的隊(duì)頭元素，并返回該元素。此操作簡(jiǎn)稱出隊(duì)。

（6） QueueFront（Q）

若隊(duì)列Q 非空，則返回隊(duì)頭元素，但不改變隊(duì)列Q 的狀態(tài)。

順序隊(duì)列

1、順序隊(duì)列

（1）順序隊(duì)列的定義

隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)稱為順序隊(duì)列，順序隊(duì)列實(shí)際上是運(yùn)算受限的順序表。

（2） 順序隊(duì)列的表示

①和順序表一樣，順序隊(duì)列用一個(gè)向量空間來存放當(dāng)前隊(duì)列中的元素。

②由于隊(duì)列的隊(duì)頭和隊(duì)尾的位置是變化的，設(shè)置兩個(gè)指針front 和rear 分別指示隊(duì)頭元素和隊(duì)尾元素

在向量空間中的位置，它們的初值在隊(duì)列初始化時(shí)均應(yīng)置為0。

（3） 順序隊(duì)列的基本操作

①入隊(duì)時(shí)：將新元素插入rear 所指的位置，然后將rear 加1。

②出隊(duì)時(shí)：刪去front 所指的元素，然后將front 加1 并返回被刪元素。

注意：

①當(dāng)頭尾指針相等時(shí)，隊(duì)列為空。

②在非空隊(duì)列里，隊(duì)頭指針始終指向隊(duì)頭元素，尾指針始終指向隊(duì)尾元素的下一位置。

順序隊(duì)列基本操作【參見動(dòng)畫演示】

（4）順序隊(duì)列中的溢出現(xiàn)象

① "下溢"現(xiàn)象

當(dāng)隊(duì)列為空時(shí)，做出隊(duì)運(yùn)算產(chǎn)生的溢出現(xiàn)象。“下溢”是正?，F(xiàn)象，常用作程序控制轉(zhuǎn)移的條件。

② "真上溢"現(xiàn)象

當(dāng)隊(duì)列滿時(shí)，做進(jìn)棧運(yùn)算產(chǎn)生空間溢出的現(xiàn)象?！罢嫔弦纭笔且环N出錯(cuò)狀態(tài)，應(yīng)設(shè)法避免。

③ "假上溢"現(xiàn)象

由于入隊(duì)和出隊(duì)操作中，頭尾指針只增加不減小，致使被刪元素的空間永遠(yuǎn)無法重新利用。當(dāng)隊(duì)列中

實(shí)際的元素個(gè)數(shù)遠(yuǎn)遠(yuǎn)小于向量空間的規(guī)模時(shí)，也可能由于尾指針已超越向量空間的上界而不能做入隊(duì)操作。

該現(xiàn)象稱為"假上溢"現(xiàn)象。

【例】假設(shè)下述操作序列作用在初始為空的順序隊(duì)列上：

EnQueue，DeQueue，EnQueue，DeQueue，…

盡管在任何時(shí)刻，隊(duì)列元素的個(gè)數(shù)均不超過1，但是只要該序列足夠長，事先定義的向量空間無論多大

均會(huì)產(chǎn)生指針越界錯(cuò)誤。

鏈隊(duì)列

1、鏈隊(duì)列的定義

隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)簡(jiǎn)稱為鏈隊(duì)列。它是限制僅在表頭刪除和表尾插入的單鏈表。

2、鏈隊(duì)列的結(jié)構(gòu)類型說明

注意：

增加指向鏈表上的最后一個(gè)結(jié)點(diǎn)的尾指針，便于在表尾做插入操作。

鏈隊(duì)列示意圖見上圖，圖中Q 為LinkQueue 型的指針。

3、鏈隊(duì)列的基本運(yùn)算

（1） 置空隊(duì)

void InitQueue(LinkQueue *Q)

{

Q->front=Q->rear=NULL;

}

（2） 判隊(duì)空

intQueueEmpty(LinkQueue *Q)

{

return Q->front==NULL&&Q->rear==Null;

//實(shí)際上只須判斷隊(duì)頭指針是否為空即可

}

（3） 入隊(duì)

void EnQueue(LinkQueue *Q,DataType x)

{//將元素x 插入鏈隊(duì)列尾部

QueueNode *p=(QueueNode *)malloc(sizeof(QueueNode));//申請(qǐng)新結(jié)點(diǎn)

p->data=x; p->next=NULL;

if(QueueEmpty(Q))

Q->front=Q->rear=p; //將x 插入空隊(duì)列

else { //x 插入非空隊(duì)列的尾

Q->rear->next=p; //*p 鏈到原隊(duì)尾結(jié)點(diǎn)后

Q->rear=p; //隊(duì)尾指針指向新的尾

}

}

（4） 出隊(duì)

DataType DeQueue (LinkQueue *Q)

{

DataType x;

QueueNode *p;

if(QueueEmpty(Q))

Error("Queue underflow");//下溢

p=Q->front; //指向?qū)︻^結(jié)點(diǎn)

x=p->data; //保存對(duì)頭結(jié)點(diǎn)的數(shù)據(jù)

Q->front=p->next; //將對(duì)頭結(jié)點(diǎn)從鏈上摘下

if(Q->rear==p)//原隊(duì)中只有一個(gè)結(jié)點(diǎn)，刪去后隊(duì)列變空，此時(shí)隊(duì)頭指針已為空

Q->rear=NULL;

free(p); //釋放被刪隊(duì)頭結(jié)點(diǎn)

return x; //返回原隊(duì)頭數(shù)據(jù)

}

（5） 取隊(duì)頭元素

DataType QueueFront(LinkQueue *Q)

{

if(QueueEmpty(Q))

Error("Queue if empty.");

return Q->front->data;

}

注意：

①和鏈棧類似，無須考慮判隊(duì)滿的運(yùn)算及上溢。

②在出隊(duì)算法中，一般只需修改隊(duì)頭指針。但當(dāng)原隊(duì)中只有一個(gè)結(jié)點(diǎn)時(shí)，該結(jié)點(diǎn)既是隊(duì)頭也是隊(duì)尾，

故刪去此結(jié)點(diǎn)時(shí)亦需修改尾指針，且刪去此結(jié)點(diǎn)后隊(duì)列變空。

③以上討論的是無頭結(jié)點(diǎn)鏈隊(duì)列的基本運(yùn)算。和單鏈表類似，為了簡(jiǎn)化邊界條件的處理，在隊(duì)頭結(jié)點(diǎn)

前也可附加一個(gè)頭結(jié)點(diǎn)，增加頭結(jié)點(diǎn)的鏈隊(duì)列的基本運(yùn)算【參見練習(xí)】

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

為充分利用向量空間，克服"假上溢"現(xiàn)象的方法是：將向量空間想象為一個(gè)首尾相接的圓環(huán)，并稱這

種向量為循環(huán)向量。存儲(chǔ)在其中的隊(duì)列稱為循環(huán)隊(duì)列（Circular Queue）。

（1） 循環(huán)隊(duì)列的基本操作

循環(huán)隊(duì)列中進(jìn)行出隊(duì)、入隊(duì)操作時(shí)，頭尾指針仍要加1，朝前移動(dòng)。只不過當(dāng)頭尾指針指向向量上界

（QueueSize-1）時(shí)，其加1 操作的結(jié)果是指向向量的下界0。這種循環(huán)意義下的加1 操作可以描述為：

① 方法一：

if(i+1==QueueSize) //i 表示front 或rear

i=0;

else

i++;

② 方法二--利用"模運(yùn)算"

i=(i+1)%QueueSize；

（2） 循環(huán)隊(duì)列邊界條件處理

循環(huán)隊(duì)列中，由于入隊(duì)時(shí)尾指針向前追趕頭指針；出隊(duì)時(shí)頭指針向前追趕尾指針，造成隊(duì)空和隊(duì)滿時(shí)

頭尾指針均相等。因此，無法通過條件front==rear 來判別隊(duì)列是"空"還是"滿"。【參見動(dòng)畫演示】

解決這個(gè)問題的方法至少有三種：

① 另設(shè)一布爾變量以區(qū)別隊(duì)列的空和滿；

② 少用一個(gè)元素的空間。約定入隊(duì)前，測(cè)試尾指針在循環(huán)意義下加1 后是否等于頭指針，若相等則認(rèn)

為隊(duì)滿（注意：rear 所指的單元始終為空）；

③使用一個(gè)計(jì)數(shù)器記錄隊(duì)列中元素的總數(shù)（即隊(duì)列長度）。

（3） 循環(huán)隊(duì)列的類型定義

#define Queur Size 100 //應(yīng)根據(jù)具體情況定義該值

typedef char Queue DataType; //DataType 的類型依賴于具體的應(yīng)用

typedef Sturet{ //頭指針，隊(duì)非空時(shí)指向隊(duì)頭元素

int front; //尾指針，隊(duì)非空時(shí)指向隊(duì)尾元素的下一位置

int rear; //計(jì)數(shù)器，記錄隊(duì)中元素總數(shù)

DataType data[QueueSize]

}CirQueue;

（4） 循環(huán)隊(duì)列的基本運(yùn)算

用第三種方法，循環(huán)隊(duì)列的六種基本運(yùn)算：

① 置隊(duì)空

void InitQueue(CirQueue *Q)

{

Q->front=Q->rear=0;

Q->count=0; //計(jì)數(shù)器置0

}

② 判隊(duì)空

int QueueEmpty(CirQueue *Q)

{

return Q->count==0; //隊(duì)列無元素為空

}

③ 判隊(duì)滿

int QueueFull(CirQueue *Q)

{

return Q->count==QueueSize; //隊(duì)中元素個(gè)數(shù)等于QueueSize 時(shí)隊(duì)滿

}

④ 入隊(duì)

void EnQueue(CirQueuq *Q,DataType x)

{

if(QueueFull((Q))

Error("Queue overflow"); //隊(duì)滿上溢

Q->count ++; //隊(duì)列元素個(gè)數(shù)加1

Q->data[Q->rear]=x; //新元素插入隊(duì)尾

Q->rear=(Q->rear+1)%QueueSize; //循環(huán)意義下將尾指針加1

⑤ 出隊(duì)

DataType DeQueue(CirQueue *Q)

{

DataType temp;

if(QueueEmpty((Q))

Error("Queue underflow"); //隊(duì)空下溢

temp=Q->data[Q->front];

Q->count--; //隊(duì)列元素個(gè)數(shù)減1

Q->front=(Q->front+1)&QueueSize; //循環(huán)意義下的頭指針加1

return temp;

}

⑥取隊(duì)頭元素

DataType QueueFront(CirQueue *Q)

{

if(QueueEmpty(Q))

Error("Queue if empty.");

return Q->data[Q->front];

}

四、c語言 棧是怎么應(yīng)用的 哪位大神能說的好理解點(diǎn)

棧分為出棧和入棧，入棧是為了保護(hù)你剛剛正在進(jìn)行的程序，把它放進(jìn)指定的空閑位置，出棧是你執(zhí)行完另一件事后把之前保存入棧的東西在從存放的地方拿出來。這是為了保護(hù)數(shù)據(jù)，防止丟失。！

比如你正看著書呢，小伙伴叫你去玩，你就加個(gè)書簽在讀過的那一頁放進(jìn)書櫥，玩回來了拿出書翻到那一頁接著讀。而你的書簽就相當(dāng)于起到保護(hù)作用，回來翻到那一頁就相當(dāng)于取出之前存入棧中的內(nèi)容。

以上就是關(guān)于棧的實(shí)際應(yīng)用相關(guān)問題的回答。希望能幫到你，如有更多相關(guān)問題，您也可以聯(lián)系我們的客服進(jìn)行咨詢，客服也會(huì)為您講解更多精彩的知識(shí)和內(nèi)容。

推薦閱讀：

棧的實(shí)際應(yīng)用（棧的實(shí)際應(yīng)用舉例）

德陽花園景觀設(shè)計(jì)企業(yè)（德陽花園景觀設(shè)計(jì)企業(yè)名單）

在線營銷的主要內(nèi)容（在線營銷的主要內(nèi)容是什么）