栈和队列是两种重要的数据结构，栈和队列是特殊的线性表。
1、栈（stack）是限定仅在表的一端进行插入或删除操作的线性表。通常称插入、删除的这一端为栈顶（top），另一端为栈底（bottom）。栈操作的特点是先进后出（后进先出）。
- 栈（顺序栈）的数据结构定义：
//栈的顺序存储表示（顺序栈）
#define STACK_INIT_SIZE 10 // 存储空间初始分配量
#define STACK_INCREMENT 2 // 存储空间分配增量
struct SqStack
{
SElemType *base; // 在栈构造之前和销毁之后，base的值为NULL
SElemType *top; // 栈顶指针
int stacksize; // 当前已分配的存储空间，以元素为单位
};
下图展示了顺序栈中的数据元素和top指针之间的对应关系：
top为栈顶指针，其初始值指向栈底，即top=base。每当插入栈顶元素时，元素数据储存在当前top指针所指位置，然后top指针增加1个位置；删除栈顶元素时，返回数据等于*--top，即指针top减1。因此，非空栈的top指针始终在栈顶元素的下一个位置上。
- 栈（顺序栈）的基本操作
构造一个空栈
void InitStack(SqStack &S)
{
if(!(S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType))))
exit(OVERFLOW); // 存储分配失败
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
}
入栈
// 插入元素e为新的栈顶元素
void Push(SqStack &S,SElemType e)
{
if(S.top-S.base>=S.stacksize) // 栈满，追加存储空间
{
S.base=(SElemType *)realloc(S.base,(S.stacksize+STACK_INCREMENT)*sizeof(SElemType));
if(!S.base)
exit(OVERFLOW); // 存储分配失败
S.top=S.base+S.stacksize;
S.stacksize+=STACK_INCREMENT;
}
*(S.top)++=e;
}
出栈
// 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR
Status Pop(SqStack &S,SElemType &e)
{
if(S.top==S.base)
return ERROR;
e=*--S.top;
return OK;
}
2、队列（queue）是限定在一端（队尾）进行插入，另一端（队头）进行删除的线性表。队列操作的特点是先进先出（后进后出）。
- 链队列 用链表表示的队列简称链队列。其含有指向头结点的头指针和指向尾元素的尾指针。
链队列结构图如下：
结构定义如下：
// 单链队列－－队列的链式存储结构
typedef struct QNode
{
QElemType data;
QNode *next;
}*QueuePtr;
struct LinkQueue
{
QueuePtr front,rear; // 队头、队尾指针
};
主要操作算法：
构造一个空队列Q
void InitQueue(LinkQueue &Q)
{
if(!(Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode))))
exit(OVERFLOW);
Q.front->next=NULL;
}
入队
// 入队，插入元素e为Q的新的队尾元素
void EnQueue(LinkQueue &Q,QElemType e)
{
QueuePtr p;
if(!(p=(QueuePtr)malloc(sizeof(QNode)))) // 存储分配失败
exit(OVERFLOW);
p->data=e;
p->next=NULL;
Q.rear->next=p;
Q.rear=p;
}
出队
// 出队，若队列不空，删除Q的队头元素，用e返回其值，并返回OK，否则返回ERROR
Status DeQueue(LinkQueue &Q,QElemType &e)
{
QueuePtr p;
if(Q.front==Q.rear)
return ERROR;
p=Q.front->next;
e=p->data;
Q.front->next=p->next;
if(Q.rear==p)
Q.rear=Q.front;
free(p);
return OK;
}
- 循环队列
在介绍循环队列前，先了解下顺序队列。顺序队列的结构如下图：
用一组地址连续的存储单元依次存放从队头到队尾的元素。Q.front为指向队头的序号，Q.rear指向队尾。当初始化队列时Q.front=Q.rear=整型0。每当插入新的队尾元素时，“队尾指针”（Q.rear）加 1 ；每当从队头删除元素时，“队头指针” （Q.front）减 1 。因此在非空队列中，队头元素等于 Q[Q.front]，队尾元素的下一个位置为 Q.rear 。
假设，当前队列存储最大空间为6。当队列处于上图的（d）状态是不能再存储新的元素，而此时动态增加存储空间是不合适的，因为队列的实际可用空间并未用满（之前删除队列元素时挪出了新的空间）。一个巧妙的办法是将顺序队列想象成一个环状的空间。
在队尾增加新的元素时有Q.rear = (Q.rear+1)%maxsize。另外为了区分空队列和满队列的判断条件（空队列为Q.front=Q.rear），我们约定当队列“头指针”在“尾指针”下一个位置时，认为队列已满。即当(Q.rear+1)%maxsize等于Q.front时认为队列已满（最后一个存储空间不能存元素）。这样，有一个存储节点是不能存数据的，队列的最大存储元素的个数为 maxsize - 1。
下面是循环队列的存储结构：
// c3-4.h 队列的顺序存储结构(元素出队时不移动元素，只改变队头元素的位置)
#define QUEUE_INIT_SIZE 10 // 队列存储空间的初始分配量
#define QUEUE_INCREMENT 2 // 队列存储空间的分配增量
struct SqQueue2
{
QElemType *base; // 初始化的动态分配存储空间
int front; // 头指针，若队列不空,指向队列头元素
int rear; // 尾指针，若队列不空,指向队列尾元素的下一个位置
int queuesize; // 当前分配的存储容量(以sizeof(QElemType)为单位)
};
主要操作算法：
构造一个空队列Q
void InitQueue(SqQueue2 &Q)
{
if(!(Q.base=(QElemType *)malloc(QUEUE_INIT_SIZE*sizeof(QElemType)))) // 存储分配失败
exit(ERROR);
Q.front=Q.rear=0;
Q.queuesize=QUEUE_INIT_SIZE;
}
入队
// 插入元素e为Q的新的队尾元素
void EnQueue(SqQueue2 &Q,QElemType e)
{
int i;
if((Q.rear+1)%Q.queuesize==Q.front)
{ // 队列满，增加存储单元
Q.base=(QElemType *)realloc(Q.base,(Q.queuesize+QUEUE_INCREMENT)*sizeof(QElemType));
if(!Q.base) // 增加单元失败
exit(ERROR);
if(Q.front>Q.rear) // “头指针”大于“尾指针”，比如front=3 rear=2
{
// 移动高端元素到新的高端
//比如 [102,103,null,4,5,6,7,8,9,10,101,null,null],
//移完后为[102,103,null,null,null,4,5,6,7,8,9,10,101],
for(i=Q.queuesize-1;i>=Q.front;i--)
Q.base[i+QUEUE_INCREMENT]=Q.base[i];
Q.front+=QUEUE_INCREMENT; // 移动队头指针
}
Q.queuesize+=QUEUE_INCREMENT; // 增加队列长度
}
Q.base[Q.rear]=e; // 将e插入队尾
Q.rear=++Q.rear%Q.queuesize; // 移动队尾指针
}
出队
// 若队列不空，则删除Q的队头元素，用e返回其值，并返回OK；否则返回ERROR
Status DeQueue(SqQueue2 &Q,QElemType &e)
{
if(Q.front==Q.rear) // 队列空
return ERROR;
e=Q.base[Q.front]; // 用e返回队头元素
Q.front=++Q.front%Q.queuesize; // 移动队头指针
return OK;
}
- 链队列和循环队列对比：循环队列适合能预估队列长度的情况，这种情况时间效率较高。链队列比较灵活，但每次出队或者入队都需要释放或者申请节点空间，效率较低。
