一、栈

1.1 什么是栈？

栈 (Stack)是一种线性存储结构，它具有如下特点： 栈中的数据元素遵守”后进先出” (First In Last Out)的原则，简称FILO结构。 限定只能在栈顶进行插入和删除操作。
栈顶与栈底：允许元素插入与删除的一端称为栈顶，另一端称为栈底。栈可以用动态数组的方式实现，也可以用链表来实现。以下是用动态数组的方式模拟实现栈。

1.2 栈的相关操作

1.2.1 结构体变量的声明

typedef int StackDataType;typedef struct Stack
{//这里就是一个指向动态开辟内存的指针即可//和顺序表一个道理StackDataType* a;//top记录栈顶位置，top的初始值为0或者-1取决于//设计者设计top位置是栈顶元素的位置(top=-1)//还是栈顶元素位置的下一个(top=0)。int top;//capacity是栈的容量，容量不够就增容int capacity;
}ST;

1.2.2 栈的初始化

void STInit(ST* st)
{assert(st);//开辟空间st->a = (StackDataType*)malloc(sizeof(StackDataType) * 4);if (st->a == NULL){perror("malloc fail");return;}st->capacity = 4;//st->top=0代表top是栈顶元素的下一个位置的下标而并非栈顶元素的下标st->top = 0;
}

1.2.3 栈的销毁

void STDestroy(ST* st)
{assert(st);free(st->a);st->a = NULL;st->capacity = 0;st->top = 0;}

1.2.4 元素入栈

