栈是限定仅在表尾进行插入和删除操作的线性表。
队列是只允许在一端进行插入操作、而在另一端进行删除操作的线性表。

一、栈

1.1 什么是栈？

栈(stack)是限定仅在表尾进行插入和删除操作的线性表。

我们把允许插入和删除的一端称为栈顶(top)，另一端称为栈底(bottom)，不含任何数据元素的栈称为空栈。栈又称为后进先出(LastInFirstOut)的线性表，简称LIFO结构。

定义中说是在线性表的表尾进行插入和删除操作，这里表尾是指栈顶，而不是栈底。

栈的插入操作，叫作进栈，也称压栈(push)、入栈。
栈的删除操作，叫作出栈，也有的叫作弹栈(pop)。

ADT 栈(stack)
Data
	同线性表。元素具有相同的类型，相邻元素具有前驱和后继关系。
Operation
	InitStack(*S)：初始化操作，建立一个空栈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

因其数据结构与线性表一致，因此也可用顺序存储和链式存储两种方式进行实现。

1.2 栈的顺序存储结构及实现

1.2.1 栈的顺序存储结构

既然说栈是线性表的一种特例，那么只需将数组特殊化即可用于实现栈，即将下标为0一端作为栈底，因为首元素都存在栈底，变化最小。
除此之外，我们还需要声明一个栈顶top元素，用于标识栈顶元素在数组中的位置。
top可以增大，减小，但是需要在栈的特定范围内，不能超出，当栈中有一个元素时，top为0，则栈为空时，top为-1。
因此经常将栈空的条件设置为：top == -1。

栈的结构定义：

typdef int SElemType;    /*SElemType 类型根据实际情况而定，这里假设为int*/
typdef struct
{
	SElemType data[MAXSIZE];
	int top;    /*用于栈顶指针*/
}SqStack;

1.2.2 栈的顺序存储结构——进栈操作

时间复杂度：没有涉及循环，O(1)

/*插入元素e为新的栈顶元素*/
Status Push(SqStack *S, SElemType e)
{
	if(S->top == MAXSIZE - 1)  /*栈满*/
	{
		return ERROR;	
	}
	S->top++;    /*栈顶指针加一*/
	S->data[S->top] = e;    /*将新插入的指针赋值给栈顶空间*/
	return OK;	
}

1.2.3 栈的顺序存储结构--出栈操作

时间复杂度：没有涉及循环，O(1)

/*若栈不为空，则删除S的栈顶指针所指的元素，并用e返回其值，将top指针下移一位，并返回成功，否则返回失败。*/
Status Pop(SqStack *S, SElemType *e)
{
	if(S->top == -1)
		return ERROR;
	*e = S->data[S->top];    /*将要删除的元素赋值给e*/
	S->top--;    /*栈顶指针减一视为删除栈顶元素，因下次插入会直接覆盖。*/
	return OK;
}

1.2.4 两栈共享空间

为了提升数组的利用率，减少栈帧溢出的可能性，我们可以假设两个栈共用同一个大的数组，两头作为两个栈的栈顶，依次向另一端插入作为栈顶。
我们的做法如图，数组有两个端点，两个栈有两个栈底，让一个栈的栈底为数组的始端，即下标为0处，另一个栈为栈的末端，即下标为数组长度n-1处。这样，两个栈如果增加元素，就是两端点向中间延伸。

其实关键思路是:它们是在数组的两端，向中间靠拢。top1和top2是栈1和栈2的栈顶指针，可以想象，只要它们俩不见面，两个栈就可以一直使用。

栈1为空的条件：top1 = -1
栈2为空的条件：top2 = n
栈1为满的条件：top1 + 1 = top2
栈2为满的条件：top2 - 1 = top1
整合可得栈1，栈2为满的条件：top1+1=top2

/*两栈共享空间结构*/
typedef struct
{
	SElemType data[MAXSIZE];
	int top1;  /*栈1的栈顶指针*/
	int top2;  /*栈2的栈顶指针*/
}SqDoubleStack;

对于两栈共享空间的 push 方法，我们除了要插入元素值参数外，还需要有一个判断是栈1还是栈2的栈号参数stackNumber。插入元素的代码如下:

