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

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

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

本文目錄:

• 1、堆棧有什么作用嗎，請舉幾個具體的例子

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

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

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

一、堆棧有什么作用嗎，請舉幾個具體的例子

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

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

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

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

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

要點：

堆：順序隨意

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

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

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

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

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

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

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

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

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

二、例子程序

這是一個前輩寫的，非常詳細(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ū)，編譯器可能會將它與p3所指向的"123456"優(yōu)化成一個地方。

編輯本段堆和棧的理論知識

1.申請方式

stack:

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

heap:

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

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

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

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

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

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

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

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

3.申請大小的限制

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

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

4.申請效率的比較

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

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

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

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

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

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

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

6.存取效率的比較

char s1[] = "aaaaaaaaaaaaaaa";

char *s2 = "bbbbbbbbbbbbbbbbb";

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

而bbbbbbbbbbb是在編譯時就確定的；

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

比如：

#include

void main()

{

char a = 1;

char c[] = "1234567890";

char *p ="1234567890";

a = c[1];

a = p[1];

return;

}

對應(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

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

7.小結(jié)：

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

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

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

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

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

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

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

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

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

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

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

1、棧的定義

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

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

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

(3)棧為后進(jìn)先出（Last In First Out）的線性表，簡稱為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)造一個空棧S。

（2）StackEmpty（S）

判?？?。若S 為空棧，則返回TRUE，否則返回FALSE。

（3）StackFull（S）

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

注意：

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

（4）Push（S，x）

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

（5）Pop（S）

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

（6）StackTop（S）

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

順序棧

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

1、順序棧的類型定義

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

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

typedef struct{

DataType data[StackSize];

int top;

}SeqStack;

注意：

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

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

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

當(dāng)前棧頂位置

2、順序棧的基本操作

前提條件：

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

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

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

注意：

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

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

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

（2） 退棧操作

退棧時，需將S-＞top 減1

注意：

①S-＞top<0 表示空棧

②"下溢"現(xiàn)象——當(dāng)棧空時，做退棧運(yùn)算產(chǎn)生的溢出現(xiàn)象。

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

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

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、兩個棧共享同一存儲空間

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

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

部分存儲空間。

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

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

率比后者要小得多。

鏈棧

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

1、鏈棧的類型定義

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

鏈棧的類型說明如下：

typedef struct stacknode{

DataType data

struct stacknode *next

}StackNode;

typedef struct{

StackNode *top; //棧頂指針

}LinkStack;

注意：

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

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

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

（1） 置?？?/p>

Void InitStack(LinkStack *S)

{

S->top=NULL;

}

（2） 判棧空

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é)點*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é)點數(shù)據(jù)

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

free(p);

return x;

}

（5） 取棧頂元素

DataType StackTop(LinkStack *S)

{

if(StackEmpty(S))

Error("Stack is empty.")

return S->top->data;

}

注意：

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

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

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

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

1、定義

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

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

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

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

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

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

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

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

只能是a1，a2，… ，an。

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

（1）InitQueue（Q）

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

（2）QueueEmpty（Q）

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

（3） QueueFull（Q）

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

注意：

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

（4） EnQueue（Q，x）

若隊列Q 非滿，則將元素x 插入Q 的隊尾。此操作簡稱入隊。

（5） DeQueue（Q）

若隊列Q 非空，則刪去Q 的隊頭元素，并返回該元素。此操作簡稱出隊。

（6） QueueFront（Q）

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

順序隊列

1、順序隊列

（1）順序隊列的定義

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

（2） 順序隊列的表示

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

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

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

（3） 順序隊列的基本操作

①入隊時：將新元素插入rear 所指的位置，然后將rear 加1。

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

注意：

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

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

順序隊列基本操作【參見動畫演示】

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

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

當(dāng)隊列為空時，做出隊運(yùn)算產(chǎn)生的溢出現(xiàn)象?！跋乱纭笔钦，F(xiàn)象，常用作程序控制轉(zhuǎn)移的條件。

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

當(dāng)隊列滿時，做進(jìn)棧運(yùn)算產(chǎn)生空間溢出的現(xiàn)象。“真上溢”是一種出錯狀態(tài)，應(yīng)設(shè)法避免。

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

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

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

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

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

EnQueue，DeQueue，EnQueue，DeQueue，…

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

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

鏈隊列

1、鏈隊列的定義

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

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

注意：

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

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

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

（1） 置空隊

void InitQueue(LinkQueue *Q)

{

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

}

（2） 判隊空

intQueueEmpty(LinkQueue *Q)

{

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

//實際上只須判斷隊頭指針是否為空即可

}

（3） 入隊

void EnQueue(LinkQueue *Q,DataType x)

{//將元素x 插入鏈隊列尾部

QueueNode *p=(QueueNode *)malloc(sizeof(QueueNode));//申請新結(jié)點

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

if(QueueEmpty(Q))

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

else { //x 插入非空隊列的尾

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

Q->rear=p; //隊尾指針指向新的尾

}

}

（4） 出隊

DataType DeQueue (LinkQueue *Q)

{

DataType x;

QueueNode *p;

if(QueueEmpty(Q))

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

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

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

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

if(Q->rear==p)//原隊中只有一個結(jié)點，刪去后隊列變空，此時隊頭指針已為空

Q->rear=NULL;

free(p); //釋放被刪隊頭結(jié)點

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

}

（5） 取隊頭元素

DataType QueueFront(LinkQueue *Q)

{

if(QueueEmpty(Q))

Error("Queue if empty.");

return Q->front->data;

}

注意：

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

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

故刪去此結(jié)點時亦需修改尾指針，且刪去此結(jié)點后隊列變空。

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

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

循環(huán)隊列

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

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

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

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

（QueueSize-1）時，其加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)隊列邊界條件處理

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

頭尾指針均相等。因此，無法通過條件front==rear 來判別隊列是"空"還是"滿"?！緟⒁妱赢嬔菔尽?/p>

解決這個問題的方法至少有三種：

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

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

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

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

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

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

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

typedef Sturet{ //頭指針，隊非空時指向隊頭元素

int front; //尾指針，隊非空時指向隊尾元素的下一位置

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

DataType data[QueueSize]

}CirQueue;

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

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

① 置隊空

void InitQueue(CirQueue *Q)

{

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

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

}

② 判隊空

int QueueEmpty(CirQueue *Q)

{

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

}

③ 判隊滿

int QueueFull(CirQueue *Q)

{

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

}

④ 入隊

void EnQueue(CirQueuq *Q,DataType x)

{

if(QueueFull((Q))

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

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

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

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

⑤ 出隊

DataType DeQueue(CirQueue *Q)

{

DataType temp;

if(QueueEmpty((Q))

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

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

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

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

return temp;

}

⑥取隊頭元素

DataType QueueFront(CirQueue *Q)

{

if(QueueEmpty(Q))

Error("Queue if empty.");

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

}

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

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

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

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

推薦閱讀：

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

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

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