# 一、概念 ### 1.棧 （1）棧實現了后進先出操作。 在棧的數組實現中，棧頂指針指向棧頂元素，插入時先修改指針再插入，刪除時先取棧頂元素再修改指針。 當top[S]=0時，棧中空的。 （2）數組棧的結構： int top;//棧頂指針 int *s];//指向棧數組 （3）在棧上實現的操作 STACK-EMPTY(S)//判斷棧是否為空 PUSH(S, x) ? ? ? ? ? ?//把x壓入到棧頂 POP(S) ? ? ? ? ? ? ? ? //取出并返回棧頂元素 ### 2.隊列 （1）隊列實現了先進先出操作。 在隊列的數組實現中，隊列的頭指針指向隊列首元素，刪除時先取隊列首元素再修改指針，隊列的尾指針指向隊尾元素的下一個元素，插入時先插入再修改指針 當top[S]=0時，棧中空的。 （2）數組隊列的結構： int tail;//隊列尾，指向最新進入的元素 int head;//隊列頭，指向最先出的元素 int length;//隊列的長度 int *s;//指向數組隊列 （3）在隊列上實現的操作 ENQUEUE(Q, x) ? ? ? ? ? ?//把x插入到隊列尾 DEQUEUE(Q) ? ? ? ? ? ? ? ?//取出隊列首元素并返回 # 二、代碼 ~~~ //10.1棧和隊列 #include <iostream> #include <stdio.h> #include <string> using namespace std; /*********棧*****************************/ struct stack { int top;//棧頂指針 int *s;//數組 stack(int size):top(0){s = new int[size+1];} // ~stack(){delete []s;} }; void Print(stack S) { int i; //從棧底到棧頂的順序輸出 for(i = 1; i <= S.top; i++) cout<<S.s[i]<<' '; cout<<endl; } //檢查一個棧是否為空 bool Stack_Empty(stack &S) { if(S.top == 0) return true; else return false; } //入棧 void Push(stack &S, int x) { S.top++; S.s[S.top] = x; } //出棧 int Pop(stack &S) { if(Stack_Empty(S)) { cout<<"underflow"<<endl; exit(0); } else { S.top--; return S.s[S.top+1]; } } /*********隊列****************************/ struct queue { int tail;//隊列頭指針 int head;//隊列尾指針 int length;//隊列長度 int *s;//數組 queue(int size):tail(1),head(1),length(size){s = new int[size+1];} }; //從隊列頭到隊列尾輸出 void Print(queue Q) { int i; if(Q.tail >= Q.head) { for(i = Q.head; i < Q.tail;i++) cout<<Q.s[i]<<' '; cout<<endl; } //因為循環的原因，隊列尾可能在隊列頭的前面 else { for(i = Q.head; i <= Q.length; i++) cout<<Q.s[i]<<' '; for(i = 1; i < Q.tail; i++) cout<<Q.s[i]<<' '; cout<<endl; } } //判斷隊列是否為空 bool Queue_Empty(queue Q) { if(Q.tail == Q.head) return 1; return 0; } //入隊列 void Enqueue(queue &Q, int x) { Q.s[Q.tail] = x; if(Q.tail == Q.length) Q.tail = 1; else Q.tail++; } //出隊列 int Dequeue(queue &Q) { int x = Q.s[Q.head]; if(Q.head == Q.length) Q.head = 1; else Q.head++; return x; } ~~~ # 三、練習 10.1-1 4 1 10.1-2 分別用數組的兩端作為兩個棧的起點，向中間擴展，兩個棧中的元素總和不超過n時，兩個棧不會相遇 見[算法導論 10.1-2 用一個數組實現兩個棧](http://blog.csdn.net/mishifangxiangdefeng/article/details/7992950) 10.1-3 3 8 10.1-4 ~~~ //代碼：能處理上溢和下溢的隊列 //入隊列 void Enqueue2(queue &Q, int x) { int t; //上溢 if(Q.tail == Q.length) t = 1; else t= Q.tail+1; if(t == Q.head) { cout<<"error:overflow"<<endl; return; } else { Q.s[Q.tail] = x; Q.tail = t; } } //出隊列 int Dequeue2(queue &Q) { //下溢 if(Q.head == Q.tail) { cout<<"error:underflow"<<endl; return -1; } int x = Q.s[Q.head]; if(Q.head == Q.length) Q.head = 1; else Q.head++; return x; } ~~~ 10.1-5 見[算法導論 10.1-5 雙端隊列](http://blog.csdn.net/mishifangxiangdefeng/article/details/7992971) 10.1-6 入隊列： 如果B棧不為空，依次彈出B棧中的值并壓入A棧。然后把要入隊列的值壓入A棧O(n) 出隊列 ： 如果A棧不為空，依次彈出A棧中的值并壓入B棧，然后將B棧中棧頂位置的值出棧并返回這個值O(n) ~~~ //用兩個棧來模擬一個隊列 //輸出隊列，棧1是從棧底到棧頂，棧2是從棧頂到棧底 void Print(stack S1, stack S2) { int i; for(i = 1; i <= S1.top; i++) cout<<S1.s[i]<<' '; for(i = S2.top; i >= 1; i--) cout<<S2.s[i]<<' '; cout<<endl; } //判斷隊列是否為空 bool Queue_Empty(stack &S1, stack &S2) { if(Stack_Empty(S1)&&Stack_Empty(S2)) return 1; return 0; } //入隊列 void Enqueue(stack &S1, stack &S2, int x) { //如果B棧不為空，依次彈出B棧中的值并壓入A棧 while(!Stack_Empty(S2)) Push(S1, Pop(S2)); //要入隊列的值壓入A棧 Push(S1, x); } //出隊列 int Dequeue(stack &S1, stack &S2) { //如果A棧不為空，依次彈出A棧中的值并壓入B棧 while(!Stack_Empty(S1)) Push(S2, Pop(S1)); //將B棧中棧頂位置的值出棧并返回這個值 return Pop(S2); } ~~~ 10.1-7 入棧： 兩個隊列中，其中一個是空隊列，將值入這個空隊列，然后將另一個非空隊列的值依次取出并加入這個隊列中O(n) 出棧：直接從非空的隊列中取出O(1) ~~~ //用兩個隊列模擬棧 //判斷棧是否為空 bool Stack3_Empty(queue Q1, queue Q2) { if(Queue_Empty(Q1) && Queue_Empty(Q2)) return 1; return 0; } //輸出棧 void Print(queue Q1, queue Q2) { if(!Queue_Empty(Q1)) Print(Q1); if(!Queue_Empty(Q2)) Print(Q2); } //入棧 void Push(queue &Q1, queue &Q2, int x) { //兩個隊列中，其中一個是空隊列 if(Queue_Empty(Q1)) { //將值入這個空隊列 Enqueue(Q1, x); //將另一個非空隊列的值依次取出并加入這個隊列中 while(!Queue_Empty(Q2)) Enqueue(Q1, Dequeue(Q2)); } else//同理 { Enqueue(Q2, x); while(!Queue_Empty(Q1)) Enqueue(Q2, Dequeue(Q1)); } } //出棧 int Pop(queue &Q1, queue &Q2) { //直接從非空的隊列中取出 if(!Queue_Empty(Q1)) return Dequeue(Q1); if(!Queue_Empty(Q2)) return Dequeue(Q2); cout<<"error:underflow"<<endl; return -1; } ~~~