/*插入元素e为新的栈顶元素*/
Status Push(SqDoubleStack *S, SElemType e, int stackNumber)
{
	if(s->top1+1 == s->top2)    /*栈已满，不能再push新元素了*/
		return ERROR;
	if(stackNumber == 1)  /*栈1有元素进栈*/
		S->data[++S->top1] = e; /*若栈1则先进行top1++,在给数组元素赋值*/
	else if(stackNumber == 2)  /*栈2有元素进栈*/
		S->data[--S->top2] = 2; /*若栈2则先进行top1++,在给数组元素赋值*/
		return OK;
}

对于两栈共享空间的 pop方法，参数就只是判断栈1栈2的参数stackNumber。

/*若栈不空则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR*/
Status pop(SqDoubleStack *S, SElemType *e, int stackNumber)
{
	if(stackNumber == 1)
	{
		if(S->top1 == -1)
			return ERROR; 
		*e = S->data[S->top1--];
	}
	else if(stackNumber == 2)
	{
		if(S->top2 == MAXSIZE)
			return ERROR; 
		*e = S->data[S->top2++];
	}
	return OK;
}

事实上，使用这样的数据结构，通常都是当两个栈的空间需求有相反关系时，也就是一个栈增长时另一个栈在缩短的情况。就像买卖股票一样，你买入时，一定是有一个你不知道的人在做卖出操作。有人赚钱，就一定是有人赔钱。这样使用两栈共享空间存储方法才有比较大的意义。否则两个栈都在不停地增长，那很快就会因栈满而溢出了。
当然使用双栈共享空间的结构前提是两个栈的数据类型要相同。

1.3 栈的链式存储结构及实现

1.3.1 栈的链式存储结构

栈的链式存储结构，简称为链栈。
由于单链表有头指针，而栈顶指针也是必须的，所以可以让二者合一，所以一般将链表头部作为栈顶。对链栈来说是不需要头结点的。

对于链栈来说，基本不存在栈满的情况，除非内存已经没有可以使用的空间，如果真的发生，那此时的计算机操作系统已经面临死机崩溃的情况，而不是这个链栈是否溢出的问题。
对于空栈来说，链表原本定义的头指针是指向空，即top=NULL。

typedef struct StackNode
{
	SElemType data;
	struct StackNode *next;
}StackNode,*LinkStackPtr;

typedef struct LinkStack
{
	LinkStackPtr top;
	int count;
}LinkStack;

链栈的操作绝大部分都和单链表类似，只是在插入和删除特殊一些。

1.3.2 栈的链式存储结构--进栈操作

对于链栈的进栈 push 操作，假设元素值为e的新结点是s，top 为栈顶指针，示意图如图所示代码如下。

/*插入元素e为新的栈顶元素*/
Status Push(LinkStack *S, SElemType e)
{
	LinkStackPtr s= (LinkStaclPtr) malloc (sizeof(StackNode));
	s->data=e;
	s->next=S->top;  /*把当前的栈顶元素赋值给新结点的直接后继*/
	S->top=s;
	S->count++;
	return OK;
}

1.3.3 栈的链式存储结构——出栈操作

至于链栈的出栈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 = S->top;
	S->top=S->top->next;
	free(p)
	S->count--;
	return OK;
}

链栈的进栈 push和出栈pop操作都很简单，没有任何循环操作，时间复杂度均为O(1)
如果栈的使用过程中元素变化不可预料，有时很小，有时非常大，那么最好是用链栈，反之，如果它的变化在可控范围内，建议使用顺序栈会更好一些。

1.4 栈的应用——递归

示例：斐波那契数列

int main()
{
	int i;
	int a[40];
	a[0] = 0;
	a[1] = 1;
	printf("%d ",a[0]);
	printf("%d ",a[1]);
	for(i=2;i<40;1++)
	{
		a[i] = a[i-1]+ a[i-2];
		printf("%d ",a[i]);
	}
	return 0
}

递归实现：

/* 斐波那契数列递归函数 */
int Fbi(int i )
{
	if(i < 2)
		return i == 0 ? 0 : 1;
	return Fbi(i-1) + Fbi(i-2);/*这里Fbi就是函数自己，它在调用自己*/
}

int main()
{
	int i;
	for(int i = 0; i < 40; i++)
		printf("%d ",Fbi(i));
	return 0;
}

1.4.1 递归定义

