栈和队列（C 语言）

一、栈

1. 栈的概念

栈是一种特殊的线性表，只允许在固定的一端进行插入和删除操作，该端被称为栈顶，相对的另一端被称为栈底。栈中的元素遵循后进先出的规则LIFO（Last In First Out）。就像一堆书，规定一次只能拿一本或者放一本，那么最先放的书在最下面，最后放的书在最上面。

2. 栈的结构

在这里插入图片描述

3. 栈的实现思路

栈可以通过数组来实现，也可以通过链表来实现。

（1）数组
在这里插入图片描述

（2）链表
在这里插入图片描述

可以看到，在栈顶的插入和删除方面，数组是尾插和尾删，链表是头插和头删，时间复杂度都是O(1)。但是链表每次都需要申请节点，而数组扩容一次就可以使用一段时间，所以相对来说数组更优一点。

栈需要以下几种功能：
（1）在栈顶插入和删除
（2）返回栈顶元素
（3）检查栈是否为空
（4）返回当前栈中有效元素个数

所以，该栈结构需要三个成员：指向数据的指针，栈顶位置的记录，栈当前的容量大小。

4. 栈的实现代码

老样子，三个文件：头文件，方法实现文件，测试文件。

头文件：Stack.h

// 头文件
#include <stdio.h>
#include <stdbool.h>// 栈// 类型声明
typedef int DataType;// 常量声明
#define CAPACITY_INIT 8// 栈结构声明
typedef struct Stack
{DataType* pdata;  // 指向数据的指针size_t top;  // 下一个入栈位置size_t capacity;  // 当前栈的容量
}Stack;// 方法// 初始化栈
void StackInit(Stack* sk);// 入栈
void StackPush(Stack* sk, DataType data);// 出栈
void StackPop(Stack* sk);// 栈空判断
bool StackEmpty(const Stack* sk);// 返回栈中当前元素个数
size_t StackSize(const Stack* sk);// 返回栈顶元素
DataType StackTop(const Stack* sk);// 销毁栈
void StackDestory(Stack* sk);

方法实现文件：Stack.c

// 头文件
#include "Stack.h"
#include <assert.h>
#include <stdlib.h>// 方法// 初始化栈
void StackInit(Stack* sk)
{assert(sk);// 申请空间sk->pdata = (DataType*)malloc(sizeof(DataType) * CAPACITY_INIT);if (NULL == sk->pdata){perror("StackInit::malloc: ");exit(-1);}// 赋值sk->capacity = CAPACITY_INIT;sk->top = 0;
}// 入栈
void StackPush(Stack* sk, DataType data)
{assert(sk);// 增容判断if (sk->top == sk->capacity){// 增容DataType* tmp = (DataType*)realloc(sk->pdata, sizeof(DataType) * sk->capacity * 2);if (NULL == tmp){perror("StackPush::realloc: ");exit(-1);}// 成功后更新sk->pdata = tmp;sk->capacity *= 2;}// 入栈sk->pdata[sk->top++] = data;
}// 出栈
void StackPop(Stack* sk)
{// 空栈判段if (0 == sk->top){printf("Empty Stack!\n");exit(-1);}// 出栈--sk->top;
}// 栈空判断
bool StackEmpty(const Stack* sk)
{assert(sk);return (0 == sk->top);
}// 返回栈中当前元素个数
size_t StackSize(const Stack* sk)
{assert(sk);return sk->top;
}// 返回栈顶元素
DataType StackTop(const Stack* sk)
{assert(sk);// 空栈判断if (0 == sk->top){printf("Empty Stack!\n");exit(-1);}// 返回return sk->pdata[sk->top - 1];
}// 销毁栈
void StackDestory(Stack* sk)
{assert(sk);// 释放数据free(sk->pdata);sk->pdata = NULL;// 成员置零sk->top = sk->capacity = 0;
}

测试文件：test.c

// 头文件
#include "Stack.h"int main()
{// 栈测试// 创建栈Stack sk;// 初始化栈StackInit(&sk);// 入栈int i = 0;for (i = 1; i <= 9; ++i){StackPush(&sk, i);}// 出栈+显示for (i = 0; i < 9; ++i){printf("%d ", StackTop(&sk));StackPop(&sk);}printf("\n");// 销毁栈StackDestory(&sk);
}

（4）测试结果：
在这里插入图片描述

也可以使用链表来实现栈，但是现在的栈都是使用数组来实现，相关的面试题给的栈也是用数组实现的。感兴趣的读者可以自己尝试使用链表实现一个栈。

