前言🎆

笔者也仅是大一萌新，写博客为了记录和巩固知识✨

赠人玫瑰，手留余香，欢迎各位读者进行交流和建议🥰

能与大家一起学习，一起进步是我的荣幸🌹

如果这篇文章有帮助到您，还请留个赞支持一下哦🤞

---

✨往期文章✨

🎃顺序表🎃

🎃单链表🎃

🎃双向带头循环链表🎃

目录🎆

• 栈和队列的区别

• 栈的实现

  1. 代码声明
  2. 初识化和清空
  3. 入栈和出栈
  4. 判空
  5. 栈顶元素
  6. 栈空间大小
  7. 总代码

• 队列的实现

  1. 代码声明
  2. 初始化和清空
  3. 入队出队
  4. 判空
  5. 队空间
  6. 队头队尾元素
  7. 总代码

栈和队列的区别🧐

栈:

1.栈是一种特殊的线性表，其插入和删除都是在固定的一端进行的

2.栈是后进先出

3.栈只允许在栈顶一端进行插入和删除

4.栈的插入操作叫压栈/进栈/入栈，栈的删除操作叫出栈

队列:

1.队列是一种特殊的线性表，其在一端进行插入，另一端进行删除

2.队列是先进先出

3.入队列:进行插入操作的一端称为队尾

4.出队列:进行删除操作的一端称为队头

栈的实现✔

入栈出栈示意图(上方为栈顶)

入栈:

出栈:

代码声明🔎:

#pragma once#include #include #include #include typedef int STDataType;typedef struct Stack{STDataType* a;int top;int capacity;}ST;void StackInit(ST* ps); //初始化void StackDestory(ST* ps); //清空void StackPush(ST* ps, STDataType x); //入栈void StackPop(ST* ps); //出栈bool StackEmpty(ST* ps); //判断是否为空STDataType StackTop(ST* ps); //栈顶元素

初始化和清空🔎:

void StackInit(ST* ps){assert(ps);ps->a = NULL;ps->top = 0;ps->capacity = 0;}void StackDestory(ST* ps){assert(ps);free(ps->a);ps->a = NULL;ps->capacity = ps->top = 0;}

入栈出栈🔎:

