前言
栈和队列作为一种典型的线性表，都是基于线性表(顺序表)实现的，有人可能会问，我都有线性表了，为什么还要知道栈和队列呢？
举个例子：
有个小平大厨，他要去做一道名菜，可能要花费上百道刀工，在此期间他会换不同的刀去完成不同的工艺，我们试想一下难道我用一把刀就不能完成各种刀工，其实也是可以的，那小平大厨为什么要那么麻烦去换不同的刀呢?那大家肯定会说这样方便啊！对没错就是方便。
其实换到数据结构上来说，由于我们会频繁的入栈、出栈、取栈顶元素，怎么操作都是最常用的，所以我们就定义栈和队列来完成他，省的我们去运用更麻烦的线性表，降低我们出错的概率。
下面我们就一起去认识栈和队列吧！
一 “栈”
栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底
压栈(入栈)：栈的插入操作，数据会在栈顶
出栈：栈的删除操作叫做出栈。出数据也在栈顶
我们可以理解为出栈就为压栈的逆过程
栈的特点：先进后出
二 栈的实现
对于栈来说，由于他都是尾插和尾删数据，所以我们选择用顺序表来实现他，此时间复杂度为O（1）。
1 栈的定义
这里我们在Stack.h的头文件中包含以下内容：
#pragma once #include<stdio.h> #include<assert.h> #include<stdlib.h> #include<stdbool.h> typedef int STDataType; //定义栈 typedef struct Stack { STDataType* arr;//数据类型 int pos;//数组下标 int capacity;//栈的容量 }ST; //初始化 void StackInit(ST* ps); //销毁 void StackDestroy(ST* ps); //入栈 void StackPush(ST* ps, STDataType x); //出栈 void StackPop(ST* ps); 显示返回栈顶数据 STDataType StackTop(ST* ps); //判断栈是否为空 bool StackEmpty(ST* ps); //返回栈的长度 int StackSize(ST* ps);
2 栈功能的实现
#include"Stack.h" //初始化 void StackInit(ST* ps) { assert(ps); ps->arr = NULL;//初始数组为空 ps->pos = ps->capacity = 0;//初始为0 } //销毁 void StackDestroy(ST* ps) { assert(ps); free(ps->arr);//arr是整个栈的地址 ps->arr = NULL; ps->capacity = ps->pos = 0; } //入栈 void StackPush(ST* ps, STDataType x) { assert(ps); //判断栈的空间是否满 if (ps->pos == ps->capacity) { //扩容 int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;//扩2倍 STDataType* tmp = (STDataType*)realloc(ps->arr,newCapacity * sizeof(STDataType)); if (tmp == NULL) { perror("reamlloc fail"); exit(-1); } //跟新容量 ps->arr = tmp; ps->capacity = newCapacity; } //入栈 ps->arr[ps->pos] = x; ps->pos++;//下标++ } //出栈 void StackPop(ST* ps) { assert(ps); //断言栈是否为空 assert(!StackEmpty(ps)); --ps->pos; } //判断栈是否为空 bool StackEmpty(ST* ps) { assert(ps); return ps->pos == 0; } //显示返回栈顶数据 STDataType StackTop(ST* ps) { assert(ps); //断言栈是否为空 assert(!StackEmpty(ps)); return ps->arr[ps->pos - 1];//下标已经前移 } //返回栈的长度 int StackSize(ST* ps) { assert(ps); return ps->pos; }
在这里我们重点为大家刨析压栈，出栈，取栈的写法。
（1）压栈
//入栈 void StackPush(ST* ps, STDataType x) { assert(ps); //判断栈的空间是否满 if (ps->pos == ps->capacity) { //扩容 int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;//扩2倍 STDataType* tmp = (STDataType*)realloc(ps->arr,newCapacity * sizeof(STDataType)); if (tmp == NULL) { perror("reamlloc fail"); exit(-1); } //跟新容量 ps->arr = tmp; ps->capacity = newCapacity; } //入栈 ps->arr[ps->pos] = x; ps->pos++;//下标++ }
这里我们的实现思路是：
判断栈的空间是否以满；
在进行入栈
（2）出栈
//出栈 void StackPop(ST* ps) { assert(ps); //断言栈是否为空 assert(!StackEmpty(ps)); --ps->pos; }
出栈的实现是非常简单的，只要将pos的标记--即可。
（3）取栈
//显示返回栈顶数据 STDataType StackTop(ST* ps) { assert(ps); //断言栈是否为空 assert(!StackEmpty(ps)); return ps->arr[ps->pos - 1];//下标已经前移 }
我们直接返回栈顶指针即可
每当我们完成一个功能时候，我们都应该去测试一下：
三 “队列”
队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出
入队列：进行插入操作的一端称为队尾
出队列：进行删除操作的一端称为队头
四 队列的实现
1 队列的定义
我们同样在Queue头文件在实现:
#pragma once #include<stdio.h> #include<assert.h> #include<stdlib.h> #include<stdbool.h> typedef int QDataType; //定义队列 typedef struct QueueNode { QDataType data;//数据类型 struct QueueNode* next; }QNode; //定义指向头和尾的二个指针 typedef struct Queue { QNode* head; QNode* tail; int size; }Queue; //初始化 void QueueInit(Queue* pq); //销毁 void QueueDestroy(Queue* pq); //入队 void QueuePush(Queue* pq, QDataType x); //出队 void QueuePop(Queue* pq); //返回指向队头的数据的指针 QDataType QueueFront(Queue* pq); //返回指向队尾的数据的指针 QDataType QueueBack(Queue* pq); //判断队列是否为空 bool QueueEmpty(Queue* pq); //返回队列的大小 int QueueSize(Queue* pq);
由于栈和队列中定义是差不多，这里就不在过的的说明了。
2 队列的实现
这里就直接上代码，里面有详细的注释，大家不懂就可以看看。
大家在实现队列时可以对照着头文件的函数功能经行实现。
#define _CRT_SECURE_NO_WARNINGS #include"Queue.h" //初始化 void QueueInit(Queue* pq) { assert(pq); pq->head = pq->tail = NULL; pq->size = 0; } //销毁 void QueueDestroy(Queue* pq) { assert(pq); QNode* cur = pq->head; while (cur) { QNode* del = cur; cur = cur->next;//指向下个节点 free(del); } pq->head = pq->tail = NULL;//防止出现野指针 pq->size = 0; } //入队 void QueuePush(Queue* pq, QDataType x) { assert(pq); //申请节点 QNode* newNode = (QNode*)malloc(sizeof(QNode)); if (newNode==NULL) { perror("malloc fail"); exit(-1); } else { newNode->data = x; newNode->next = NULL; } //队列为空 if (pq->tail == NULL) { pq->head = pq->tail = newNode; } //不为空 else { pq->tail->next = newNode; pq->tail = newNode;//tail指针指向newNode } pq->size++; } //出队 void QueuePop(Queue* pq) { assert(pq); //断言队列是否为空 assert(!QueueEmpty(pq)); //当队列中就一个数据时 if (pq->head->next == NULL) { free(pq->head); pq->head = pq->tail = NULL; } else { QNode* del = pq->head; pq->head = pq->head->next;//头变为下个节点 free(del); del = NULL; } pq->size--; } //判断队列是否为空 bool QueueEmpty(Queue* pq) { assert(pq); return pq->tail == NULL; } //返回指向队头的数据的指针 QDataType QueueFront(Queue* pq) { assert(pq); //断言队列是否为空 assert(!QueueEmpty(pq)); return pq->head->data; } //返回指向队尾的数据的指针 QDataType QueueBack(Queue* pq) { assert(pq); //断言队列是否为空 assert(!QueueEmpty(pq)); return pq->tail->data; } //返回队列的大小 int QueueSize(Queue* pq) { return pq->size; }
下面我们继续测试一下队列是否能够成功实现自己的功能：
五 栈和队列的区别
栈和队列区别：
(1)操作的限定不同:
栈是在栈顶进栈顶出，无法对栈底进行直接操作。
队列是在队尾入队头出，可以对二边进行操作。
(2）操作的规则不同:
栈是先进后出，新来的成员从栈顶入，老成员要想离开，就得先让栈顶的成员先离开。
队列是先进先出,新来的成员总是在队尾插入，每次离开的成员都是从队头离开。
(3)遍历数据速度不同:
栈是只能从顶部取数据，也就是说最先进入栈底的，需要遍历整个栈才能取出来，而且在遍历数据的同时需要为数据开辟临时空间，保持数据在遍历前的一致性
队列是通过地址指针进行遍历，而且可以从头部或者尾部进行遍历，但不能同时遍历，无需开辟空间，因为在遍历的过程中不影响数据结构，所以遍历速度要快
