数据结构------栈和队列

一、特殊线性表——栈
1.栈的逻辑结构
①栈：限定仅在表尾进行插入和删除操作的线性表。
允许插入和删除的一端称为栈顶，另一端称为栈底。
栈的特殊操作：后进先出。
②栈只是对表插入和删除操作的位置进行了限制，并没有限定插入和删除操作进行的时间。
③栈的抽象数据类型定义
ADT Stack
Data
栈中元素具有相同类型及后进先出特性，
相邻元素具有前驱和后继关系
Operation
InitStack
前置条件：栈不存在
输入：无
功能：栈的初始化
输出：无
后置条件：构造一个空栈
DestroyStack
前置条件：栈已存在
输入：无
功能：销毁栈
输出：无
后置条件：释放栈所占用的存储空间
Push
前置条件：栈已存在
输入：元素值x
功能：在栈顶插入一个元素x
输出：如果插入不成功，抛出异常
后置条件：如果插入成功，栈顶增加一个元素
Pop
前置条件：栈已存在
输入：无
功能：删除栈顶元素
输出：如果删除成功，返回被删元素值，否则，抛出异常
后置条件：如果删除成功，栈减少一个元素
GetTop
前置条件：栈已存在
输入:无
功能：读取当前的栈顶元素
输出：若栈不空，返回当前的栈顶元素值
后置条件：栈不变
Empty
前置条件：栈已存在
输入：无
功能：判断栈是否为空
输出：如果栈为空，返回1，否则，返回0
后置条件：栈不变
endADT
2.栈的顺序存储结构及实现
①用数组：
确定用数组的哪一端表示栈底
附设指针top指示栈顶元素在数组中的位置
进栈：top加1
栈空：top=-1
出栈：top减1
栈满：top=MAX_SIZE-1
②顺序栈的实现——入栈
操作接口：bool Empty（）
template
bool seqStsck::Empty()
{
if(top==-1)
return ture;
return false;
}
③取顶栈
操作接口：T GetTop();
template
T seqStack::GetTop()
{
if(Empty())throw"空栈“;
return data[top];
}
④出栈
操作接口：T Pop();
template
T seqStack::Pop()
{
if(top==-1) throw"溢出";
x=data[top];
top–;
return x;
}
⑤两栈共享空间（双端栈）
顺序存储：为每一个栈开辟一个数组空间。
顺序栈单项延伸——使用一个数组来存储栈
栈1为空：top1=-1
栈2为空：top2=Stack_Size
插入，删除。
3、栈的链接存储结构及实现
①插入（入栈）
操作接口：void Push（T x）
template
void LinkStack::Push(T x)
{
s=new Node;
s->data=x;
s->next=top;
top=s;
}
②删除（出栈）
操作接口：T Pop();
template
T LinkStack::Pop()
{
if(top= =NULL)
throw"下溢";
x=top->data;
p=top;
top=top->next;
delete p;
return x;
}
③链栈的析构（链栈的销毁）
二、栈的应用举例——表的式求值
1、中缀表达式求值
①表达式的组成：
操作数
运算符
界限符
②求值过程
设置两个栈
自左向右扫描中缀表达式
③中缀表达式转化为后缀表达式
设置一个运算符栈（从左到右）
遇到数值直接输出
遇到”（“入栈
遇到运算符a，如果栈顶符号的优先级低于a的优先级则入栈，栈顶符号出栈，直到栈顶符号的优先级低于a的优先级，此时a入栈
遇到”）“则栈顶符号出栈，知道”（“
重复以上工作，直到表达式结束。此时将栈里符号全部出栈
④ 后缀表达式求值
三、特殊线性表——队列
1、队列的逻辑结构
队列的操作特性：先进先出（FIFO，LILO）
2、队列的抽象数据类型定义
3、队列的顺序存储结构及实现
①队首元素存放在下标为0的一端
②改进出队的时间性能
设置队头、队尾两个指针
队头指针指向队头元素的前一个位置
队尾指针指向队中最后一个元素
③队空：front==rear
队满：front=rear
队满的条件：（rear+1）mod QueueSize=front