【数据结构与算法篇】栈和队列
🥕个人主页：开敲🍉
🔥所属专栏：数据结构与算法🍅
🌼文章目录🌼
1. 栈
1.1 栈的概念
栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除操作。进行数据插入和删除的一端称为栈顶，另一端则称为栈底。栈中的元素遵循后进先出的原则(LIFO:Last in First Out)。
压栈：栈的插入元素称为压栈，进入的数据存放在栈顶
出栈：栈的删除元素称为出栈，从栈顶开始删除元素
1.2 栈的实现
栈的实现一般可以用数组或者链表，相对而言数组的结构实现更优一些，因为在数组尾部插入数据较链表而言容易一些。
// 对于定长的静态栈的结构，实际中一般不实用，所以我们主要实现下面的支持动态增长的栈，以下是.h文件中声明的函数
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
typedef int STDataType;//栈结构体
typedef struct Stack
{
STDataType* arr;
int top;
int capacity;
}ST;
//初始化栈
void StackInit(ST* st);
//释放栈
void StackRelease(ST* st);
//判空
bool StackEmpty(ST* st);//入栈
void StackPush(ST* st);
//出栈
void StackPop(ST* st);
//栈顶
STDataType StackTop(ST* st);
//以下是.c文件中实现的函数
#include "Stack.h"
//初始化栈
void StackInit(ST* st)
{
assert(st);
st->arr = NULL;
st->capacity = st->top = 0;
}
//释放栈
void StackRelease(ST* st)
{
assert(st);
free(st->arr);
st->arr = NULL;
st->capacity = st->top = 0;
}
//判空
bool StackEmpty(ST* st)//判空只需要判断栈中元素是否为0即可
{
assert(st);
return st->top == 0;
}//入栈
void StackPush(ST* st, STDataType x)
{
assert(st);
if (st->top == st->capacity)//判断栈空间是否足够
{
int newcapacity = st->capacity == 0 ? 4 : 2 * st->capacity;
STDataType* tmp = (STDataType*)realloc(st->arr,sizeof(STDataType) * newcapacity);
if (tmp == NULL)
{
perror("realloc:");
exit(-1);
}
st->arr = tmp;
st->capacity = newcapacity;
}
st->arr[st->top] = x;//将元素入栈
st->top++;
}
//出栈
void StackPop(ST* st)
{
assert(st);
assert(st->top > 0);
st->top--;//出栈直接将top--
}//获取栈顶元素
STDataType StackTop(ST* st)
{
assert(st);
assert(st->top > 0);
return st->arr[st->top - 1];
}
2. 队列
2.1 队列的概念及结构
队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out)的特性。
入队列：进行插入操作的一端称为队尾
出队列：进行删除操作的一端称为队头
2.2 队列的实现
队列可以用数组或链表的结构实现，使用链表的结构更优一些，因为如果使用数组的结构，出队列在数组头部出数据，还需要挪动后面的数据，效率会比较低。
//以下为.h头文件队列的声明
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
typedef int QDataType;
//队列节点
typedef struct ListNode
{
QDataType val;
struct ListNode* next;
}LN;
//队列头尾指针
typedef struct Queque
{
LN* phead;
LN* ptail;
int size;
}QE;
//队列初始化
void QueInit(QE* qe);
//入列
void QuePush(QE* qe, QDataType x);//出列
void QuePop(QE* qe);
//获取列头元素
QDataType QueGetHead(QE* qe);
//获取列尾元素
QDataType QueGetBack(QE* qe);
//获取队列元素个数
int QueSize(QE* qe);
//判断队列是否为空
bool QueEmpty(QE* qe);//释放队列
void QueRelease(QE* qe);
//以下为队列.c源文件队列的实现
//队列初始化
void QueInit(QE* qe)
{
assert(qe);
qe->phead = NULL;
qe->ptail = NULL;
qe->size = 0;
}
//入列
void QuePush(QE* qe, QDataType x)
{
assert(qe);
LN* newnode = (LN*)malloc(sizeof(LN));
if (newnode == NULL)
{
perror("malloc:");
exit(-1);
}
newnode->next = NULL;
newnode->val = x;
if (qe->phead == NULL)
{
qe->phead = qe->ptail = newnode;
}
else
{
qe->ptail->next = newnode;
qe->ptail = qe->ptail->next;
}
qe->size++;
}
//出列
void QuePop(QE* qe)
{
assert(qe);
assert(qe->phead != NULL);
assert(qe->size > 0);
LN* tmp = qe->phead->next;
free(qe->phead);
qe->phead = tmp;
qe->size--;
}
//获取列头元素
QDataType QueGetHead(QE* qe)
{
assert(qe);
assert(qe->phead != NULL);
return qe->phead->val;
}//获取列尾元素
QDataType QueGetBack(QE* qe)
{
assert(qe);
assert(qe->ptail != NULL);
return qe->ptail->val;
}//获取队列元素个数
int QueSize(QE* qe)
{
assert(qe);
return qe->size;
}//判断队列是否为空
bool QueEmpty(QE* qe)
{
assert(qe);
return qe->size == 0;
}
//释放队列
void QueRelease(QE* qe)
{
assert(qe);
while (qe->phead)
{
LN* tmp = qe->phead->next;
free(qe->phead);
qe->phead = tmp;
}
qe->ptail = NULL;
qe->size = 0;
free(qe);
qe = NULL;
}
