栈和队列的定义和特点

• 栈和队列是两种常用、重要的线性结构，从数据结构角度上来看也是线性表。
• 栈和队列是限定插入和删除只能在表的“端点”进行操作的线性表。

栈：是限定仅为表尾进行插入或者删除的线性表。因此，对栈来说，表尾端有其特殊含义，成为 栈顶（top），相应的，表头端称为 栈底（bottom）。不含元素的空表称为空栈。栈是一种 后进先出的线性表；

与栈相反， 队列（queue）是一种 先进先出（first in first out，缩写为FIFO）的线性表，它只允许在表的一端进行插入，而在另一端删除元素。在队列中，允许插入的一端叫做 队尾（rear），允许删除的一端则称为 队头（front）。

栈的表示和实现 http://dxb.myzx.cn

栈的插入操作，叫做进栈，也称压栈、入栈。
栈的删除操作，叫作出栈，也有的叫弹栈。

栈的顺序存储结构

我们定义一个top变量来指示栈顶元素在数组中的位置，类似于小时候学过的油游标卡尺，它的来回移动就意味着栈顶top可以变大变小。当栈存在一个元素是，top等于0，因此通常把空栈的判断条件定为top等于-1.

栈的结构定义

typedef int SElemType;typedef struct{
	SElemTye data[MAXSIZE];
	int top;      /* 用于栈顶指针 */}SqStack;123456

栈的顺序存储结构——进栈操作 http://zzdxb.baikezh.com/

对于栈的插入，即进栈操作（如下图所示）：

代码如下：

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

栈的顺序存储结构——出栈操作

出栈操作pop

代码如下：

/* 若栈不空，则删除s的栈顶元素，用e返回其值，并返回OK；否则返回ERROR*/Status Pop(SqStack *s,SElemType *e){
	if(s->top == -1)
		return ERROR;
	*e = s->data[s->top];   /* 将要删除的栈顶元素赋值给e */
	s->top--;               /* 栈顶指针减一 */
	return OK;      }123456789

• 两者没有涉及到任何循环语句，因此时间复杂度均为O(1)。 http://dxb.myzx.cn/henan/

栈的链式存储结构

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

链栈的结构代码如下：

typedef struct StackNode{
	SElemType data;
	struct StackNode *next;}StackNoda,*LinkStackPtr;typedef struct LinkStack{
	LinkStackPtr top;
	int count;}LinkStack;1234567891011

栈的链式存储结构——进栈操作

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

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

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

对于链栈的pop操作，也是很简单的三句操作。假设用变量 p 用来存储要删除的栈顶结点，将栈顶指针下移一位，最后释放p即可。
代码表示如下： http://zzdxb.baikezh.com/jiyuan/

/* 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR */Status Pop(LinkStack *S, SElemType *e){
	LinkStackPtr p;
	if(StackEmpty(*S))
		return ERROR;
	*e = S->top->data;
	p=S->top;                /* 将栈顶结点赋值给p */
	S->top = S->top->next;   /* 使得栈顶指针下移一位，指向后一结点 */
	free(p);
	S->count--;
	return OK;}12345678910111213

如果栈的使用过程中元素变化不可预料，有时很小，有时非常大，那么最好是用链栈，反之，如果它的变化在可控范围内，建议使用顺序栈会更好一些 http://dxb.myzx.cn/question/

队列的表示和实现

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

与栈不同的是，队列元素的出列是在队头，即下标为0的位置，也就是意味着，队列中的所有元素都得想前移动，以确保队列的队头也就是小标为0的位置不为空，此时时间复杂度为O（n），如下图所示：

（手绘多包涵）

为了避免当只有一个元素时，队头和队尾重合使处理编的麻烦，所有引入两个指针， front 指针指向队头元素， rear 指针指向队尾元素的下一个位置，这样当front等于rear时，此队列不是还剩一个元素，而是空队列。

假如这个队列的总个数不超过5个，但是目前如果接着入队的话，因数组末尾元素已经占用，再向后加，就会产生数组越界的错误，可实际上，我们的队列在下标为0和1的地方还是空闲的。我们把这种现象称为“假溢出”。
因此引入循环队列概念。 http://ask.baikezh.com/

另外，当rear > front 时，此时队列的长度为 rear - front 。但当 rear < front 时，队列长度分为两段，一段是QueueSize - front，另一段是0 + rear ，加在一起，队列长度为 rear - front + QueueSize。因此通用的计算队列长度公式为：
（rear - front + QueueSize）% QueueSize

队列的链式存储结构及实现

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

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

链队列的结构为： http://ask.baikezh.com/anhui/

typedef int QElemType; /* QElemType 类型根据实际情况而定 */typedef struct QNode  /* 姐弟啊结构 */{
	QElemType data;
	struct QNode *next;}QNode,*Queueptr;typedef struct              /* 队列的链表结构 */{
	QueuePtr front,rear;   /* 队头、队尾指针 */}LinkQueue;123456789101112

队列的链式存储结构——入队操作

入队操作时，其实就是在链表尾部插入结点。
其代码如下： http://zzdxb.baikezh.com/zhumadian/

/* 插入元素e为Q的新的队尾元素 */Status EnQueue(LinkQueue *Q, QElemType 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;}1234567891011

队列的链式存储结构——出队操作

出队操作时，就是头结点的后继结点出队，将头结点的后继改为它后面的结点，若链表除头结点外只剩下一个元素时，则需要将 rear 指向头结点。

代码如下： http://ask.baikezh.com/heilongjiang/

/* 若队列不空，删除Q的队头元素，用e返回其值，并返回OK */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;}1234567891011121314

总的来说，在确定队列长度最大值的情况下，建议用循环队列，如果你无法预估队列的长度时，则用链队列。