在高级语言中，调用自己和其他函数并没有本质的不同。我们把一个直接调用自已或通过一系列的调用语句间接地调用自己的函数，称做递归函数。
当然，写递归程序最怕就是陷入永不结束的无穷递归中，所以，每个递归定义必须至少有一个条件，满足时递归不再进行，即不再引用自身而是返回值退出。比如刚才的例子，总有一次递归会使得i<2 的，这样就可以执行return i的语句而不用继续递归了。
对比了两种实现斐波那契为代码。迭代和递归的区别是:迭代使用的是循环结简洁、更容易让人理构，递归使用的是选择结构。递归能使程序的结构更清晰、更解，从而减少读懂代码的时间但是大量的递归调用会建立函类的副本，会耗费大量因此我们应该视不同的时间和内存。迭代则不需要复调用函数和占用额外的内存情况选择不同的代码实现方式。

1.5 栈的应用——四则运算表达式求值

1.5.1 后缀(逆波兰)表示法定义

例如：9+(3-1)*3+10/2，用后缀表达式表示为：9 3 1 - 3 * + 10 2 / +，叫后缀的原因在于所有的运算符号都是在要运算数字的后面出现。

1.5.2 后缀表达式的运算结果

算式：9 3 1 - 3 * + 10 2 / +
规则：从左到右遍历表达式的每个数字和符号，遇到是数字就进栈，遇到是符号，就将处于栈顶两个数字出栈，进行运算，运算结果进栈，一直到最终获得结果。
流程：

初始化一个空栈。此栈用来对要运算的数字进出使用。
后缀表达式中前三个都是数字，所以 9、3、1进栈。
接下来是“ - ”，所以将栈中的1出栈作为减数，3 出栈作为被减数，并运算 3-1得到 2，再将2进栈。
接着是数字3进栈。
后面是“ * ”也就意味着栈中3和2出栈，2与3相乘，得到6，并将6进栈。
下面是“ + ”，所以栈中6和9出栈，9与6相加，得到15，将15进栈。
接着是10与2两数字进栈。
接下来是符号“/”，因此，栈顶的2与10出栈，10与2相除，得到5、将5进栈。
最后一个是符号“+”，所以15与5出栈并相加，得到20，将20进栈。
结果是 20出栈，栈变为空。

1.5.3 中缀表达式转后缀表达式

我们把平时所用的标准四则运算表达式，即“9+(3-1)x3+10-2”叫做中缀表达式。因为所有的运算符号都在两数字的中间，现在我们的问题就是中缀到后缀的转化。

规则:从左到右遍历中缀表达式的每个数字和符号，若是数字就输出，即成为后缀表达式的一部分;若是符号，则判断其与栈顶符号的优先级，是右括号或优先级低于栈顶符号(乘除优先加减)则栈顶元素依次出栈并输出，并将当前符号进栈，一直到最终输出后缀表达式为止。

流程：

