当前位置：首页 > article >正文

数据结构栈和队列

article 2024/11/14 11:22:41

1. 栈

1.1 栈的概念及结构

栈是线性表的一种，这种数据结构只允许在固定的一端进行插入和删除元素的操作，进行数据插入和删除的一端称为栈顶，另一端称为栈底。

这种数据结构的操作方式可以类比为弹匣，存取子弹只能在固定的一端（图源网络，侵删）
在这里插入图片描述

栈对应的两个操作：

压栈：栈的插入操作，又叫进栈/压栈/入栈，插入的数据在栈顶。
出栈：栈的删除操作，删除的数据同样在栈顶。

栈中的数据元素遵守后进先出LIFO(Last In First Out)的原则
在这里插入图片描述

1.2 栈的实现

下面我们通过c语言来实现栈的结构以及相关操作。

实现栈的结构，我们可以通过顺序表或链表来实现，相对而言通过顺序表实现更好一些，因为顺序表对于尾部的操作效率更高一些。

对于栈我们提供出栈、入栈、判空等接口，下面来看具体代码：

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef int STDataType;

//通过顺序表来实现栈
typedef struct Stack {
	STDataType* _a;
	int _top;		//栈顶
	int _capacity;	//容量
}Stack;

//初始化栈
void StackInit(Stack* ps) {
	assert(ps);
	ps->_a = NULL;
	ps->_capacity = ps->_top = 0;
}

//检查空间是否足够
void CheckCapacity(Stack* ps)
{
	if (ps->_top == ps->_capacity)
	{
		int NewCapacity = ps->_capacity == 0 ? 4 : 2 * ps->_capacity;
		STDataType* NewA = (STDataType*)realloc(ps->_a, sizeof(STDataType) * NewCapacity);
		if (NewA == NULL)
		{
			perror("realloc fail");
		}
		ps->_capacity = NewCapacity;
		ps->_a = NewA;
	}
}

//入栈
void StackPush(Stack* ps, STDataType data) {
	assert(ps);
	CheckCapacity(ps);
	*(ps->_a + ps->_top) = data;
	ps->_top++;
}

//出栈
void StackPop(Stack* ps)
{
	assert(ps && ps->_top > 0);
	ps->_top--;
}

//获取栈顶元素
STDataType StackTop(Stack* ps)
{
	assert(ps && ps->_top > 0);
	return *(ps->_a + ps->_top - 1);
}

//获取栈中有效元素个数
int StatckSize(Stack* ps) {
	assert(ps);
	return ps->_top;
}

//检测栈是否为空，若为空则返回非零结果
//若不为空则返回0
int StackEmpty(Stack* ps) {
	return ps->_top == 0;
}

//输出栈
void PrintStack(Stack* ps)
{
	for (int i = 0; i < ps->_top; i++)
	{
		printf("%d ", *(ps->_a + i));
	}
	printf("\n");
}

//销毁栈
void StackDestroy(Stack* ps) {
	assert(ps);
	free(ps->_a);
	ps->_a = NULL;
	ps->_capacity = ps->_top = 0;
}

值得注意的是，关于_top的指向问题，有两种情况：

_top指向栈顶元素：初始化时应将_top指向 -1 的位置，因为它若指向 0 的位置，无法判断它是否为空。
_top指向栈顶元素的下一个位置：初始化时应将_top指向 0 的位置，这样就代表栈为空。上述代码就是按照这种方式的实现的。

2. 队列

2.1 队列的概念及结构

队列：一种只允许在一端进行插入数据操作，在另一端进行删除数据操作的线性表，队列符合先进先出FIFO(First In First Out)

这种数据结构可以类比为排队出门，先进队伍的先出门。

队列对应的两个操作：

入队列：进行插入操作的一端称为队尾。
出队列：进行删除操作的一端称为队头。

在这里插入图片描述

2.2 队列的实现

队列也可以通过顺序表或链表来实现，相对而言使用链表更优一些，因为使用顺序表在队头出队列时效率较低。

下面我们通过c语言来实现对应的结构和相关操作：

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef int QDataType;

// 链式结构：表示队列的节点
typedef struct QListNode
{
	struct QListNode* _next;// 指针域
	QDataType _data;        // 数据
}QNode;

// 在处理队列时，需要用到队列的队头指针和队尾指针
// 所以直接将描述一个队列的信息封装到一个结构体中
// 这样在处理队列时，只需要一个结构体变量就足够了
// 队列的结构
typedef struct Queue
{
	QNode* _front; // 队头
	QNode* _rear;  // 队尾
	int size;      // 节点个数
}Queue;

// 初始化队列
void QueueInit(Queue* q) {
	assert(q);
	q->_front = q->_rear = NULL;
	q->size = 0;
}

// 申请节点
QNode* QListBuyNode(QDataType x)
{
	QNode* newNode = (QNode*)malloc(sizeof(QNode));
	if (newNode == NULL)
	{
		perror("malloc fail");
		exit(1);
	}
	newNode->_data = x;
	newNode->_next = NULL;
	return newNode;
}

// 队尾入队列
void QueuePush(Queue* q, QDataType data)
{
	assert(q);
	QNode* newNode = QListBuyNode(data);
	if (q->size == 0)
	{
		q->_front = q->_rear = newNode;
	}
	else {
		q->_rear->_next = newNode;
		q->_rear = q->_rear->_next;
	}
	q->size++;
}

// 队头出队列 
void QueuePop(Queue* q)
{
	assert(q && q->size);
	if (q->size == 1)
	{
		free(q->_front);
		q->_front = q->_rear = NULL;
	}
	else {
		QNode* PopNode = q->_front;
		q->_front = q->_front->_next;
		free(PopNode);
		PopNode = NULL;
	}
	q->size--;
}

// 获取队列头部元素 
QDataType QueueFront(Queue* q) {
	assert(q && q->size);
	return q->_front->_data;
}

// 获取队列队尾元素 
QDataType QueueBack(Queue* q) {
	assert(q && q->size);
	return q->_rear->_data;
}

// 获取队列中有效元素个数 
int QueueSize(Queue* q) {
	assert(q);
	return q->size;
}

// 检测队列是否为空
// 如果为空返回非零结果
// 如果非空返回0 
int QueueEmpty(Queue* q) {
	assert(q);
	return q->size == 0;
}

// 销毁队列 
void QueueDestroy(Queue* q)
{
	assert(q);
	while (q->_front) {
		QueuePop(q);
	}
	q->_front = NULL;
	q->_rear = NULL;
}