void StackPush(ST* ps, STDataType x){assert(ps);if (ps->top == ps->capacity) //扩容{int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;ps->a = realloc(ps->a, newCapacity * sizeof(STDataType));if (ps->a == NULL){printf("realloc fail\n");exit(-1);}ps->capacity = newCapacity;}ps->a[ps->top] = x;ps->top++;}void StackPop(ST* ps){assert(ps);assert(ps->top > 0);--ps->top; //栈顶元素实际是栈最后一个元素，直接--即可}

判空函数🔎:

bool StackEmpty(ST* ps){assert(ps);return ps->top == 0;}

栈顶元素🔎:

STDataType StackTop(ST* ps){assert(ps);assert(ps->top > 0); //防止越界return ps->a[ps->top - 1];}

栈空间🔎:

int StackSize(ST* ps){assert(ps);return ps->top;//栈顶就是最后一个元素，直接返回就是空间大小}

总代码🔎:

#pragma once#include #include #include #include typedef int STDataType;typedef struct Stack{STDataType* a;int top;int capacity;}ST;void StackInit(ST* ps);void StackDestory(ST* ps);void StackPush(ST* ps, STDataType x);void StackPop(ST* ps);bool StackEmpty(ST* ps);STDataType StackTop(ST* ps);

#include "Stack.h"void StackInit(ST* ps){assert(ps);ps->a = NULL;ps->top = 0;ps->capacity = 0;}void StackDestory(ST* ps){assert(ps);free(ps->a);ps->a = NULL;ps->capacity = ps->top = 0;}void StackPush(ST* ps, STDataType x){assert(ps);if (ps->top == ps->capacity){int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;ps->a = realloc(ps->a, newCapacity * sizeof(STDataType));if (ps->a == NULL){printf("realloc fail\n");exit(-1);}ps->capacity = newCapacity;}ps->a[ps->top] = x;ps->top++;}void StackPop(ST* ps){assert(ps);assert(ps->top > 0);--ps->top;}bool StackEmpty(ST* ps){assert(ps);return ps->top == 0;}STDataType StackTop(ST* ps){assert(ps);assert(ps->top > 0);return ps->a[ps->top - 1];}int StackSize(ST* ps){assert(ps);return ps->top;}

#include "Stack.h"void testStack(){ST st;StackInit(&st);StackPush(&st, 1);StackPush(&st, 2);StackPush(&st, 3);StackPush(&st, 4);while (!StackEmpty(&st)){printf("%d ", StackTop(&st));StackPop(&st);}}int main(){testStack();return 0;}

队列的实现✔

入队出队示意图：

可以想象成你做核酸，第一个排队，你就是队头，做完也是第一个出队的，最后一个要排队就先要入队，那么也就是队尾

代码声明🔎:

#include #include #include #include typedef int QDataType;typedef struct QueueNode{QDataType data;struct QueueNode* next;}QNode; //定义节点typedef struct Queue{QNode* head;QNode* tail;}Queue; //定义头尾void QueueInit(Queue* pq); //初始化void QueueDestory(Queue* pq); //清空void QueuePush(Queue* pq, QDataType x); //入队void QueuePop(Queue* pq); //出队bool QueueEmpty(Queue* pq); //判空size_t QueueSize(Queue* pq); //空间大小QDataType QueueFront(Queue* pq); //队头元素QDataType QueueBack(Queue* pq); //队尾元素

初始化和清空🔎:

void QueueInit(Queue* pq){assert(pq);pq->head = pq->tail = NULL;}void QueueDestory(Queue* pq){assert(pq);QNode* cur = pq->head;while (cur){QNode* next = cur->next;free(cur);cur = next;}pq->head = pq->tail = NULL;}

入队出队🔎:

void QueuePush(Queue* pq, QDataType x){assert(pq);QNode* newnode = (QNode*)malloc(sizeof(QNode)); //扩容newnode->data = x; //将x放入newnode->next = NULL;if (pq->tail == NULL) //当队列为空的情况{assert(pq->head == NULL);pq->head = pq->tail = newnode;}else{pq->tail->next = newnode; //插入newnodepq->tail = newnode; //更新tail}}void QueuePop(Queue* pq){assert(pq);assert(pq->head && pq->tail);if (pq->head->next == NULL) //当仅有队头{free(pq->head);pq->head = pq->tail = NULL;}else{QNode* next = pq->head->next; //储存head的下一个节点，防止丢失free(pq->head);pq->head = next;}}

判空🔎:

bool QueueEmpty(Queue* pq){assert(pq);return pq->head == NULL && pq->tail == NULL;}

队空间大小🔎:

size_t QueueSize(Queue* pq){assert(pq);QNode* cur = pq->head;size_t size = 0;while (cur){size++;cur = cur->next;}return size;}

队头队尾元素🔎:

QDataType QueueFront(Queue* pq){assert(pq);assert(pq->head);return pq->head->data; //直接返回队头队尾的data即可}QDataType QueueBack(Queue* pq){assert(pq);assert(pq->head);return pq->tail->data;}

总代码🔎:

#include #include #include #include typedef int QDataType;typedef struct QueueNode{QDataType data;struct QueueNode* next;}QNode; //定义节点typedef struct Queue{QNode* head;QNode* tail;}Queue; //定义头尾void QueueInit(Queue* pq);void QueueDestory(Queue* pq);void QueuePush(Queue* pq, QDataType x);void QueuePop(Queue* pq);bool QueueEmpty(Queue* pq);size_t QueueSize(Queue* pq);QDataType QueueFront(Queue* pq);QDataType QueueBack(Queue* pq);

#include "Queue.h"void QueueInit(Queue* pq){assert(pq);pq->head = pq->tail = NULL;}void QueueDestory(Queue* pq){assert(pq);QNode* cur = pq->head;while (cur){QNode* next = cur->next;free(cur);cur = next;}pq->head = pq->tail = NULL;}void QueuePush(Queue* pq, QDataType x){assert(pq);QNode* newnode = (QNode*)malloc(sizeof(QNode));newnode->data = x;newnode->next = NULL;if (pq->tail == NULL){assert(pq->head == NULL);pq->head = pq->tail = newnode;}else{pq->tail->next = newnode;pq->tail = newnode;}}void QueuePop(Queue* pq){assert(pq);assert(pq->head && pq->tail);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;}}bool QueueEmpty(Queue* pq){assert(pq);return pq->head == NULL && pq->tail == NULL;}size_t QueueSize(Queue* pq){assert(pq);QNode* cur = pq->head;size_t size = 0;while (cur){size++;cur = cur->next;}return size;}QDataType QueueFront(Queue* pq){assert(pq);assert(pq->head);return pq->head->data;}QDataType QueueBack(Queue* pq){assert(pq);assert(pq->head);return pq->tail->data;}

#include "Queue.h"void Test(){Queue q;QueueInit(&q);QueuePush(&q, 1);QueuePush(&q, 2);QueuePush(&q, 3);QueuePush(&q, 4);QueuePush(&q, 5);while (!QueueEmpty(&q)){printf("%d ", QueueFront(&q));QueuePop(&q);}printf("\n");}int main(){Test();return 0;}