【图解数据结构】 栈&队列
1.栈
1.1栈的定义
栈（stack）是限定在表尾进行插入和删除的操作的线性表。
我们把允许插入和删除的一端称为栈顶（top），另一端称为栈底（bottom）,不包含任何数据元素的栈称为空栈。栈又称为后进先出（Last In First Out）的线性表，简称LIFO结构。
栈的插入操作，叫做进栈，也称压栈、入栈。
栈的删除操作，叫做出栈，也称弹栈。
1.2栈的顺序存储结构及实现
既然栈是线性表的特例，那么栈的顺序存储其实也是线性表顺序存储的简化。
用数组实现，下标为0的一端作为栈底比较好，因为首元素都存在栈底。
栈的结构定义：
定义一个top变量来指示栈顶元素在数组中的位置，若存储栈的长度为SackSize,则栈顶位置top必须小于SackSize。当栈存在一个元素时，top等于0，因此通常把空栈的判定条件为top=-1。
typedef int SElemType;
typedef struct
{
SElemType data[MAXSIZE];
int top; /*用于栈顶指针*/
} SqStack;1.3栈的顺序存储结构——进栈操作
代码实现：
#define MAXSIZE 5
#define OK 1
#define ERROR 0
/*插入元素e为新的栈顶元素*/
Status Push(SqStack *S, SElemType e)
{
if (S->top == MAXSIZE - 1) /*栈满*/
{
return ERROR;
}
S->top++;
S->data[S->top] = e;
return OK;
}测试代码：
int main()
{
SqStack stack = { {1,2},1 }; /*初始化栈内有两个元素，top=1*/
Push(&stack, 3);
}运行结果：
1.4栈的顺序存储结构——出栈操作
代码实现：
#define MAXSIZE 5
#define OK 1
#define ERROR 0
/*若栈不为空，则删除S的栈顶元素，用e返回其值*/
Status Pop(SqStack *S, SElemType *E)
{
if (S->top == -1)
{
return ERROR;
}
*E = S->data[S->top];
S->data[S->top] = NULL;
S->top--;
return OK;
}测试代码：
int main()
{
SElemType e;
SqStack stack = { {1,2},1 }; /*初始化栈内有两个元素，top=1*/
Push(&stack, 3);
Pop(&stack, &e);
}运行结果：
验证了栈是后进先出的结构。
1.5栈的链式存储结构及实现
栈的链式存储结构，简称为栈链。由于单链表有头指针，而栈顶指针也是必须的，那么便可以让它俩合二为一。以为就是说栈顶放在单链表的头部。
对于链栈来说，基本不存在栈满的情况，除非内存已经没有可以使用的空间。但是对于空栈来说，链表原定义是头指针指向空，那么链栈的空其实就是top=NULL。
栈链的结构代码如下：
typedef int SElemType;
typedef struct StackNode
{
SElemType data;
struct StackNode *next;
} StackNode;
typedef struct StackNode *LinkStackPtr;
typedef struct LinkStatck
{
LinkStackPtr top;
int count;
}LinkStatck;1.6栈的链式存储结构——进栈操作
代码实现：
#define OK 1
#define ERROR 0
typedef int Status;
typedef int SElemType;
/*插入元素e为新的栈顶元素*/
Status Push(LinkStatck *S, SElemType e)
{
LinkStackPtr s = (LinkStackPtr)malloc(sizeof(StackNode));
s->data = e;
s->next = S->top;
S->top = s; /*将新的节点s赋值给栈顶指针*/
S->count++;
return OK;
}测试代码：
int main()
{
LinkStatck stack = { NULL ,0}; /*初始化一个空链栈*/
Push(&stack, 1);
Push(&stack, 2);
Push(&stack, 3);
}运行结果：
动画模拟：
1.7栈的链式存储结构——出栈操作
代码实现：
#define OK 1
#define ERROR 0
typedef int Status;
typedef int SElemType;
/*若栈不为空，则删除S的栈顶元素，用e返回其值*/
Status Pop(LinkStatck *S, SElemType *e)
{
LinkStackPtr p;
if (S->count == 0)
{
return ERROR;
}
*e = S->top->data;
p = S->top; /*将栈顶节点赋值给p*/
S->top = S->top->next; /*使栈顶指针下移一位，指向后一节点*/
free(p); /*释放节点p*/
S->count--;
return OK;
}测试代码：
int main()
{
LinkStatck stack = { NULL ,0}; /*初始化一个空链栈*/
Push(&stack, 1);
Push(&stack, 2);
Push(&stack, 3);
SElemType e;
Pop(&stack, &e);
Pop(&stack, &e);
Pop(&stack, &e);
}运行结果：
动画模拟：
2.队列
2.1队列的定义
队列（queue）是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。
队列是一种先进先出（First In First Out）的线性表，简称FIFO。允许插入的一端称为队尾，允许删除的一端称为队头。
2.2队列的顺序存储结构
我们假设一个队列有n个元素，则顺序存储的队列需建立一个大于n的数组。
现在进行入队操作，就是在队尾插入一个元素，不需要移动任何元素，因此时间复杂度是O[1]。
出队操作是在队头，那么队列中所有的元素都要向前移动一个位置，确保下标为0的位置不为空，时间复杂度是O[n]，这是个问题。
如果不限定出队操作时所有的元素都要向前移动，也就是说队头不一定必须在下标为0 的位置，出队的性能就会大大增加。
但是这样又会出现另一个问题——假溢出，就是假设队列前面的位置是空着的，但是从队尾入队已经满了。
循环队列可以解决这一个问题，后面满了，就从头再开始，也就是头尾相接的循环，这种头尾相接的顺序存储结构称为循环队列。
但是循环队列还是会面临着数组溢出的问题。
2.3队列的链式存储结构及实现
队列的链式存储结构，其实就是线性表的单链表，只不过它能尾进头出而已，简称链队列。
队头指针指向链队列的头节点，而队尾指针指向终端节点：
空队列时都指向头节点：
链队列的结构如下：
typedef int QElemType;
typedef struct QNode /*结点结构*/
{
QElemType data;
struct QNode *next;
}QNode,*QueuePtr;
typedef struct /*队列的链表结构*/
{
QueuePtr front, rear; /*队头、队尾指针*/
} LinkQueue;2.4队列的链式存储结构——入队操作
入队操作，在队尾插入新元素。
代码实现：
#define OK 1
#define ERROR 0
typedef int Status;
/*插入元素e为Q的新的队尾元素*/
Status EnQueue(LinkQueue *Q, QElemType e)
{
QueuePtr s = (QueuePtr)malloc(sizeof(QNode));
s->data = e;
s->next = NULL;
Q->rear->next = s; /*把拥有元素e新节点s赋值给原队尾结点的后继*/
Q->rear = s; /*把s设置为队尾结点，rear指向s*/
return OK;
}测试代码：
int main()
{
/*头结点*/
QueuePtr head = (QueuePtr)malloc(sizeof(QNode));
head->data = 0;
head->next = NULL;
LinkQueue q = { head ,head }; //空队列，队头、队尾指针都指向头结点
EnQueue(&q, 1);
EnQueue(&q, 2);
}运行结果：
动画模拟：
2.4队列的链式存储结构——出队操作
代码实现：
#define OK 1
#define ERROR 0
typedef int Status;
/*若队列不为空，删除Q的队头元素，用e返回其值*/
Status DeQueue(LinkQueue *Q, QElemType *e)
{
QueuePtr p;
if (Q->front == Q->rear)
{
return ERROR;
}
p = Q->front->next; /*将欲删除的队头节点暂存给p*/
*e = p->data;
Q->front->next = p->next; /*将原队头结点后继赋值给头结点后继*/
if (Q->rear == p) /*若队头是队尾，则删除后将rear指向头结点*/
{
Q->rear = Q->front;
}
free(p);
return OK;
}测试代码：
int main()
{
/*头结点*/
QueuePtr head = (QueuePtr)malloc(sizeof(QNode));
head->data = 0;
head->next = NULL;
LinkQueue q = { head ,head };
EnQueue(&q, 1);
EnQueue(&q, 2);
QElemType e;
DeQueue(&q, &e);
}运行结果：
动画模拟：