初始化一空栈，用来对符号进出栈使用。
第一个字符是数字9，输出9，后面是符号“+”，进栈。
第三个字符是“("，依然是符号，因其只是左括号，还未配对，故进。
第四个字符是数字3，输出，总表达式为93，接着是“-”进栈。
接下来是数字1，输出，总表达式为9 3 1，后面是符号“)”，此时，我们需要去匹配此前的“(”，所以栈顶依次出栈，并输出，直到“(”出栈为止。此时左括号上方只有“-”，因此输出“-”。总的输出表达式为 9 3 1 -。
接着是数字3，输出，总的表达式为931-3。紧接着是符号“x”，因为此时的栈顶符号为“+”号，优先级低于“x”，因此不输出，“ * ”进栈。
之后是符号“+”，此时当前栈顶元素“ * ”比这个“+”的优先级高，因此栈中元素出栈并输出(没有比“+”号更低的优先级，所以全部出栈)，总输出表达式为9 3 1 - 3 * +。然后将当前这个符号“+”进栈。也就是说，前6张图的栈底的“+”是指中缀表达式中开头的9后面那个“+”，而下图中的栈底(也是栈顶)的“+”是指“9 + ( 3 - 1 ) x 3 +”中的最后一个“+”。
紧接着数字10，输出，总表达式变为9 3 1 - 3 * + 10。后是符号“÷”，所以“/”进栈。如图所示。
最后一个数字2，输出，总的表达式为`9 3 1 - 3 * + 10 2。
因已经到最后，所以将栈中符号全部出栈并输出。最终输出的后缀表达式结果为9 3 1 - 3 * + 10 2 / +。
将中缀表达式转化为后缀表达式(栈用来进出运算的符号)。
将后缀表达式进行运算得出结果(栈用来进出运算的数字)。

二、队列

2.1 队列的定义

队列(queue)是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。

队列是一种先进先出(First In First Out)的线性表，简称 FIFO。允许插入的一端称为队尾，允许删除的一端称为队头。假设队列是q=(a1，a2，…，an)，那么a1就是队头元素，而 an是队尾元素。这样我们就可以删除时，总是从a1开始，而插入时，列在最后。这也比较符合我们通常生活中的习惯，排在第一个的优先出列，最后来的当然排在队伍最后。

2.2 队列的抽象数据类型

ADT 队列 (Queue)
Data
	同线性表。元素具有相同的类型，香菱元素具有前驱和后继关系。
Operation
	InitQueue(*Q):初始化操作，建立一个空队列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):删除队列中队头元素，并用e返回其值。
	QueueLength(Q):返回队列Q的元素个

2.3 循环队列（线性存储）

线性表有顺序存储和链式存储，栈是线性表，所以有这两种存储方式。同样，队列作为一种特殊的线性表，也同样存在这两种存储方式。我们先来看队列的顺序存储结构。

2.3.1 队列顺序存储的不足

我们假设一个队列有n个元素，则顺序存储的队列需建立一个大于n的数组，并把队列的所有元素存储在数组的前n个单元，数组下标为0的一端即是队头。所谓的入队列操作，其实就是在队尾追加一个元素，不需要移动任何元素，因此时间复杂度O(1)。

与栈不同的是，队列元素的出列是在队头，即下标为0的位置，那也就意味着队列中的所有元素都得向前移动，以保证队列的队头，也就是下标为0的位置不为空，此时时间复杂度为 0(n)，如图所示。

优化：队头不固定在0位置，为了避免当只有一个元素时，队头和队尾重合使得处理变得麻烦，所以引入两个指针，front指针指向队头元素，rear指针指向队尾元素的下一个元素，这样当front等于rear时，此队列为空。
存在的问题：由于频繁入队出队，导致队尾可能会越界，但前面空间还有空闲，这种现象称为“假溢出”。

2.3.2 循环队列定义

所以解决假溢出的办法就是后面满了，就再从头开始，也就是头尾相接的循环。
我们把队列的这种头尾相接的顺序存储结构称为循环队列。
例如，rear 可以改为指向下标为0的位置，这样就不会造成指针指向不明的问题了。

接着入队 a6，将它放置于下标为0处，rear 指针指向下标为1处，如图所示。若再入队 a7，则rear 指针就与front 指针重合，同时指向下标为2的位置。

此时问题又出来了，我们刚才说，空队列时，ont等于rear，现在当队列满时，也是 font等于rear，那么如何判断此时的队列究竟是空还是满呢?
办法一是设置一个标志变量ag，当font==rear，且flag=0时为队列空当 front==rear，且fag=1时为队列满。
办法二是当队列空时，条件就是font=rear，当队列满时，我们修改其条件，保留一个元素空间。也就是说，队列满时，数组中还有一个空闲单元。我们就认为此队列已经满了。

我们重点来讨论第二种方法，由于rear可能比front大，也可能比font小，所以尽管它们只相差一个位置时就是满的情况，但也可能是相差整整一圈。所以若队列的最大尺寸为 QueueSize，那么队列满的条件是(rear+1)%QueueSize==front(取模“%”的目的就是为了整合rear与front大小为一个问题)。比如上面这个例子,QueueSize=5，图中front=0，而rear=4,(4+1)%5=0，所以此时队列满。再比如front=2而rear=1。(1+1)%5=2，所以此时队列也是满的。而对于front=2而rear=0，(0+1)%5=1，1≠2，所以此时队列并没有满。
另外，当rear>front 时，此时队列的长度为rear-front。但当rear<front 时，队列长度分为两段，一段是 QueueSize-front，另一段是0+rear，加在一起，队列长度为rear-front+QueueSize。因此通用的计算队列长度公式为:
(rear-front + QueueSize)%QueueSize

typdef int QElemType;    /*QElemType类型根据实际情况而定，这里假设为int*/
/*循环队列的顺序存储结构*/
typedef struct
{
	QElemType data[MAXSIZE];
	int front;    /*头指针*/
	int rear;    /*尾指针，若队列不空，指向队列尾元素的下个位置*/
}SqQueue;

循环队列的初始化代码如下：

/* 初始化一个空队列Q */
Status InitQueue(SqQueue *e)
{
	Q->front = 0;
	Q->rear = 0;
	return OK;
}

循环队列求队列长度代码：

/*返回Q的元素个数，也就是队列的当前长度*/
int QueueLength(SqQueue Q)
{
	return (Q.rear - Q.front + MAXSIZE) % MAXSIZE;
}

循环队列的入队列操作代码：

Status EnQueue(SqQueue *Q, QElemType e)
{
	if ((Q->rear + 1) % MAXSIZE == Q->front)  /*队列满的判断*/
		return ERROR;
	Q->data[Q->rear]==e;    /*将元素e赋值给队尾*/
	Q->rear = (Q->rear+1)%MAXSIZE;/*rear 指针向后移一位置*/
	return OK;
}

循环队列的操作代码如下：

/*若队列的不空，则删除Q中队头元素，用e返回其值*/
Status DeQueue(SqQueue *Q, QElemType *e)
{
	if (Q->front == Q->rear) /*队列为空的判断*/
		return ERROR;
	*e = Q->data[front];    /*将队头元素赋值给e */
	Q->front = (Q->front+1)%MAXSIZE;  /*front指针向后移一位，若到最后则转移到数组0位*/	
}

2.4 队列的链式存储

队列的链式存储结构，其实就是线性表的单链表，只不过它只能尾进头出而已，我们把它简称为链队列。为了操作上的方便，我们将队头指针指向链队列的头结点，而队尾指针指向终端节点。

空队列时，front和rear都指向头结点

typedef int QElemType;    /* QElemtype 类型根据实际情况而定，这里假设为int */

typedef struct QNode  /*结点结构*/
{
	QElemType data;
	struct QNode *next;
}QNode,*QueuePtr;

typedef struct  /*队列的链表结构*/
{
	QueuePtr front,rear;  /*队头、队尾指针*/
}LinkQueue;

2.4.1 入队操作

入队操作，其实就是在链表尾部进行插入。

Ststus EnQueue(LinkQueue *Q, QRlemType e)
{
	Queueptr s = (QueuePtr)malloc(sizeof(QNode));
	if(!s)    /*存储分配失败*/
		exit(OVERFLOW);
	s->data = e;
	s->next = NULL;
	Q->rear->next = s;   /*把拥有元素e新节点s赋值给原队尾结点的后继*/
	Q->rear=s;    /*把当前的s设置为队尾结点，rear指向s*/
	return OK;
}

2.4.2 出队操作

/*若队列不空，删除Q的队头元素，用e返回其值，并返回OK，否则返回ERROR*/
Status DeQueue(LinkQueue *Q, QElemType *e)
{
	QueuePtr p;
	if(Q->front == Q->rear)
		return ERROR;
	p=Q->front->next; /*将欲删除的队头结点站存给p*/
	*e=p->data;    /*将欲删除的队头结点数据赋值给e*/
	Q->front->next = p->next;    /*将原队头结点后继p->next赋值给头节点后继，以实现删除操作*/
	if(Q->rear == p)    /*若队头是队尾，则删除后将rear指向头节点*/
		Q->rear = Q->front;
	free(p);
	return OK;
}

三、总结

在可以确定队列长度最大值的时候，建议用循环队列，无法预估队列长度则建议用链队列。

总结：
栈和队列都是特殊线性表，只不过对插入和删除操作做了限制。

栈（Stack）是限定仅在表尾进行插入和删除操作的线性表。
- 线性存储时，如果是两个相同数据类型的栈，则可以用数组两端作为栈底，让两个栈共享数组空间。
- 链式结构和线性表基本相同
队列（Queue）是只允许在一段进行插入操作，而在另一端进行删除操作的线性表。
- 为了避免数组的插入和删除需要频繁移动数据，于是引入了循环队列，是的队头和队尾可以在数组中循环变化，使得插入和删除的时间复杂度由O(n)减少到O(1)。
- 链式结构和线性表基本相同

【Data Structure】数据结构解构其四：栈和队列

一、栈