3.1 栈
3.1.1 栈的逻辑结构
1、栈：栈是限定仅在表尾进行插入和删除操作的线性表，允许插入和删除的一端称为栈顶，另一端称为栈底，不含任何数据元素的栈称为空栈。
栈中元素除了具有线性关系外，还具有后进先出的特性。
2、栈的抽象数据类型定义
虽然对插入和删除操作的位置限制减少了栈操作的灵活性，但同时也是的栈的操作更有效更容易实现。
ADT Stack
Data 栈中元素具有相同类型及后进先出的特性，相邻元素具有前驱和后继关系
Operation
InitStack 功能：栈的初始化 后置条件：构造一个空栈
DestroyStack 销毁栈 释放栈所占用的存储空间
Push 入栈操作，在栈顶插入一个元素x 若插入成功，则栈顶增加一个元素
Pop 出栈操作，删除栈顶元素 若删除成功，则栈顶减少一个元素
GetTop 取栈顶元素，读取当前的栈顶元素 栈不变
Empty 判空操作 栈不变
endADT
3.1.2 栈的顺序存储结构及实现
1、栈的顺序存储结构——顺序栈
顺序栈：栈的顺序存储结构。
需要确定的是用数组的哪一端表示栈底，通常把数组中下标为0的一端作为栈底，同时指针top指示栈顶元素在数组中的位置。
数组长度为StackSize,栈空时栈顶指针top=-1；栈满时栈顶指针top=StackSize-1.入栈时，栈顶元素top加1；出栈时栈顶指针top减去1.
2、顺序栈的实现
其抽象数据类型定义在顺序栈存储结构下在c++中的类实现
const int StackSize=10;
template<class T>
class SeqStack
{
public:
SeqStack(){top=NULL;}
~SeqStack(){}
void Push(T x);
T Pop();
T GetTop(){if(top!=NULL)return top->data;}
int Empty(){top==-1?return data[top];}
private:
T data[StackSize];
int top;
}
实质是单链表基本操作简化，除析构函数外，算法的时间复杂度均为O（1）。
（1） 栈的初始化
SeqStack<T>::SeqStack()
{
top=-1;
}
（2）入栈操作
template<class T>
void SeqStack<T>::Push(T x)
{
if(top==StackSize-1)throw"上溢";
top++;
data[top]=x;
}
（3） 出栈操作
template<class T>
T SeqStack<T>::Pop()
{
T x;
if(top==-1)throw"下溢";
x==data[top--];
return x;
}
（4）取栈顶元素
template<class T>
T SeqStack<T>::GetTop()
{
if(top!=-1)
return data[top];
}
（5）判空操作
template<class T>
int SeqStack<T>::Empty()
{
if(top==-1)return 1;
else return 0;
}
3、两栈共享空间
使用一个数组来存储两个栈，让一个的栈底为该素组的始端，另一个栈的栈底为该数组的末端，每个栈从各自的端点向中间延伸，
两栈共用一个数组空间的抽象数据类型为：
ADT BothStack
Data
Operation
BothStack 功能：创建两栈共享的数组空间 后置条件：两栈均为空，top1=-1，top2=StackSize
~BothStack 销毁两栈共享的数组空间 将两栈的数组空间释放
GetTop 读取栈i当前的栈顶元素 两栈均不变
Push 入栈操作，在栈i插入一个元素x 若插入成功，则栈i插入了一个栈顶元素
POP 出栈操作，在栈i中删除栈顶元素 若删除成功，则栈i中删除了栈顶元素
Empty 判空操作，判断栈i是否为空栈 两栈均不变
endADT
在C++中的类声明
const int StackSize=100;
template<class T>
class BothStack
{
public:
BothStack(){top1=-1；top2=StackSize;}
~BothStack(){}
void Push(int i;T x);
T Pop(int i);
T GetTop(int i);
int Empty(int i);
private:
T data[StackSize];
int top1,top2;
};
(1)入栈操作
栈1的栈顶元素和栈2的栈顶元素位于数组中的相邻位置，top1=top2-1（top2=top1+1），当新元素插入栈2时，栈顶指针top2不是加1而是减去1
template<class T>
void BothStack<T>::void Push(int i;T x);
{
if(top1==top2-1) throw"上溢";
if(i==1)data[++top1]=x;
if(i==2)data[--top2]=x;
}
（2）出栈操作
template<class T>
void BothStack<T>::POP(int i);
{
if（ i==1）
{
if（top==-1）throw“下溢”；
return data[top1--];
)
if(i==2)
{
if(top2==StackSize)throw"下溢";
return data[top2++];
}
}
3.1.3 栈的链接存储结构及实现
1、栈的链接存储结构——链栈
链栈：栈的链接存储结构。链栈用单链表表示，因此其结点结构与单链表的结点结构相同。
2、链栈的实现
template<class T>
class LinkStack
{
public:
LinkStack(){top=NULL;}
~LinkStack(){}
void Push(T x);
T Pop();
T GetTop(){if(top!=NULL)return top->data;}
int Empty(){top==NULL?return 1：return 0;}
private:
Node<T>*top;
}
其基本操作本质是单链表基本操作简表且除析构函数外算法时间复杂度为O（1）。
（1）构造函数
将栈顶指针top置为空。
（2）入栈操作 Push
template<T>
void LinkStack<T>::Push(T x)
{
s=new Node;s->data=x;
s->next=top;top=s;
}
(3)出栈操作Pop
template<class T>
T LinkStack<T>::Pop()
{
if(top==NULL)throw"下溢";
x=top->data;p=top;
top=top->next;
delete p;
return x;
}
(4)取栈顶元素
返回栈顶指针top所指结点的数据域.
(5)判空操作
判断top==NULL是否成立，成立栈为空，返回1；不成立栈非空，返回0.
(6)析构函数
链栈的析构函数需要将链栈中所有节点的存储空间释放。
3.1.4 顺序栈和链栈的比较
它们所有基本操作算法都只需要常数时间，可比较的是空间性能。
初始时，顺序栈必须确定一个固定的长度，所以有存储元素个数的限制和空间浪费问题。链栈没有栈满的问题，只有当内存没有可用空间时才会出现栈满，但是每个元素都需要一个指针域，从而产生结构性开销。
当栈满的使用过程中元素个数变化较大时，用链栈最合适；反之采用顺序表。
3.2 队列
1、队列：只允许在一端进行插入操作，在另一端进行删除操作的线性表。
队尾：允许插入的一端。
队头：允许删除的一端。
具有先进先出的特性。
2、队列的抽象数据类型定义
ADT Queue
Data
Operation
InitQueue 功能：初始化队列 后置条件：创建一个空队列
DestroyQueue 销毁队列 释放队列所占用的存储空间
EnQueue 入队操作 若插入成功，队尾增加一个元素
DeQueue 出队操作 若删除成功，队头减少一个元素
GetQueue 读取队头元素 队列不变
Empty 判空操作 队列不变
endADT
3.2.2 队列的顺序存储结构及实现
1、队列的顺序存储结构——循环队列
约定：队头指针front指向队头元素的前一个位置 ，队尾指针rear指向队尾元素。
随着队列的插入和删除操作的进行，整个队列向数组中下标较大的位置移过去，从而产生了队列的“单向移动性”。当元素被插入到数组中下标最大的位置上之后，队列的空间就用尽了，尽管此时数组的低端还有空闲空间，这种现象叫做“假溢出”。
解决假溢出的方法是将存储队列的数组看成是头尾相接的循环结构，即允许队列直接从数组中下标最大的位置延续到下标最小的位置。
队列中头尾相接的顺序存储结构称为循环队列。
2、循环队列的实现
在C++中的模板机制
const int QueueSize=100;
template<class T>
class CirQueue
{
public:
CirQueue();{front=rear=QueueSize-1;}
~ CirQueue ();{}
void EnQueue(T x);
T DeQueue();
GetQueue();
int Empty();{front=rear?return 1:return 0:}
private:
T data[QueueSize];
int front,rear;
}
(1)构造函数
将队头指针和队尾指针同时指向数组的某一个位置，一般是数组的高端，即rear=front=QueueSize-1.
(2)入队操作 EnQueue
template<class T>
void CirQueue<T>::EnQueue(T x)
{
if((rear+1)%QueueSize==front) throw"上溢";
rear=(rear+1)%QueueSize;
data[rear]=x;
}
(3)出队操作DeQueue
template<class T>
T CirQueue<T>::DeQueue()
{
if(rear=front) throw"下溢";
front=(front+1)%QueueSize;
return data[front]；
}
(4)读取队头元素GetQueue
template<class T>
T CirQueue<T>::GetQueue()
{
if(rear=front) throw"下溢";
i=(front+1)%QueueSize;
return data[i]；
}
(5) 判空操作
判断front==rear是否成立，成立则队列为空，返回1；不成立队列非空，返回0.
3.2.3 队列的链接存储结构及实现
1、队列的链接存储结构——链队列
链队列：队列的链接存储结构。
2、链队列的实现
在C++的模板机制
template<class T>
class LinkQueue
{
public:
LinkQueue ();
~ LinkQueue ();
void EnQueue(T x);
T DeQueue();
T GetQueue();
int Empty();{front==rear?return1:return 0;}
private:
Node<T> *front,*rear;
};
(1)构造函数LinkQueue
template<class T>
LinkQueue<T>::LinkQueue()
{
s=new Node<T>;
s->next=NULL;
front=rear=s;
}
(2)入队操作EnQueue
template<class T>
void LinkQueue<T>::EnQueue(T x)
{
s=new Node<T>;
s->data=x;
s->next=NULL;
rear->next=s;
rear=s;
}
(3)出队操作DeQueue
template<class T>
T LinkQueue<T>::DeQueue()
{
if(rear=front)throw"下溢";
p=front->next;
x=p->data;
front->next=p->next;
if(p->next=NULL)rear=front;
delete p;
return x;
}
(4)取队头元素
template<class T>
T LinkQueue<T>::GetQueue()
{
if(front!=rear)
return front->next->data;
}
(5)判空操作
template<class T>
int LinkQueue<T>::Empty()
{
if(front==rear)return 1;
else return 0;
}
(6)析构函数
template<class T>
LinkQueue<T>::~LinkQueue()
{
Node<T> *p=NULL;
while(front!=NULL)
{
p=front->next;
delete front;
front=p;
}
}
本章总结
3.2.4 循环队列和链队列的比较
循环队列不能像顺序栈那样共享空间，通常不能在一个数组中存储两个循环队列。
习题
1、设有一个空栈，栈顶指针为1000H,每个元素需要一个单位的存储空间，则push,push,pop,push,pop,push,push后，栈顶指针为（1003H）。
2、栈结构通常采用的两种结构是（顺序存储结构和链式存储结构），其判定栈空的条件分别是（top=-1和top=NULL），判定栈满条件分别是（top等于数组的长度和内存无可用空间）。
3、（栈）可作为实现递归函数调用的一种数据结构。
4、表达式a*(b+c)-d的后缀表达式是（abc+*d-）
5、栈和队列是两种特殊的线性表，栈的操作特性是（后进先出），队列的操作特性（先进后出），栈和队列的主要区别是（对插入和删除操作限定的位置不同）。
6、循环队列的引入是为了克服（假溢出）。
7、数组Q[n]用来表示一个循环队列，front为队头元素的前一个位置，rear是队尾元素的位置，计算队列中元素个数的公式为(（rear-front+n）%n)
8、用循环链表表示的队列长度为n,若只设头指针，则出队和入队的时间复杂度分别是（O(1),O(n)）
