栈和队列（顺序栈、链栈、队列、循环队列、链队列）
栈的定义
定义：栈是限定仅在表尾进行插入和删除操做的线性表。咱们把容许插入和删除的一端称为栈顶，另外一端称为栈底，不含任何数据元素的栈称为空栈。栈又称后进先出(Last In First Out)的线性表，简称LIFO结构。web
栈的插入操做，叫做进栈（Push），也称压栈、入栈。栈的删除操做，叫做出栈（Pop），也有的叫做弹栈。示意图以下：算法
栈的抽象数据类型
栈自己就是一个线性表，因此关于线性表的操做，对栈基本上也是符合的，只是在某些方面会有少量变化，如下是栈的抽象数据类型：编程
ADT 栈（stack） Data 同线性表。元素具备相同的类型，相邻元素具备前驱和后继关系。 Operation InitStack（*S）： 初始化操做，创建一个空栈。 DestroyStack（*S）： 若栈存在，则销毁它。 ClearStack（*S）： 将栈清空。 StackEmpty（S）： 若栈为空，返回true，不然返回false。 GetTop（S，*e）： 若栈存在且非空，用e返回S的栈顶元素。 Push（*S，e）： 若栈S存在，插入新元素e到栈S中并成为栈顶元素。 Pop（*S，*e）： 删除栈S中栈顶元素，并用e返回其值。 StackLength（S）： 返回栈S的元素个数。 endADT
栈的顺序存储结构及实现
栈的顺序存储结构实际上是线性表顺序存储结构的简化，咱们简称为顺序栈。在没有指针的高级程序语言中，咱们使用数组来实现线性表，栈也是一样的道理，不过由于栈后进先出的特色，咱们定义下标为0的一端做为栈底，由于首元素在栈底，变化最小。数组
栈的结构定义以下：数据结构
//SElemType类型根据实际状况而定，这里假设为int typedef int SElemType； typedef struct{ SElemType data[MAXSIZE]; //用于栈顶指针 int top; }SqStack;
压栈和弹栈
-
压栈（入栈）svg
压栈的示意图如上，下面咱们来看下push的代码算法实现：性能
//时间复杂度为O（1） //插入元素e为新的栈顶元素 Status Push(SqStack *S,SElemType e){ //栈满 if(S->top == MAXSIZE - 1){ return ERROR; } //栈顶指针+1 S->top++; //将新插入元素赋值给栈顶空间 S-data[S->top] = e; return OK; }
-
弹栈（出栈）优化
弹栈的示意图如上，下面咱们来看下pop的代码算法实现：spa
//时间复杂度为O（1） //若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；不然返回ERROR Status Push(SqStack *S,SElemType e){ //空栈 if(S->top == -1){ return ERROR; } //将要删除的栈顶元素赋值给e *e = S-data[S->top]; //栈顶指针-1 S->top--; return OK; }
两栈共享空间
栈的顺序存储结构有一个很大的缺陷，就是必须事先肯定数组存储空间大小，万一不够用了，就须要编程手段来扩展数组的容量，很是麻烦。对于一个栈，咱们也只能尽可能考虑周全，设计出合适大小的数组来处理，但对于两个相同类型的栈（前提），咱们却能够作到最大限度地利用其实现开辟的存储空间来进行操做，这就是两栈共享空间。设计
作法以下，数组有两个端点，两个栈有两个栈底，让一个栈的栈底为数组的始端，即下标为0处，另外一个栈为数组的末端，即下标为数组长度n-1处。这样，两个栈若是增长元素，就是两端点向中间延伸。
两栈共享空间的结构的代码以下：
//两栈共享空间结构 typedef struct{ SElemType data[MAXSIZE]; //栈1栈顶指针 int top1; //栈2栈顶指针 int top2; }SqDoubleStack;
两栈共享空间的push方法：
//插入元素e为新的栈顶元素。除了插入元素值外，还须要有一个判断是栈1仍是栈2的栈号stackNumber Status push(SqDoubleStack *S,SElemType e,int stackNumber){ //栈已满，不能再push新元素了 if(S->top1+1 == S->top2){ return ERROR; } //栈1有元素进栈 if(stackNumber == 1){ S->data[++S->top1] = e; } //栈2有元素进栈 else if(stackNumber == 2){ S->data[--S->top2] =e; } return OK; }
两栈共享空间的pop方法：
//若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；不然返回ERROR Status pop(SqDoubleStack *S,SElemType *e,int stackNumber){ if(stackNumber == 1){ if(S->top1 == -1){ //说明栈1已是空栈，溢出 return ERROR; } //将栈1的栈顶元素出栈 *e = S->data[S->top1--]; }else if(stackNumber == 2){ if(S->top2 == MAXSIZE){ //说明栈2已是空栈，溢出 return ERROR; } //将栈2的栈顶元素出栈 *e = S->data[S->top2++]; } return OK; }
事实上，使用这样的数据结构，一般都是当两个栈的空间需求有相反关系时，也就是一个栈增加时另外一个栈在缩短的状况。
栈的链式存储结构及实现
栈的链式存储结构，简称链栈。因为单链表有头指针，而栈顶指针也是必须的，因此比较好的办法是把栈顶放在单链表的头部（以下图）。由于有了栈顶在头部，单链表中比较经常使用的头结点也就失去意义，一般对于链栈来讲，是不须要头结点的。
链栈基本上不存在栈满的状况，除非内存已经没有可使用的空间。但对于空栈来讲，链表原定义是头指针指向空，那么链栈的空其实就是top=NULL。
链栈的结构代码以下：
typedef struct StackNode{ SElemType data; struct StackNode *next; }StackNode,*LinkStackPtr; typedef struct LinkStack{ LinkStackPtr top; int count; }LinkStack;
进栈和出栈
1.进栈（上图左侧）
进栈即push操做，假设元素值为e的新结点为s，top为栈顶指针，代码实现以下：
//插入元素e为新的栈顶元素 Status Push(LinkStack *S,SElemType e){ LinkStackPtr s = (LinkStackPtr)malloc(sizeof(StackNode)); s->data = e; //把当前的栈顶元素赋值给新结点的直接后继 s->next = S->top; //将新结点s赋值给栈顶指针 S->top = s; S->count++; return OK; }
2.出栈（上图右侧）
出栈即pop操做，假设变量p用来存储要删除的栈顶结点，将栈顶指针下移一位，最后释放p，代码实现以下：
//若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；不然返回ERROR
Status Pop(LinkStack *S,SElemType *e){
LinkStackPtr p;
if(StackEmpty(*S)){
return ERROR;
}
*e = S->top->data;
//将栈顶结点赋值给p
p = S->top;
//使得栈顶指针下移一位，指向后一结点
S->top = S->top->next;
free(p);
S->count--;
return OK;
}
若是栈的使用过程当中元素变化不可预料，有时很大，有时很小，那么最好使用链栈；反之，若是它的变化在可控范围以内，最好使用顺序栈。
队列的定义
定义：队列是只容许一端进行插入操做，而在另外一端进行删除操做的线性表。容许插入的一端称为队尾，容许删除的一端称为队头。
队列是**先进先出（First In First Out）**的线性表
假设队列是q={a1，a2，…，an}，那么a1就是队头元素，而an是队尾元素。删除时老是从a1开始，而插入时，列在最后。
队列的抽象数据类型
队列的操做基本和线性表差很少，不一样的就是插入数据只能在队尾，删除数据只能在队头。
ADT 队列（Queue） Data 同线性表。元素具备相同的类型，相邻元素具备前驱和后继关系。 Operation InitQueue（*Q）： 初始化操做，创建一个空队列。 DestroyQueue（*Q）： 若队列Q为空，则销毁它。 ClearQueue（*Q）： 将队列Q清空。 QueueEmpty（Q）： 若队列Q为空，返回true，不然返回false。 GetHead（Q，*e）： 若队列Q存在且非空，用e返回队列Q的队头元素。 EnQueue（*Q，e）： 若队列Q存在，插入新元素e到队列Q中并成为队尾元素。 DeQueue（*Q，*e）： 删除队列Q中队头元素，并用e返回其值。 QueueLength（Q）： 返回队列Q的元素个数。 endADT
队列的顺序存储结构
假设一个队列有n个元素，则顺序存储的队列需创建一个大于n的数组，并把队列的全部元素存储在数组的前n个单元，数组下标为0的一端便是队头。如今咱们来研究一下关于入队和出队的流程：
从上面咱们能够看出根据正常的队列定义，咱们入队的时间复杂度为O（1），可是出队的时间复杂度确实O（n），缘由是队头是下标为0的位置，每一次在队头出队一个元素，后面的元素就要所有向前移一格。这样来看性能是很很差的，有什么方式来优化呢？很简单，就是咱们再也不限制把队列中的全部元素存在数组的前n个单元，具体如何实现呢，咱们来看一下一个新的流程图：
在这里咱们引入了两个指针，分别是front指向队头元素；rear指向队尾的下一个位置。在出队一个元素以后，队头元素后移一位，此时出队的时间复杂度由O（n）优化为了O（1），可是当前这个模式有一个问题，那就是假溢出。为了解决假溢出问题，咱们的循环队列出来了。循环队列的定义很简单：咱们把队列的这种头尾相接的顺序存储结构称为循环队列。
什么是假溢出呢？咱们以上图为例，当前队列的总容量为5，咱们先移除下标0、1中的元素，而后填充下标二、三、 4中的元素，此时队头指针指向下标2，那队尾呢？好像已经越界了，这就是假溢出，由于实际上当前数组中下标0、1仍是能够填充队列元素的。
根据循环队列的定义，咱们把上面出现假溢出的案例的流程图补上：
这样咱们就圆满的解决了假溢出的bug。可是不要高兴太早，新bug来啦，那就是咱们该如何判断队列何时是空，何时是满？
为了解决这个问题，咱们把队列空和队列满的条件作了一点修改：
（1）队列空：front=rear
（2）队列满：若数组中海油一个空闲单元，咱们就认为队列满（见下图）。
在队列满这里，有一点须要注意，那就是rear既可能比front大，也可能比front小，因此尽管它们只相差一个位置时就是满的，但也可能相差整整一圈，假设队列的最大长度为QueueSize，那么队列满的判断条件是：
(rear+1) % QueueSize == front
同时，在计算队列的实际长度时也存在rear > front和rear < front,通用的计算队列长度公式为：
(rear - front + QueueSize) % QueueSize
下面咱们开始介绍循环队列的结构和一些常见操做。
##循环队列的顺序存储结构
//QElemType类型根据实际状况而定，这里假设为int typedef int QElemType; //循环队列的顺序存储结构 typedef struct{ QElemType data[MAXSIZE]; //头指针 int front; //尾指针，若队列不为空，指向队尾元素的下一个位置 int rear; }
循环队列的常见操做
1.初始化
//初始化空队列 Status InitQueue(SqQueue *Q){ Q->front = 0; Q->rear = 0; return OK; }
2.队列长度
//返回队列Q的元素个数 int QueueLength(SqQueue Q){ return (Q.rear-Q.font+MAXSIZE)%MAXSIZE; }
3.入队
//若队列Q未满，则插入元素e为Q新的队尾元素 Status EnQueue(SqQueue *Q,QElemType e){ //队列已满 if((Q->rear+1)%MAXSIZE == Q->front){ return ERROR; } //将元素e赋值给队尾 Q->data[Q->rear] = e; //rear指针后移一位，若到最后则转到数组头部 Q->rear=(Q->rear+1)%MAXSIZE; return OK; }
4.出队
//若队列Q不空，则删除Q中队头元素，用e返回其值 Status EnQueue(SqQueue *Q,QElemType *e){ //队列为空 if(Q->rear == Q->front){ return ERROR; } //将队头元素赋值给e *e = Q->data[Q->front]; //front指针后移一位，若到最后则转到数组头部 Q->front = (Q->front+1)%MAXSIZE; return OK; }
从上面的介绍咱们能够发现，单是顺序存储，若不是循环队列，算法的时间性能不高，但循环队列又面临着数组可能会溢出的问题，因此咱们还须要研究一下队列的链式存储结构。
##队列的链式存储结构及实现
队列的链式存储结构，其实就是单链表，只不过它只能尾进头出而已，咱们把它称为链队列。为了操做上的方便，咱们将队头指针front指向链队列的头结点，将队尾指针rear指向终端结点：
链队列的结构：
//QElemType类型根据实际状况而定，这里假设为int typedef int QElemType; //结点结构 typedef struct QNode{ QElemType data; struct QNode *next; }QNode,*QueuePtr; //队列的链表结构 typedef struct{ QueuePtr front,near; }LinkQueue;
链队列的入队、出队
1.入队
//插入元素e为Q的新的队尾元素 Status EnQueue(LinkQueue *Q,QElemType e){ //s即为新插入的元素e QueuePtr s = (QueuePtr)malloc(sizeof(QNode)); if(!s){ //存储分配失败 exit(OVERFLOW); } s->data = e; s->next = NULL; //把拥有元素e新结点s赋值给原队尾结点的后继 Q->rear->next = s; //把当前的s设置为队尾结点，rear指向s Q->rear = s; return OK; }
2.出队
//若队列不空，删除Q的队头元素，用e返回其值，并返回OK，不然返回ERROR Status DeQueue(LinkQueue *Q,QElemType *e){ QueuePtr p; //此时是空队列 if(Q->front == Q->rear){ return ERROR; } //将欲删除的队头结点暂存给p p = Q->front->next; //将欲删除的队头结点的值赋值给e *e = p->data; //将原队头结点后继p->next赋值给头结点后继 Q->front->next = p->next; if(Q->rear == p){ Q->rear = Q->front; } free(p); return OK; }
对于循环队列和链队列的比较，能够从两方面考虑，时间上，它们的基本操做都是常数时间，即O(1)，不过循环队列是事先申请好空间，使用期间不释放，而对于链队列，每次申请和释放结点存在必定的时间开销；空间上，循环队列必须有一个固定的长度，因此就有了空间浪费的问题，而链队列不存在这个问题，尽管它须要一个指针域，会产生一些空间上的开销，但也能够接受。