資料結構 ~ 兩個棧實現佇列

NO IMAGE

回顧前兩篇文章

1> 由前2篇文章,我們知道棧的特性是:先進後出
佇列的特性是:先進先出

用兩個棧去實現一個佇列,也就是我們要用兩個”先進後出“ 去實現一個“先進先出”,我們不妨假設一個佇列有2個元素,這2個元素就是2個棧stack1和stack2。 我們通過一個具體的例子來分析往佇列裡插入和刪除元素的過程:

首先插入一個元素A, 我們不妨把它插入棧1即stack1,此時stack1裡面元素有{A},棧2即stack2為空,再壓入2個元素B和C,還是插入stack1,此時stack1中的元素有{A,B,C},其中C位於棧頂,而stack2仍然為空

這時候我們試著從佇列裡刪除一個元素,按著佇列先入先出的原則,由於A是最先插入的,最先被刪除的應該是A,元素A儲存在stack1,但是並不是位於棧頂,因此不能直接刪除,注意到stack2一直沒有被使用過,現在是時候讓stack2發揮作用了,如果我們把stack1中的元素逐個彈出並壓入到stack2,則元素在stack2中的順序剛好跟原來的順序相反,因此stack2中的元素是{C,B,A},stack1為空,A位於stack2的棧頂,彈出stack2中的棧頂元素,即滿足了對佇列刪除A操作的要求。

如果我們還想繼續刪除佇列的頭部怎麼辦,剩下的兩個元素是B ,C,由於B比C先入,因此對於佇列來說應該先刪除B,剛剛好B位於stack2的棧頂,滿足要求,彈出B後,stack2只含有元素{C}。

從上面的分析我們可以總結出刪除一個元素的步驟是:當stack2不為空時,在stack2棧頂的元素是先進入佇列的沒可以彈出,當stack2為空時,我們把stack1中的元素逐個的彈出並壓入stack2,由於進入佇列的元素被壓入stack1的棧底。經過彈出和壓入操作之後就位於stack2的頂端,又可以被直接彈出

接下來我們再考慮插入一個元素D,我們還是把它壓入stack1,這樣會不會有問題呢?我們考慮下一次刪除佇列的頭部stack2不為空,直接彈出他的棧頂元素C,而C確實比D先進入佇列,應該在D之前刪除,因此不會出現矛盾。

綜合上訴總結:

入隊:

當stack1和stack2都為空時,直接入隊stack1
當stack1為空,stack2不為空時,把stack2的元素都倒回stack1,然後再入隊stack1
出隊:

當stack2不為空時,直接出隊stack2
當stack2為空且stack1不為空時,把stack1的元素都倒進stack2,然後出隊stack2

程式碼:

typedef struct {  
stack<int>s1;  //負責入佇列  
stack<int>s2;  //負責出佇列  
}SQueue;  
//判斷佇列是否為空  
bool IsEmpty(SQueue &q) {  
if ((q.s1.empty()) && (q.s2.empty())) {  
return true;  
}  
return false;  
}  
// 入佇列  
void EnQueue(SQueue &q, ElemType e) {  
q.s1.push(e);  
}  
//  佇列大小  
int GetQueueSize(SQueue &q) {  
return q.s1.size()   q.s2.size();  
}  
//出佇列  
void DeQueue(SQueue &q) {  
if (q.s2.empty()) {  
while (!q.s1.empty()) {  
q.s2.push(q.s1.top());  
q.s1.pop();  
}  
}  
if (!q.s2.empty()) {  //隊空  
q.s2.pop();  //出佇列  
}  
}  
//  取隊首先元素  
int GetFront(SQueue &q) {  
if (q.s2.empty()) {  
while (!q.s1.empty()) {  
q.s2.push(q.s1.top());  
q.s1.pop();  
}  
}  
if (q.s2.empty()) {  //隊空  
throw;  
}  
return q.s2.top();  
} 

以上,歡迎留言交流~