数据结构-栈和队列
文章目录
- 栈
- 什么是栈
- 栈的操作
- 栈的特点
- 栈的实现
- 栈的时间复杂度
- 栈的应用
- 队列
- 队列的概念
- 队列的操作
- 队列的实现
- 队列的时间复杂度
栈
什么是栈
堆栈又名栈（stack），它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。
栈的操作
这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。
栈的特点
先进后出，后进先出
栈的实现
顺序栈：
一、思路
1.通过动态数组的来实现，保证数组的空间足够
2.我们要实现栈需要实现入栈和出栈等函数
3.通过结构体来存储不同数据
二、框架
Stack.h
//需要用的函数头文件
#include <stdio.h>//输入
#include <stdlib.h>//扩容
#include <assert.h>//断言
#include<stdbool.h> //判断真假
typedef int STDataType;//定义类型名
typedef struct Stack//构建结构体和定义类型名
{
STDataType* a;//指针
int top;//数组下标
int capacity;//容量
}ST;
test.c
void test() {
ST s;//结构体变量
}
三、函数实现
1.初始化函数
初始化结构体内容
void StackInit(ST* ps)//初始化
{
assert(ps);//断言
ps->a = (STDataType*)malloc(sizeof(STDataType)*4);//开始先给四个空间
ps->capacity = 4;//容量大小
ps->top = 0;//数组下标
}
ST s;
StackInit(&s);//初始化，改变内容需要用传址调用
2.入栈函数
将数据压栈到栈顶
（1）.栈底是固定的，栈顶会随着入栈变化
（2）.入栈要判断空间是否够，不够扩容
代码实现：
void StackPush(ST* ps, STDataType x) //入栈
{
assert(ps);
//先判断是否需要扩容
if (ps->capacity == ps->top) {
STDataType* p = (STDataType*)realloc(ps->a,sizeof(STDataType) * ps->capacity*2);
if (p == NULL) {//是否扩容成功
printf("reallocfail\n");
exit(-1);//终止程序
}
else {
ps->a =p;
ps->capacity = ps->capacity * 2;//更新容量大小
}
}
ps->a[ps->top] = x;//压栈
ps->top++;//元素增加
}
3.出栈函数
从栈顶出栈
代码实现：
void StackPop(ST* ps) {// 出栈
assert(ps);//断言
assert(ps->top);//断言是否有元素
ps->a[ps->top - 1] = 0;//置0
ps->top--;//元素个数减1
}
4.元素大小函数
直接放回我们记录的元素大小即可
代码实现
int StackSize(ST* ps) {//数组元素个数
assert(ps);//断言
return ps->top;//返回数组元素的个数
}
5.判断是否为空函数
通过bool类型来判断，空的话为真，否则返回假
代码实现
bool StackEmpty(ST* ps) {//判断是否为空
assert(ps);//断言
return ps->top==0;//如果top==0就返回真
}
6.释放函数
当我们不用时就将申请的空间释放
代码实现
void StackDestory(ST* ps) {//释放
assert(ps);//断言
//释放并置空
free(ps->a);
ps->a = NULL;
ps->top = 0;
ps->capacity = 0;
}
7.总代码：
Stack.h
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include<stdbool.h>
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);
STDataType StackTop(ST* ps);//出栈的元素
int StackSize(ST* ps);//返回元素个数
bool StackEmpty(ST* ps);//是否为空
Stack.c
#include"Stack.h"
void StackInit(ST* ps)//初始化
{
assert(ps);
ps->a = (STDataType*)malloc(sizeof(STDataType)*4);
ps->capacity = 4;
ps->top = 0;
}
void StackPush(ST* ps, STDataType x) //入栈
{
assert(ps);
if (ps->capacity == ps->top) {
STDataType* p = (STDataType*)realloc(ps->a,sizeof(STDataType) * ps->capacity*2);
if (p == NULL) {
printf("reallocfail\n");
exit(-1);//终止程序
}
else {
ps->a =p;
ps->capacity = ps->capacity * 2;
}
}
ps->a[ps->top] = x;
ps->top++;
}
void StackPop(ST* ps) {// 出栈
assert(ps);
assert(ps->top);
ps->a[ps->top - 1] = 0;
ps->top--;
}
STDataType StackTop(ST* ps) {//出栈的元素
assert(ps);
assert(ps->top);
return ps->a[ps->top - 1];
}
int StackSize(ST* ps) {//数组元素个数
assert(ps);
return ps->top;
}
bool StackEmpty(ST* ps) {//判断是否为空
assert(ps);
return ps->top==0;
}
void StackDestory(ST* ps) {//释放
assert(ps);
free(ps->a);
ps->a = NULL;
ps->top = 0;
ps->capacity = 0;
}
test.c
#include"Stack.h"
void test() {
ST s;
StackInit(&s);
//压栈
StackPush(&s, 1);
StackPush(&s, 2);
StackPush(&s, 3);
while (s.top) {
STDataType te = StackTop(&s);//打印出栈
StackPop(&s);
printf("%d ", te);
}
}
int main() {
test();
return 0;
}
运行结果：
先进栈的后出栈，所以先出3>2>1
栈的时间复杂度
因为每一次压栈出栈只需要进行一次操作，所以时间复杂度为O（1）
栈的应用
车厢调度问题：
分析
1.从A方向来的车厢有可能进入车站C后就留在车站C，这个过程就是我们的压栈，也有可能进入后就往B的方向行使了，这个过程就是我们的出栈。
2.因为车厢是不连接的，所以每节车厢离开的情况是不同的，有可能是进C就直接离开，也有可能停留，这样就要等其他车厢都离开后才能离开了
比如：
3.就是先要实现一个栈，再根据题目输入出栈的顺序，然后从1开始到n进行压栈，要是在压栈的过程中有与我们输入顺序相同的数据就出栈，直到压到n，再然后就是判断是否n个都符合条件出栈了，要是没有就按先进后出，后进先出的规则，来出栈与剩下输入顺序的数据对比，要是相同就继续，没有就打破，最后判断栈是否为空，为空则符合，不为空则输入顺序不符合
代码实现：
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include<stdbool.h>
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);
STDataType StackTop(ST* ps);//出栈的元素
int StackSize(ST* ps);//返回元素个数
bool StackEmpty(ST* ps);//是否为空
void StackInit(ST* ps)//初始化
{
assert(ps);
ps->a = (STDataType*)malloc(sizeof(STDataType)*4);
ps->capacity = 4;
ps->top = 0;
}
void StackPush(ST* ps, STDataType x) //入栈
{
assert(ps);
if (ps->capacity == ps->top) {
STDataType* p = (STDataType*)realloc(ps->a,sizeof(STDataType) * ps->capacity*2);
if (p == NULL) {
printf("reallocfail\n");
exit(-1);//终止程序
}
else {
ps->a =p;
ps->capacity = ps->capacity * 2;
}
}
ps->a[ps->top] = x;
ps->top++;
}
void StackPop(ST* ps) {// 出栈
assert(ps);
assert(ps->top);
ps->a[ps->top - 1] = 0;
ps->top--;
}
STDataType StackTop(ST* ps) {//出栈的元素
assert(ps);
assert(ps->top);
return ps->a[ps->top - 1];
}
int StackSize(ST* ps) {//数组元素个数
assert(ps);
return ps->top;
}
bool StackEmpty(ST* ps) {//判断是否为空
assert(ps);
return ps->top==0;
}
void StackDestory(ST* ps) {//释放
assert(ps);
free(ps->a);
ps->a = NULL;
ps->top = 0;
ps->capacity = 0;
}
//上面是栈的实现
bool test1() {
int arr[1000] = { 0 },n=0;//按照题目要求。n最大为1000
scanf("%d", &n);//车厢个数
for (int i = 0; i < n; i++)//输入出站顺序
scanf("%d", &arr[i]);
ST s;
StackInit(&s);
int j = 1;
int t = 0;
while (j <= n) {//从1开始进站
StackPush(&s, j);//压栈
if (j == arr[t]) {//相同的数据就出栈
StackPop(&s);
t++;
}
j++;
}
while (t < n) {//判断是否都出了
STDataType te = StackTop(&s);//取出栈顶的元素
if (te == arr[t]) {//对比
StackPop(&s);
t++;
}
else {
break;
}
}
bool pd=StackEmpty(&s);//判断栈是否为空
StackDestory(&s);//释放
return pd;/返回
}
int main() {
if (test1())
printf("YES\n");
else
printf("NO\n");
return 0;
}
队列
队列的概念
队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。
队列的操作
进行插入操作的端称为队尾，进行删除操作的端称为队头。
队列的实现
单链表实现:
一、思路
1.通过两个指针来实现，一个指向对头，一个指向队尾，这样方便了插入和删除
2.实现头删和尾插等函数
二、框架
Queue.h
//用到的头文件
#include <stdlib.h>
#include <stdio.h>
#include <assert.h>
#include <stdbool.h>
typedef int QDataType;//重新命名
typedef struct QueueNode
{
struct QueueNode* next;//前驱指针
QDataType data;//数据
}QNode;重新命名
typedef struct Queue
{
QNode* head;//队头的指针
QNode* tail;//队尾指针
}Queue;//重新命名
test.c
void test() {
Queue p;//结构体变量
}
三、实现函数
1.初始化函数
将结构体变量初始化
代码实现
void QueueInit(Queue* pq) {//初始化
assert(pq);//断言
pq->head = pq->tail = NULL;//将两个结构体指针都置空
}
2.插入函数
（1）先扩容
（2）从队尾插入数据
代码实现
void QueuePush(Queue* pq, QDataType x) {//队尾入
assert(pq);
QNode* p = (QNode*)malloc(sizeof(QNode));//扩容
if (p == NULL) {//判断是否成功
printf("malloc fail\n");
exit(-1);
}
p->data = x;//再新的空间加入数据
p->next = NULL;
//判断是否是没有数据
if (pq->tail == NULL)
pq->head = pq->tail = p;
else {
pq->tail->next = p;
pq->tail = p;
}
}
3.删除数据函数
分为只有1个数据和有多个数据
代码实现
void QueuePop(Queue* pq) {
assert(pq);
//一个
if (pq->head->next == NULL) {
free(pq->head);//只有一个数据随便释放一个队头或者队尾都行，并置空
pq->head = pq->tail == NULL;
}
//多个
//
else {
Queue* p = pq->head->next;//先保存下一个结点，在释放队头
free(pq->head);
pq->head = NULL;
pq->head = p;//换队头
}
}
4.取出队头函数
我们直接利用队头指针去放回数据即可
代码实现
QDataType QueueFront(Queue* pq) {
assert(pq);
assert(pq->head);//队头不能为空
return pq->head->data;//取数据
}
5.计算队列大小函数
（1）设置一个计算变量
（2）为了队头不变。先将队头复制，再通过遍历迭代到队尾
int QueueSize(Queue* pq) {
assert(pq);
assert(pq->tail);
int n = 0;//计数器
QNode* p = pq->head;//复制
while (p)
{
n++;
p = p->next;//迭代
}
return n;//返回计算器
}
6.判断队列是否为空
我们只需要判断队头即可，对头为空，则队列为空
bool QueueEmpty(Queue* pq) {
assert(pq);
return pq->head==NULL;
}
7.释放函数
（1）.我们通过队头找到下一个结点，再释放队头
（2）.通过迭代方式实现逐个释放，并最后要将队头和队尾都释放
void QueueDestory(Queue* pq) {
assert(pq);
while (pq->head) {
QNode* p = pq->head->next;
free(pq->head);
pq->head = NULL;
pq->head = p;//迭代
}
pq->head = pq->tail = NULL;//队头和队尾都释放
}
8.总代码：
Queue.h
#include <stdlib.h>
#include <stdio.h>
#include <assert.h>
#include <stdbool.h>
typedef int QDataType;
typedef struct QueueNode
{
struct QueueNode* next;
QDataType data;
}QNode;
typedef struct Queue
{
QNode* head;
QNode* tail;
}Queue;
void QueueInit(Queue* pq);
void QueueDestory(Queue* pq);
// 队头出
void QueuePop(Queue* pq);
QDataType QueueFront(Queue* pq);//头出
QDataType QueueBack(Queue* pq);//尾出
int QueueSize(Queue* pq);//个数
bool QueueEmpty(Queue* pq);//是否为空
Queue.c
#include"Queue.h"
void QueueInit(Queue* pq) {//初始化
assert(pq);
pq->head = pq->tail = NULL;
}
void QueuePush(Queue* pq, QDataType x) {//队尾入
assert(pq);
QNode* p = (QNode*)malloc(sizeof(QNode));
if (p == NULL) {
printf("malloc fail\n");
exit(-1);
}
p->data = x;
p->next = NULL;
if (pq->tail == NULL)
pq->head = pq->tail = p;
else {
pq->tail->next = p;
pq->tail = p;
}
}
void QueuePop(Queue* pq) {
assert(pq);
//一个
if (pq->head->next == NULL) {
free(pq->head);
pq->head = pq->tail == NULL;
}
//多个
else {
Queue* p = pq->head->next;
free(pq->head);
pq->head = NULL;
pq->head = p;
}
}
QDataType QueueFront(Queue* pq) {
assert(pq);
assert(pq->head);
return pq->head->data;
}
int QueueSize(Queue* pq) {
assert(pq);
assert(pq->tail);
int n = 0;
QNode* p = pq->head;
while (p)
{
n++;
p = p->next;
}
return n;
}
bool QueueEmpty(Queue* pq) {
assert(pq);
return pq->head==NULL;
}
void QueueDestory(Queue* pq) {
assert(pq);
while (pq->head) {
QNode* p = pq->head->next;
free(pq->head);
pq->head = NULL;
pq->head = p;
}
pq->head = pq->tail = NULL;
}
test.c
#include"Queue.h"
void test() {
Queue p;
QueueInit(&p);
QueuePush(&p,1);//插
QueuePush(&p, 2);
QueuePush(&p, 3);
while (p.head) {//打印数据
QDataType te=QueueFront(&p);
QueuePop(&p);//删
printf("%d ", te);
}
}
int main() {
test();
return 0;
}
根据代码来运行：
队列的时间复杂度
队列的操作过程（插和删）中的时间复杂度都为O（1）
以上就是我的分享了，如果有什么错误，欢迎在评论区留言。
最后，谢谢大家的观看！