本文主要是介绍数据结构-＞手把手教入门栈与列队（基础），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
✅作者简介：大家好，我是橘橙黄又青，一个想要与大家共同进步的男人😉😉
🍎个人主页：橘橙黄又青-CSDN博客
1.什么是栈
1.1栈的概念及结构
栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除 操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out） 的原则。
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据也在栈顶。
这种结构类似于弹夹：遵守后进先出的原则
1.2栈的实现
栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上 插入数据的代价比较小。
2.栈的实现
这里我们讲解数组（顺序表）实现
2.1栈的初始化和销毁
这里顺序表一样，a是数组，free是释放一块连续的空间。
2.2栈的节点创建
这里注意的是创建后，记得top++；
2.3出栈和返回栈顶元素
2.4返回栈的数据个数和判断栈为空
2.5测试代码：
这里我们讲一个点，我们只创建一个栈Stack s，如果要创建两个栈，最好使用结构体包装起来，比如说：
这样就可以直接创建两个顺序表了。
3.什么是列队
3.1队列的概念及结构
列队列队其实可以理解为排队
队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先 进先出FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾 出队列：进行删除操作的一 端称为队头。
4.列队的实现
队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构， 出队列在数组头上出数据，效率会比较低。
所以我们选择链表实现。
4.1列队初始化和销毁
4.2入队列
4.3出队列
出队列是链表的头删操作。
4.4找到列队头尾
4.5列队判断为空和数据个数
5.代码
5.1列队代码：
Queue.h
#pragma once
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>typedef int QDataType;
typedef struct QueueNode
{int val;struct QueueNode* next;
}QNode;入队列
//void QueuePush(QNode** pphead, QNode** pptail);出队列
//void QueuePop(QNode** pphead, QNode** pptail);typedef struct Queue
{QNode* phead;QNode* ptail;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);Queue.c
#include"Queue.h"
//初始化
void QueueInit(Queue* pq)
{assert(pq);pq->phead = NULL;pq->ptail = NULL;pq->size = 0;
}void QueueDestroy(Queue* pq)
{assert(pq);QNode* cur = pq->phead;while (cur){QNode* next = cur->next;free(cur);cur = next;}pq->phead = pq->ptail = NULL;pq->size = 0;
}// 入队列
void QueuePush(Queue* pq, QDataType x)
{assert(pq);QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc fail");return;}newnode->val = x;newnode->next = NULL;if (pq->ptail){pq->ptail->next = newnode;pq->ptail = newnode;}else{pq->phead = pq->ptail = newnode;}pq->size++;
}// 出队列
void QueuePop(Queue* pq)
{assert(pq);// 0个节点// 温柔检查//if (pq->phead == NULL)// return;// 暴力检查 assert(pq->phead != NULL);// 一个节点// 多个节点if (pq->phead->next == NULL){free(pq->phead);pq->phead = pq->ptail = NULL;}else{QNode* next = pq->phead->next;free(pq->phead);pq->phead = next;}pq->size--;
}
//返回队列头
QDataType QueueFront(Queue* pq)
{assert(pq);// 暴力检查 assert(pq->phead != NULL);return pq->phead->val;
}
//返回队列尾
QDataType QueueBack(Queue* pq)
{assert(pq);// 暴力检查 assert(pq->ptail != NULL);return pq->ptail->val;
}bool QueueEmpty(Queue* pq)
{assert(pq);return pq->size == 0;
}int QueueSize(Queue* pq)
{assert(pq);return pq->size;
}
Test.c
//队列，链表实现
#include"Queue.h"int main()
{Queue q;QueueInit(&q);QueuePush(&q, 1);QueuePush(&q, 2);printf("%d ", QueueFront(&q));QueuePop(&q);QueuePush(&q, 3);QueuePush(&q, 4);while (!QueueEmpty(&q)){printf("%d ", QueueFront(&q));QueuePop(&q);}QueueDestroy(&q);return 0;
}5.1栈代码：
Stack.h
#pragma once#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>//方便以后改数据类型
typedef int STDataType;
//顺序表
typedef struct Stack
{STDataType* a;int top;int capacity;
}Stack;//初始化
void STInit(Stack* ps);//栈销毁
void STDestroy(Stack* ps);//进栈
void STPush(Stack* ps, STDataType x);//出栈
void STPop(Stack* ps);//出栈顶元素
STDataType STTop(Stack* ps);//链表数据个数
int STSize(Stack* ps);//判断链表为不为空
bool STEmpty(Stack* ps);
Stack.c
#include"Stack.h"void STInit(Stack* ps)
{assert(ps);ps->a = NULL;ps->top = 0;ps->capacity = 0;
}void STDestroy(Stack* ps)
{assert(ps);free(ps->a);ps->a = NULL;ps->top = ps->capacity = 0;
}void STPush(Stack* ps, STDataType x)
{assert(ps);if (ps->top == ps->capacity){int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;STDataType* tmp = (STDataType*)realloc(ps->a, newcapacity * sizeof(STDataType));if (tmp == NULL){perror("realloc fail");return;}ps->a = tmp;ps->capacity = newcapacity;}ps->a[ps->top] = x;ps->top++;
}void STPop(Stack* ps)
{assert(ps);assert(!STEmpty(ps));ps->top--;
}STDataType STTop(Stack* ps)
{assert(ps);assert(!STEmpty(ps));return ps->a[ps->top - 1];
}int STSize(Stack* ps)
{assert(ps);return ps->top;
}bool STEmpty(Stack* ps)
{assert(ps);return ps->top == 0;
}Test.c
//栈，顺序表实现#include"Stack.h"int main()
{Stack s;STInit(&s);STPush(&s, 1);STPush(&s, 2);STPush(&s, 3);int top = STTop(&s);printf("%d ", top);STPop(&s);top = STTop(&s);printf("%d ", top);STPop(&s);STPush(&s, 4);STPush(&s, 5);while (!STEmpty(&s)){int top = STTop(&s);printf("%d ", top);STPop(&s);}STDestroy(&s);return 0;
}今天的分享就到这里了，点个赞，谢谢。
这篇关于数据结构-＞手把手教入门栈与列队（基础）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
