第10章 10.1 栈和队列 · 《算法导论》答案

# 一、概念 ### 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; } ~~~