【数据结构】栈和队列(及其实现)

发布于:2022-11-16 ⋅ 阅读:(11) ⋅ 点赞:(0) ⋅ 评论:(0)

1、栈

1.1栈的概念

栈:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶,另一端称为栈底。栈中的数据元素遵守后进先出LIFO(Last In First Out)的原则。
压栈:栈的插入操作叫做进栈/压栈/入栈,入数据在栈顶
出栈:栈的删除操作叫做出栈。出数据也在栈顶
在这里插入图片描述

1.2栈的实现

栈的实现一般可以使用数组或者链表实现,相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。
栈的实现还是分为三部分:
1️⃣Stack.c 栈功能的实现。
2️⃣Stack.h 结构体的创建,头文件的包含,函数的声明。
3️⃣test.c 进行测试栈的各项功能。

Stack.c
#define _CRT_SECURE_NO_WARNINGS 1

#include"Stack.h"

void StackInit(ST* ps)
{//对栈进行初始化
	assert(ps);
	ps->a = (STDatatype*)malloc(sizeof(STDatatype) * 4);
	//开始先创建四个整型的空间
	if (ps->a == NULL)
	{//必须要进行是否开辟成功的判断!
		perror("malloc");
		exit(-1);
	}

	ps->top = 0;//初始化为零
	ps->capacity = 4;//开辟空间时开了四个整型空间,所以初始化时的容量为四。
}

void StackPush(ST* ps, STDatatype x)
{//将数据进行入栈
	assert(ps);
	if (ps->top == ps->capacity)
	{//判断是否需要扩容
		STDatatype* prev = (STDatatype*)realloc(ps->a, sizeof(STDatatype) * ps->capacity * 2);
		//这里扩容就直接扩容为原来的二倍
		if (prev == NULL)
		{//必须判断时候开辟成功
			perror("relloc");
			exit(-1);
		}
		ps->a = prev;
		ps->capacity *= 2;
	}
	ps->a[ps->top] = x;把数据进行入栈
	ps->top++;
}

void StackPop(ST* ps)
{//出栈
	assert(ps);
	assert(!StackEmpty(ps));
	//当top为零时,也就是该函数true时,不能在进行出栈的操作
	ps->top--;
}
void StackDestroy(ST* ps)
{//销毁栈,并释放空间
	assert(ps);

	free(ps->a);
	ps->a = NULL;
	ps->top = ps->capacity = 0;
}

STDatatype StackTop(ST* ps)
{//找到栈顶
	assert(ps);
	assert(!StackEmpty(ps));
	当top为零时,也就是该函数true时,不能在进行出栈的操作
	return ps->a[ps->top - 1];
	因为top指向的是栈顶的下一个位置,所以,在查找栈顶是需要进行减一
}

bool StackEmpty(ST* ps)
{//判断栈中是否为空
	assert(ps);

	/*if (ps->top == 0)
	{
		return true;
	}
	else
	{
		return false;
	}*/

	return ps->top == 0;
	//和上面注释的代码作用是一样的,下面的更简洁,上面的可读性更强
}

int StackSize(ST* ps)
{//用来计算一共有多少数据的
	assert(ps);
	return ps->top;
}
Stack.h
#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include <stdbool.h>
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>

typedef int STDatatype;
typedef struct Stack
{
	STDatatype* a;
	int capacity;
	int top;   // 初始为0,表示栈顶位置下一个位置下标
}ST;

void StackInit(ST* ps);//初始化栈
void StackDestroy(ST* ps);//销毁栈
void StackPush(ST* ps, STDatatype x);//入栈
void StackPop(ST* ps);//出栈
STDatatype StackTop(ST* ps);//栈顶数据

bool StackEmpty(ST* ps);//栈是否为空
int StackSize(ST* ps);//栈中数据的个数
test.c
#include"Stack.h"