void STPush(ST* st, StackDataType x)
{assert(st);if (st->capacity == st->top){//增容StackDataType* tmp = (StackDataType*)realloc(st->a, sizeof(StackDataType) * (st->capacity * 2));if (tmp == NULL){perror("realloc fail");return;}st->a = tmp;st->capacity *= 2;}//top位置是栈顶元素位置的下一个，所以直接把x入栈到top下标的位置st->a[st->top] = x;st->top++;}

1.2.5 元素出栈

void STPop(ST* st)
{//出栈的条件之一是栈内必须有数据//所以不能为空assert(st && !STEmpty(st));//直接top--即可st->top--;
}

1.2.6 取栈顶元素

StackDataType STTop(ST* st)
{assert(st);//要取元素，栈不能为空assert(!STEmpty(st));//由于top是栈顶的下一个位置的下标，所以需要返回top-1位置的元素return st->a[st->top - 1];
}

1.2.7 求栈顶元素的数目

size_t STSize(ST* st)
{assert(st);//由于top是有0开始的，插入一个数据就+1//所以插入了多少个数据top就是多少，所以直接返回top的大小即可return st->top;
}

1.2.8 判断栈是否为空

bool STEmpty(ST* st)
{assert(st);//如果top==0，证明栈内无数据，//栈为空，st->top==0的逻辑结果true，直接返回即可return st->top == 0;
}

1.3 栈的代码汇总

1.3.1 Stack.h

#pragma once#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>typedef int StackDataType;typedef struct Stack
{StackDataType* a;int top;int capacity;
}ST;extern void STInit(ST* st);
extern void STDestroy(ST* st);
extern void STPush(ST* st, StackDataType x);
extern void STPop(ST* st);
extern StackDataType STTop(ST* st);
extern size_t STSize(ST* st);
extern bool STEmpty(ST* st);

1.3.2 Stack.c

#define _CRT_SECURE_NO_WARNINGS 1#include "Stack.h"void STInit(ST* st)
{assert(st);//开辟空间st->a = (StackDataType*)malloc(sizeof(StackDataType) * 4);if (st->a == NULL){perror("malloc fail");return;}st->capacity = 4;//st->top=0代表top是栈顶元素的下一个的位置的下标而并非栈顶元素的下标st->top = 0;
}void STDestroy(ST* st)
{assert(st);free(st->a);st->a = NULL;st->capacity = 0;st->top = 0;}void STPush(ST* st, StackDataType x)
{assert(st);if (st->capacity == st->top){//增容StackDataType* tmp = (StackDataType*)realloc(st->a, sizeof(StackDataType) * (st->capacity * 2));if (tmp == NULL){perror("realloc fail");return;}st->a = tmp;st->capacity *= 2;}//top位置是栈顶元素位置的下一个，所以直接把x入栈到top下标的位置st->a[st->top] = x;st->top++;}void STPop(ST* st)
{assert(st && !STEmpty(st));//直接top--即可st->top--;
}StackDataType STTop(ST* st)
{assert(st);//要取元素，栈不能为空assert(!STEmpty(st));//由于top是栈顶的下一个位置的下标，所以需要返回top-1位置的元素return st->a[st->top - 1];
}size_t STSize(ST* st)
{assert(st);//由于top是有0开始的，插入一个数据就+1//所以插入了多少个数据top就是多少，所以直接返回top的大小即可return st->top;
}bool STEmpty(ST* st)
{assert(st);//如果top==0，证明栈内无数据，//栈为空，st->top==0的逻辑结果true，直接返回即可return st->top == 0;
}

1.3.3 test.c

#define _CRT_SECURE_NO_WARNINGS 1#include "Stack.h"int main()
{ST st;STInit(&st);STPush(&st, 1);STPush(&st, 2);STPush(&st, 3);STPush(&st, 4);STPush(&st, 5);while (!STEmpty(&st)){printf("%d ", STTop(&st));STPop(&st);}printf("\\n");STDestroy(&st);return 0;
}

二、队列

2.1 什么是队列？

队列(Queue)也是一种线性的存储结构，它具有如下特点： 队列中的数据元素遵守”先进先出” (First In First Out)的原则，简称FIFO结构。 限定只能在队列的尾部进行插入数据，头部进行删除数据。
队列适合用单链表实现，因为单链表头删和尾插的时间复杂度是O(1)的，效率很高。

2.2 队列相关操作

2.2.1 结构体变量的声明

typedef int QNodeDataType;//队列的每一个元素是一个结构体
typedef struct QueueNode
{//每一个结点内都存着下一个结点的指针(地址)struct QueueNode* next;//结点的有效数据QNodeDataType data;}QNode;typedef struct Queue
{//队列最好定义一个指向头节点的指针和//一个指向尾节点的指针，方便头删和尾插，提高效率QNode* head;QNode* tail;//记录队列一共有多少个结点，每插入一个结点就+1int size;}Queue;

2.2.2 队列的初始化

void QueueInit(Queue* pq)
{assert(pq);//空队列的头和尾指针都要指向NULLpq->head = NULL;pq->tail = NULL;pq->size = 0;}

2.2.3 队列的销毁

void QueueDestroy(Queue* pq)
{assert(pq);//由于每一个结点都是malloc出来的，所以//需要遍历逐一释放队列内的结点，防止内存泄露QNode* cur = pq->head;while (cur){//先保存需要释放的结点del，释放后cur迭代地走下去//直到cur为空就全部释放完了QNode* del = cur;cur = cur->next;free(del);del = NULL;}pq->head = NULL;pq->tail = NULL;pq->size = 0;
}

2.2.4 队列的插入

void QueuePush(Queue* pq, QNodeDataType x)
{assert(pq);//申请结点QNode* newNode = (QNode*)malloc(sizeof(QNode));if (newNode == NULL){perror("");return;}newNode->data = x;newNode->next = NULL;//第一次插入时由于队列为空，所以pq->head和pq->tail//都为空，则应该直接赋值结点的结构体给p->head和pq->tail//如果直接pq->tail->next = newNode程序会崩的，因为pq->tail为空//不能访问if (pq->head == NULL){pq->head = pq->tail = newNode;}else{//插入到尾部pq->tail->next = newNode;//newNode更新为新的尾结点pq->tail = newNode;}//队列的数据数目+1pq->size++;
}

2.2.5 队列的删除

void QueuePop(Queue* pq)
{assert(pq);//删除的前提是不能队列为空assert(!QueueEmpty(pq));//如果只有一个结点的话，那删掉这个结点//同时把尾指针要置为NULL，不置空的话//尾指针就是一个野指针，存在越界访问的风险if (pq->head->next == NULL){free(pq->head);pq->head = pq->tail = NULL;}else{//先保存下一个结点的地址，再释放当前的结点QNode* next = pq->head->next;free(pq->head);pq->head = next;}//数目-1pq->size--;}

2.2.6 队列元素的数目

int QueueSize(Queue* pq)
{assert(pq);return pq->size;
}

2.2.7 判断队列是否为空

bool QueueEmpty(Queue* pq)
{assert(pq);return pq->size == 0;
}

2.2.8 取队列头部的元素

QNodeDataType QueueFront(Queue* pq)
{assert(pq);//取元素的前提是队列不能为空assert(!QueueEmpty(pq));return pq->head->data;
}

2.2.9 取队列尾部的元素

QNodeDataType QueueBack(Queue* pq)
{assert(pq);//取元素的前提是队列不能为空assert(!QueueEmpty(pq));return pq->tail->data;}

2.3 队列的代码汇总

2.3.1 Queue.h

#pragma once#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>typedef int QNodeDataType;typedef struct QueueNode
{struct QueueNode* next;QNodeDataType data;}QNode;typedef struct Queue
{QNode* head;QNode* tail;int size;}Queue;extern void QueueInit(Queue* pq);
extern void QueueDestroy(Queue* pq);
extern void QueuePush(Queue* pq, QNodeDataType x);
extern void QueuePop(Queue* pq);
extern int QueueSize(Queue* pq);
extern bool QueueEmpty(Queue* pq);
extern QNodeDataType QueueFront(Queue* pq);
extern QNodeDataType QueueBack(Queue* pq);

2.3.2 Queue.c

#define _CRT_SECURE_NO_WARNINGS 1#include "Queue.h"void QueueInit(Queue* pq)
{assert(pq);pq->head = NULL;pq->tail = NULL;pq->size = 0;}void QueueDestroy(Queue* pq)
{assert(pq);//由于每一个结点都是malloc出来的，所以//需要遍历逐一释放队列内的结点，防止内存泄露QNode* cur = pq->head;while (cur){//先保存需要释放的结点del，释放后cur迭代地走下去//直到cur为空就全部释放完了QNode* del = cur;cur = cur->next;free(del);del = NULL;}pq->head = NULL;pq->tail = NULL;pq->size = 0;
}void QueuePush(Queue* pq, QNodeDataType x)
{assert(pq);//申请结点QNode* newNode = (QNode*)malloc(sizeof(QNode));if (newNode == NULL){perror("");return;}newNode->data = x;newNode->next = NULL;//第一次插入时由于队列为空，所以pq->head和pq->tail//都为空，则应该直接赋值结点的结构体给p->head和pq->tail//如果直接pq->tail->next = newNode程序会崩的，因为pq->tail为空//不能访问if (pq->head == NULL){pq->head = pq->tail = newNode;}else{//插入到尾部pq->tail->next = newNode;//newNode更新为新的尾结点pq->tail = newNode;}//队列的数据数目+1pq->size++;
}void QueuePop(Queue* pq)
{assert(pq);//删除的前提是不能队列为空assert(!QueueEmpty(pq));//如果只有一个结点的话，那删掉这个结点//同时把尾指针要置为NULL，不置空的话//尾指针就是一个野指针，存在越界访问的风险if (pq->head->next == NULL){free(pq->head);pq->head = pq->tail = NULL;}else{//先保存下一个结点的地址，再释放当前的结点QNode* next = pq->head->next;free(pq->head);pq->head = next;}//数目-1pq->size--;}int QueueSize(Queue* pq)
{assert(pq);return pq->size;
}bool QueueEmpty(Queue* pq)
{assert(pq);return pq->size == 0;
}QNodeDataType QueueFront(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->head->data;
}QNodeDataType QueueBack(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->tail->data;}

2.3.3 test.c

#define _CRT_SECURE_NO_WARNINGS 1#include "Queue.h"int main()
{Queue q;QueueInit(&q);QueuePush(&q, 1);QueuePush(&q, 2);QueuePush(&q, 3);QueuePush(&q, 4);QueuePush(&q, 5);/*printf("%d ", QueueFront(&q));QueuePop(&q);printf("%d ", QueueFront(&q));QueuePop(&q);*/while (!QueueEmpty(&q)){printf("QueueFront:%d ", QueueFront(&q));printf("size = %d\\n", QueueSize(&q));QueuePop(&q);}QueueDestroy(&q);return 0;
}

以上就是用C语言实现栈和队列的所有内容，你学会了吗？喜欢的在评论区留下一颗小心心点点关注呗！！！