一. 栈
1.1 概念与结构
栈：一种特殊的线性表，其 只允许在固定的一端进行插入和删除元素操作 。进行数据插入和删除操作的一端称为 栈顶 ，另一端称为 栈底 。栈中的数据元素遵守 后进先出LIFO （Last In First Out）的原则。 压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。 出栈：栈的删除操作叫做出栈。出数据也在栈顶。1.2 栈的实现
在实现栈之前，我们想一下实现栈要用什么结构，是数组？顺序表？单链表？根据栈的特性：只允许在一端进行插入和删除元素的操作。我们会首选数组，原因是什么呢？在C语言中，使用数组来实现栈结构有以下几个优势：访问效率高
- 数组是连续存储的内存结构，通过下标访问元素的时间复杂度为O(1)。
- 顺序表本质上也是基于数组实现的，虽然也有连续存储的特性，但在栈的操作场景下，数组可以更简洁地实现栈的功能。
实现简单
- 用数组实现栈，只需要定义一个数组和一个记录栈顶位置的变量。
- 相比之下，链表实现栈需要定义链表节点结构体，涉及节点的动态内存分配和指针操作，实现起来较为复杂。
空间利用可预测
- 数组实现栈，空间大小在定义时基本确定（如果是静态数组），如 char buffer_stack[100]; ，其占用的内存空间是固定的。这在一些对内存使用要求可预测的场景很有用，便于进行内存管理和性能评估。
- 链表的空间是动态分配的，会产生内存碎片，而且每个节点都有指针域占用额外空间。顺序表虽然也基于数组，但在动态扩展等操作时也会涉及复杂的内存管理问题，不如数组简单直接用于栈的实现。
下面是使用数组实现栈的结构：
//stack.h
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
//定义栈的结构
typedef int datatype;
typedef struct Stack
{
datatype* arr;
int capacity;//栈的空间大小
int top; //栈顶
}ST;
void STInit(ST* ps); //初始化
void STDestory(ST* ps); //销毁
datatype STTop(ST* ps); //取栈顶元素
bool STEmpty(ST* ps); //判断是否为空
void STPush(ST* ps,datatype x); //插入数据
void STPop(ST* ps); //删除数据
//test.c
#define _GRT_SECURT_NO_WARNINGS 1
#include "stack.h"
void test1()
{
ST st;
STInit(&st);
STPush(&st, 1);
STPush(&st, 2);
STPush(&st, 3);
STPush(&st, 4);
//STPush(&st, 5);
//循环出栈，直到栈为空
while (!STEmpty(&st))
{
datatype data = STTop(&st);
printf("%d", data);
//出栈
STPop(&st);
}
STDestory(&st);
}
int main()
{
test1;
return 0;
}
//stack.c
#define _GRT_SECURT_NO_WARNINGS 1
#include"stack.h"
void STInit(ST* ps)//初始化
{
assert(ps);
ps->arr = NULL;
ps->capacity = ps->top = 0;
}
datatype STTop(ST* ps)//取栈顶元素
{
assert(ps);
assert(!STEmpty(ps));
return ps->arr[ps->top - 1];
}
bool STEmpty(ST* ps)//判断是否为空
{
assert(ps);
return ps->top == 0;
}
void STPush(ST* ps,datatype x) //插入数据
{
//1.判断空间是否足够
if (ps->capacity == ps->top)
{
//增容
int newcapacity = ps->capacity == 0 ? 4 : 2 * ps ->capacity;
ST* tmp = (ST*)realloc(ps->arr, newcapacity * sizeof(ST));
if (tmp == NULL)
{
perror("realloc fail");
exit(1);
}
ps->arr = tmp;
ps->capacity = newcapacity;
}
ps->arr[ps->top++] = x;
}
void STPop(ST* ps) //删除数据
{
assert(ps);
assert(!STEmpty(ps));
--ps->top;
}
void STDestory(ST* ps)//销毁
{
assert(ps);
if (ps->arr)
free(ps->arr);
ps->arr = NULL;
ps->top = ps->capacity = 0;
}
关于栈的实现呢，我们到这里差不多讲完了，跟顺序表的实现基本是一样的，但是不一样的地方同样是存在的，大家可能发现在实现栈的时候我们没有写打印数据的函数，因为栈是不能被遍历的，它只能从一端来插入或者删除数据，也就是说假如我们依次输入1 2 3 4，那么位于栈底的数字就是1，位于栈顶的数字就是4，如果我们现在要打印在栈中的数字，必须先打印4并且在打印完之后让4出栈之后，我们才能访问到下一个数字3，所以在栈中是不存在一次性遍历的。
二. 队列
2.1 概念与结构
对于队列来说，他也是一种特殊的线性表，只允许一端进行插入数据操作，另一端进行删除数据的操作，队列具有先进先出FIFO(First In First Out) ，入队列：进行插入操作的一端称为队尾，出队列：进行删除操作的一端称为队头。
//定义队列结构
//创建节点结构
typedef int qdatatype;
typedef struct queue
{
qdatatype data;
struct queue* next;
}SQNode;
struct queue
{
SQNode* phead;
SQNode* ptail;
}SQ;实现队列的全部结构功能如下:
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
//定义队列结构
//创建节点结构
typedef int qdatatype;
typedef struct QueueNode
{
qdatatype data;
struct QueueNode* next;
}SQNode;
typedef struct queue
{
SQNode* phead;//队头
SQNode* ptail;//队尾
int size;//记录队列有效的个数
}SQ;
//初始化队列
void QueueInit(SQ* pq);
//销毁队列
void SQDestroy(SQ* pq);
// ⼊队列，队尾
void SQPush(SQ* pq, qdatatype x);
// 出队列，队头
void SQPop(SQ* pq);
//取队头数据
qdatatype SQFront(SQ* pq);
//取队尾数据
qdatatype SQBack(SQ* pq);
//队列判空
bool SQEmpty(SQ* pq);
//队列有效元素个数
int SQSize(SQ* pq);
#define _GRT_SECURT_NO_WARNINGS 1
#include"queue.h"
//初始化队列
void QueueInit(SQ* pq)
{
assert(pq);
pq->phead = pq->ptail = NULL;
int size = 0;
}
//销毁队列
void SQDestroy(SQ* pq)
{
assert(pq);
assert(!SQEmpty(pq));
SQNode* pcur = pq->phead;
while (pcur)
{
SQNode* next = pcur->next;
free(pcur);
pcur = next;
}
pq->phead = pq->ptail = NULL;
pq->size = 0;
}
// 入队列，队尾
void SQPush(SQ* pq, qdatatype x)
{
assert(pq);
SQNode* newnode = (SQNode*)malloc(sizeof(SQNode));
if (newnode == NULL)
{
perror("fail");
exit(1);
}
if (pq->phead == NULL)
{
pq->phead = pq->ptail = newnode;
}
else
{
pq->ptail->next = newnode;
pq->ptail = newnode;
}
pq->size++;
}
//队列判空
bool SQEmpty(SQ* pq)
{
assert(pq);
return pq->phead = NULL && pq->ptail == NULL;
}
// 出队列，队头
void SQPop(SQ* pq)
{
assert(pq);
assert(!SQEmpty(pq));
if (pq->ptail == pq->phead)
{
free(pq->phead);
pq->phead = pq->ptail = NULL;
}
else
{
SQNode* new = pq->phead->next;
free(pq->phead);
pq->phead = new;
}
--pq->size;
}
//取队头数据
qdatatype SQFront(SQ* pq)
{
assert(pq);
assert(!SQEmpty(pq));
return pq->phead->data;
}
//取队尾数据
qdatatype SQBack(SQ* pq)
{
assert(pq);
assert(!SQEmpty(pq));
return pq->ptail->data;
}
//队列有效元素个数
int SQSize(SQ* pq)
{
assert(pq);
return pq->size;
}
#define _GRT_SECURT_NO_WARNINGS 1
#include"queue.h"
void test1()
{
SQ* q;
QueueInit(&q);
SQPush(&q, 1);
SQPush(&q, 2);
SQPush(&q, 3);
SQPush(&q, 4);
printf("head:%d\n", SQFront(&q));
printf("tail:%d\n", SQFront(&q));
}
int main()
{
test1();
return 0;
}