void TestStack1()
{
	ST st;
	StackInit(&st);
	StackPush(&st, 1);
	StackPush(&st, 2);
	StackPush(&st, 3);
	StackPush(&st, 4);
	StackPush(&st, 5);

	printf("size:%d\n", StackSize(&st));

	StackPop(&st);
	StackPop(&st);
	StackPop(&st);
	StackPop(&st);
	StackPop(&st);
	StackDestroy(&st);
}

int main()
{
	TestStack1();

	return 0;
}

2、队列

2.1队列的概念

队列:只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先进先出FIFO(First In First Out) 入队列:进行插入操作的一端称为队尾 出队列:进行删除操作的一端称为队头。
在这里插入图片描述

2.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);
	QNode* cur = pq->head;
	while (cur)
	{
		QNode* prev = cur;
		cur = cur->next;
		free(prev);
	}
	pq->head = NULL;
	pq->tail = NULL;
	pq->size = 0;
}
//在队尾插入数据
//这里的size是用来记录在队列当中数据的个数的。
void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc");
		exit(-1);
	}
	if (pq->head == NULL)
	{
		pq->head = pq->tail = newnode;
	}
	else
	{
		pq->tail->next = newnode;
		pq->tail = newnode;
	}
	pq->size++;
	newnode->data = x;
	newnode->next = NULL;
}
//在队头删除数据
void QueuePop(Queue* pq)
{
	assert(pq);
	//这里需要判断一下队列是否为空
	//当为空时并不能在删除数据
	assert(!QueueEmpty(pq));
	if (pq->head->next == NULL)
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	else
	{
		QNode* prev = pq->head;
		pq->head = pq->head->next;
		free(prev);
	}
	pq->size--;
}

//用来判断队列是否为空。
//通过下面的两种方法是都可以的,一种是通过size
//另一种是对队头队尾进行判断
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	if (pq->size == 0)
	{
		return true;
	}
	return false;
	//return pq->head == NULL && pq->tail == NULL;
}
//返回队头数据
QDataType QueueFront(Queue* pq)
{
	assert(pq);
	//这里需要判断一下队列是否为空
	assert(!QueueEmpty(pq));
	return pq->head->data;
}
//返回队尾数据
QDataType QueueBack(Queue* pq)
{
	assert(pq);
	//这里需要判断一下队列是否为空
	assert(!QueueEmpty(pq));
	return pq->tail->data;
}
//返回队列中数据的个数。
int QueueSize(Queue* pq)
{
	return pq->size;
}
Queue.h
#define _CRT_SECURE_NO_WARNINGS 1

#pragma once
#include <stdbool.h>
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>

typedef int QDataType;
typedef struct QueueNode
{
	QDataType data;
	struct QueueNode* next;
}QNode;

typedef struct Queue
{
	QNode* head;
	QNode* tail;
	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);
test.c

对队列的各项功能进行测试。

#define _CRT_SECURE_NO_WARNINGS 1

#include"Queue.h"
int main()
{
	Queue pq;
	QueueInit(&pq);
	QueuePush(&pq, 1);
	QueuePush(&pq, 2);
	QueuePush(&pq, 3);
	QueuePush(&pq, 4);
	QueuePush(&pq, 5);
	QueuePush(&pq, 6);
	/*QNode* cur = pq.head;
	while (cur)
	{
		printf("%d ", cur->data);
		cur = cur->next;
	}*/
	QueuePop(&pq);
	QueuePop(&pq);
	QueuePop(&pq);
	QueuePop(&pq);
	QueuePop(&pq);
	//QueuePop(&pq);
	printf("\n%d", QueueSize(&pq));
	QNode* cur = pq.head;
	while (cur)
	{
		printf("%d ", cur->data);
		cur = cur->next;
	}
	printf("%d", QueueFront(&pq));
	printf("%d", QueueBack(&pq));
	QueueDestroy(&pq);
	return 0;
}
最后:文章有什么不对的地方或者有什么更好的写法欢迎大家在评论区指出