二、队列

1. 队列的概念

队列也是一种特殊的线性表，它只能从前端出数据，从后端入数据，符合先进先出的规则FIFO（First In First Out）。也就和我们日常排队是一个道理，当然插队不算数哈。

2. 队列的结构

在这里插入图片描述

3. 队列的实现思路

队列通常使用链表来实现，为什么不用数组？因为数组头插需要挪动数据，有人说可以在队头出数据，在队尾入数据，那扩容之后怎么办？那链表在尾部入数据还要找尾呢，这个可以在队列结构中添加一个尾指针就可以解决。

所以，队列包含两个链表节点指针，一个指向队列的队头，另一个指向队列的队尾。

队列需要实现如下功能：
（1）在队头出数据
（2）在队尾入数据
（3）空队检查
（4）返回当前队列元素个数
（5）返回队头元素
（6）返回队尾元素

为了方便返回队列当前元素个数，可以在队列结构中添加一个 size 变量，专门记录当前元素个数。

4. 队列的实现代码

头文件：Queue.h

// 头文件
#include <stdio.h>
#include <stdbool.h>// 队列// 类型声明
typedef int DataType;// 节点结构声明
typedef struct Node
{DataType val;struct Node* next;
}Node;// 队列结构声明
typedef struct Queue
{Node* head;Node* tail;size_t size;
}Queue;// 方法// 初始化队列
void QueueInit(Queue* q);// 入队
void QueuePush(Queue* q, DataType data);// 出队
void QueuePop(Queue* q);// 返回队头元素
DataType QueueFront(Queue* q);// 返回队尾元素
DataType QueueBack(Queue* q);// 空队判断
bool QueueEmpty(Queue* q);// 返回队列当前元素个数
size_t QueueSize(Queue* q);// 销毁队列
void QueueDestory(Queue* q);

方法实现文件：Queue.c

// 头文件
#include "Queue.h"
#include <assert.h>
#include <stdlib.h>// 方法// 初始化队列
void QueueInit(Queue* q)
{assert(q);// 初始化q->head = q->tail = NULL;q->size = 0;
}// 入队
void QueuePush(Queue* q, DataType data)
{assert(q);// 申请新节点Node* new_node = (Node*)malloc(sizeof(Node));if (NULL == new_node){perror("QueuePush::malloc: ");exit(-1);}// 申请成功，赋值new_node->val = data;new_node->next = NULL;// 链接入队// 头插判断if (NULL == q->head){q->head = q->tail = new_node;}else  // 尾插{q->tail->next = new_node;q->tail = new_node;}// 元素个数 +1++q->size;
}// 出队
void QueuePop(Queue* q)
{assert(q);// 空队判断if (NULL == q->head){printf("Empty Queue!\n");exit(-1);}// 出队// 尾删判断if (NULL == q->head->next){// 释放free(q->head);// 置空q->head = q->tail = NULL;}else{// 存储下一个结点Node* next = q->head->next;// 删除头节点free(q->head);// 新头节点q->head = next;}// 元素个数 -1--q->size;
}// 返回队头元素
DataType QueueFront(Queue* q)
{assert(q);// 空队判断if (NULL == q->head){printf("Empty Queue!\n");exit(-1);}// 返回return q->head->val;
}// 返回队尾元素
DataType QueueBack(Queue* q)
{assert(q);// 空队判断if (NULL == q->head){printf("Empty Queue!\n");exit(-1);}// 返回return q->tail->val;
}// 空队判断
bool QueueEmpty(Queue* q)
{assert(q);return (0 == q->size);
}// 返回队列当前元素个数
size_t QueueSize(Queue* q)
{assert(q);return q->size;
}// 销毁队列
void QueueDestory(Queue* q)
{assert(q);Node* cur = q->head;while (cur){// 存储下一个节点Node* next = cur->next;// 释放当前节点free(cur);// 下一个节点cur = next;}// 成员置空q->head = q->tail = NULL;q->size = 0;
}

测试文件：test.c

// 头文件
#include "Queue.h"int main()
{// 队列测试// 创建队列Queue q;// 初始化队列QueueInit(&q);// 入队int i = 0;for (i = 1; i <= 9; ++i){QueuePush(&q, i);}// 出队+打印for (i = 0; i < 9; ++i){printf("%d ", QueueFront(&q));QueuePop(&q);}// 销毁队列QueueDestory(&q);return 0;
}