栈与队列是两种重要的线性结构。从数据结构角度来看，栈和队也是线性表，其特殊性在于其操作受限，是限定性的数据结构。但从数据类型上看，它是和线性表大为不同的抽象数据类型。
栈与队列的定义和概念
栈
定义
栈（stack）是限定在表尾巴进行插入或删除操作的线性表；栈是一种后进先出的线性表（LFIO 结构），比如货仓里的货物。
栈顶
栈顶（top）是线性表运行进行插入删除的那一端。
栈底
栈底（bottom）是固定的，不允许进行插入与删除的另一端。
卡特兰数
卡特兰数（catalan）是对栈的一种数学描述。n 个不同元素进栈，出栈元素不同排列个数为 \frac{1}{n+1}C^{n}_{2n}
性质
栈是一种后进先出的线性表（LFIO 结构），比如货仓里的货物。
队列
定义
队列（queue）是一种先进先出（FIFO）的线性表，只允许在一端插入，而在另一端删除。
队尾
队尾（rear）是允许插入的一端。
队首
队首（front）是允许删除的一端。
栈与队列的实现
注：这里栈实现的是顺序栈，队是链队。此外如链队，循环队等等后补（咕咕咕）；并且在实现后的测试均只测试部分。
栈
顺序栈的数据结构
#include <stdio.h>
#include <stdlib.h>
#include "Status.h"
//顺序栈相关操作
#define stackinitsize 100
#define stackincrement 10
//在迷宫 表达式 二叉树二叉链表 孩子兄弟树中次类型要重新定义
typedef int selemtype_sq;
typedef struct{
selemtype_sq *base;//在栈构造之前和销毁后，base值为null
selemtype_sq *top;//栈顶指针
int stacksize;//栈规模
}sqstack;
初始化
Status initstacksq(sqstack *S){
(*S).base=(selemtype_sq*)malloc(stackinitsize*sizeof(selemtype_sq));
if(!(*S).base) exit(OVERFLOW);
(*S).top=(*S).base;
(*S).stacksize=stackinitsize;
return OK;
};
和顺序表的初始化类比，都是一样的思路。
出入值是指针类型，指向 sqtack 结构量 S；我们对数据元素 base 进行空间分配（后判断是否分配成功）。然后将栈顶也指向栈底指向的空间（这样栈的长度就为 0 了）；将栈的最大规模赋值为栈的初始化规模。
销毁
Status destorystacksq(sqstack *S){
free((*S).base);
(*S).base=NULL;
(*S).top=NULL;
(*S).stacksize=0;
return OK;
};
和顺序表类比。
我们需要对初始化中申请的空间进行释放（free），是否之后我们要将指针指向空（不然这个指针就是一个没有指向的野指针），最后对栈规模清 0.
清空与栈长栈空
Status clearstacksq(sqstack S){
(*S).top=(*S).base;
return OK;
};
int stacklensq(sqstack S){
return S.top-S.base;
};
Status stackemptysq(sqstack S)
{
if(S.top==S.base)
return TRUE;
else
return FALSE;
}
略
返回栈顶元素
Status gettopsq(sqstack S,selemtype_sq *e){
if(S.top==S.base) return ERROR;
*e=*(S.top-1);
return OK;
};
传入值是栈 S 和指针 e（保存栈顶元素）。对栈长度进行判断，若长度为 0，则后续操作没有意义了。
我们可以直接访问栈顶元素（也就是 S.top）。
为什么这里的栈顶元素是（S.top-1）呢？
我的理解是这里 S.top 是一个没有元素值的栈顶，也就是说仅仅是为了栈结构而存在的栈顶（有了栈顶就方便进行定义中的限定操作），这样做可以保护数据。
进栈和出栈
Status pushsq(sqstack *S,selemtype_sq e){
if((*S.top-(*S).base)+1>=(*S).stacksize){
(*S).base=(selemtype_sq*)realloc((*S).base,((*S).stack+stackincrement));
if(!(*S).base) exit(OVERFLOW);
(*S).top=(*S).base+(*S).stacksize;
(*S).stacksize+=stackincrement;
}
*(S->top)=e;
(S->top)++;
return OK;
};
Statsu popsq(sqstack *S,selemtype_sq *e){
if((*S).top==(*S).base) return ERROR;
(*S).top--;
*e=*((*S).top);
return OK;
};
进栈传入指针类 S（指向栈，因为我们需要对栈元素进行改变）和元素 e。
判断元素进栈后长度是否超过规模，若超过，需要重新分配空间。之后进行元素的入栈，我们将元素 e 填充到栈顶的位置，然后栈顶加一
出栈类似，栈顶减一，将栈顶的元素取出。
遍历
Status stacktravesq(sqstack S,void(Visit)(selemtype_sq)){
selemtype_sq *p=S.base;
while(p<S.top) Visit(*p++);
return OK;
};
略
栈测试
#include <stdio.h>
#include "sequncestack.h"
void printelem(selemtype_sq e){
printf("%d ",e);
};
int main(){
sqstack S;
int i=0;
selemtype_sq e=0;
printf("init测试...\n");
{
printf("初始化顺序栈S...\n");
initstacksq(&S);
printf("\n");
}
PressEnter;
printf("stackempty测试...\n");
{
stackemptysq(S)?printf("S 为空\n") : printf("S 不为空\n");
printf("\n");
}
PressEnter;
printf("push测试\n");
{
for(i=1;i<=6;i++){
printf("将%2d压入栈S",2*i);
pushsq(&S,2*i);
printf("（累计第 %d 个元素）...\n", S.top-S.base);
}
printf("\n");
}
PressEnter;
printf("stacktravesq 测试...\n");
{
printf(" S 中的元素为：S = ");
stacktravesq(S, printelem);
printf("\n\n");
}
PressEnter;
printf("pop 测试...\n");
{
popsq(&S, &e);
printf("栈顶元素 \"%d\" 出栈...\n", e);
printf(" S 中的元素为：S = ");
stacktravesq(S, printelem);
printf("\n\n");
}
PressEnter;
printf("stacklensq 测试...\n");
{
i = stacklensq(S);
printf(" S 的长度为 %d \n", i);
printf("\n");
}
PressEnter;
printf("gettop 测试...\n");
{
gettopsq(S, &e);
printf("栈顶元素的值为 \"%d\" \n", e);
printf("\n");
}
PressEnter;
}
队列
链队数据结构
#include <stdio.h>
#include <stdlib.h>
#include "Status.h"
//链队相关操作，在模拟银行排队二叉树三叉链表算法需重新定义
typedef int qelemtype_l;
typedef struct qnode{
qelemtype_l data;
struct qnode *next;
}qnode;
typedef qnode* queueptr;
typedef struct{
queueptr front;
queueptr rear;
}linkqueue;
注意这里 typedef struct qnode 和过去的结构定义不太一样，对语法来说我们不需要在 struct 后面跟类型名，但是这里我们在结构体内设置了数据元素 struct qnode；可能是因为程序自上而下进行，如果不 typedef struct qnode 这么用，程序无法识别这个数据元素是什么。
初始化
Status initqueuel(linkqueue *Q){
(*Q).front = (*Q).rear = (queueptr)malloc(sizeof(qnode));
if(!(*Q).front)
exit(OVERFLOW);
(*Q).front->next = NULL;
return OK;
};
传入的是链类型指针 Q，对链头和链尾进行空间分配，判断分配成功后对这两个指针赋值 NULL ，不要让他们成为野指针。
清空
void clearqueuel(linkqueue *Q){
(*Q).rear = (*Q).front->next;
while((*Q).rear)
{
(*Q).front->next = (*Q).rear->next;
free((*Q).rear);
(*Q).rear = (*Q).front->next;
}
(*Q).rear = (*Q).front;
};
链式存储与顺序存储是不同的，注意链之间的关系，注意勾链的逻辑，一般是先右后左。
看看链队的勾链把，首先链尾设置为链头的后一位，现在将链头的下一个指向链尾的下一个，释放链尾，链尾重新指向为链头的下一个；这样我们就释放了一个结点，一直循环到没有链尾（结点）。
这时为了保证队链结构的完整性，我们讲队尾指向队首。
销毁
void destoryqueuel(linkqueue *Q){
while((*Q).front)
{
(*Q).rear = (*Q).front->next;
free((*Q).front);
(*Q).front = (*Q).rear;
}
};
销毁只需要将整个空间释放就行了，将首尾相指，释放空间，重新定向，如此循环，直到最后一个结点被释放。
判空和队长
Status queueemptyl(linkqueue Q){
if(Q.front==Q.rear)
return TRUE;
else
return FALSE;
};
int queuelenl(linkqueue Q){
int count = 0;
queueptr p = Q.front;
while(p!=Q.rear)
{
count++;
p = p->next;
}
return count;
};
略
得到队首元素
Status getheadl(linkqueue Q,qelemtype_l *e){
queueptr p;
if(Q.front==Q.rear)
return ERROR;
p = Q.front->next;
*e = p->data;
return OK;
};
类似于栈，我们首先要判断长度，如果长度为 0 程序也没有进行下去的必要了。同样这里我们默认为链头结点是不存放数据的，取出第一个元素数据是链头的后一个。
入队
Status enqueuel(linkqueue *Q,qelemtype_l e){
queueptr p;
p = (queueptr)malloc(sizeof(qnode));
if(!p)
exit(OVERFLOW);
p->data = e;
p->next = NULL;
(*Q).rear->next = p;
(*Q).rear=p;
return OK;
};
对于链式结构来说，增添新元素就是添加一个结点，所有我们要为这个结点分配空间（这个结构 qnode 内有指针，我们要弄清楚什么时候需要去分配，弄清楚 malloc 服务的对象）。分配成功后对结点赋值。队是限制性操作的线性表，我们直接在队尾前插入就行。
注意这里是怎么插入的，这里是先右，(*Q).rer->next=p 后左 (*Q).rear=p ；尾结点的下一个指向（是）p，这是将结点 p 入链；后更新尾指针为 p，这时候队尾指针就是指向结点 p 的。
在写下这段话后，我们感觉到了指针与实体结点的疏离感，其实我本身会混淆指针与结点之间的关系，认为指针就是结点，猫猫愚钝。
出队
Status dequeuel(linkqueue *Q,qelemtype_l *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;
};
略 注意勾链的步骤。
遍历
void queuetravell(linkqueue Q,void(Visit)(queuetype_l)){
queueptr p;
p = Q.front->next;
while(p)
{
Visit(p->data);
p = p->next;
}
};
通过一个指针不断向后移动完成遍历
链队测试
#include <stdio.h>
#include "linkqueue.h"
void printelem(qelemtype_l e){
printf("%d ",e);
}
int main(){
linkqueue Q;
int i=0;
qelemtype_l e=0;
printf("initqueuel 测试...\n");
{
printf("初始化链队 Q ...\n");
initqueuel(&Q);
printf("\n");
}
PressEnter;
printf("queueemptyl 测试...\n");
{
queueemptyl(Q) ? printf(" Q 为空！！\n") : printf(" Q 不为空！\n");
printf("\n");
}
PressEnter;
printf("enqueuel 测试...\n");
{
for(i=1; i<=6; i++)
{
printf("元素 \"%2d\" 入队，", 2*i);
enqueuel(&Q, 2*i);
printf("（累计第 %d 个元素）...\n", queuelenl(Q));
}
printf("\n");
}
PressEnter;
printf("queuetravell 测试...\n");
{
printf(" Q 中的元素为：Q = ");
queuetravell(Q, printelem);
printf("\n\n");
}
PressEnter;
printf("dequeuel 测试...\n");
{
dequeuel(&Q, &e);
printf("队头元素 \"%d\" 出队...\n", e);
printf(" Q 中的元素为：Q = ");
queuetravell(Q, printelem);
printf("\n\n");
}
PressEnter;
printf("queuelengthl 测试...\n");
{
i = queuelenl(Q);
printf(" Q 的长度为 %d \n", i);
printf("\n");
}
PressEnter;
printf("getheadl 测试...\n");
{
getheadl(Q, &e);
printf("队头元素的值为 \"%d\" \n", e);
printf("\n");
}
PressEnter;
}
栈与队列的应用
栈与队列的应用十分广泛，光书上的就有数制转换，括号匹配，行程序编辑，迷宫，表达式求值，汉诺塔等等，有时间补（鸽了！）
思考
- 栈和队列的主要区别
- 3 个不同元素依次进栈，能有几种不同的出栈序列
这里顺便把上节的问题回答了
- 存储密度大，方便访问
- 随机，注意这里是存储结构，意思是我们能够通过下标任意的访问第 i 号元素的数值。与之相反的链式存储，你想想，链表的每个结点都有一个指向后继的指针，所以我们要访问链表的结点必须从第一个开始访问，真能说是随机的吗？
但另一方面，我们称顺序表的顺序存储结构，指的是逻辑结构上是紧紧挨着的。
所以 线性表的顺序存储结构是一种随机存取的存储结构。哈哈怎么样晕了吗。
ps: 摸一摸数据结构(目录)
欢迎来到这里！
我们正在构建一个小众社区，大家在这里相互信任，以平等 • 自由 • 奔放的价值观进行分享交流。最终，希望大家能够找到与自己志同道合的伙伴，共同成长。
注册 关于