第10章 10.1 栈和队列
最后更新于：2022-04-01 07:35:24
# 一、概念
### 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;
}
~~~