【数据结构】栈和队列

2023-12-31 23:30:29

在这里插入图片描述

前言:
栈(Stack)和队列(Queue),它们都是常用的数据结构,用于组织和存储数据。


一、栈

当我们谈论栈时,我们实际上在谈论一种后进先出(Last In, First Out,LIFO)的数据结构。这意味着最后插入的元素首先被移除。让我们深入了解一下栈的特性和操作:

1. 特性:

  • 后进先出(LIFO): 最后放入栈的元素是第一个被移除的。

  • 操作受限: 栈有两个主要操作:推入(Push)和弹出(Pop)。推入将元素添加到栈的顶部,而弹出则将栈顶的元素移除。

  • 栈顶: 只有栈顶的元素是可见的,即只能访问或修改栈顶的元素。

2. 操作:

  • 推入(Push): 将元素添加到栈的顶部。

  • 弹出(Pop): 从栈的顶部移除元素。

  • 查看栈顶(Peek): 查看栈顶的元素,但不移除它。

  • 判空和判满: 可以检查栈是否为空(Empty)或已满(Full),虽然栈的大小通常是动态调整的,因此满的情况相对较少。

在这里插入图片描述


栈的实现

栈的实现一般可以使用数组或者链表实现,相对而言数组的结构实现更优一些。这里我们使用动态的数组来实现栈。

在这里插入图片描述
Stack 结构体:

typedef int STDataType;

typedef struct Stack {
	STDataType* a; 
	int top;     //标识栈顶
	int capacity; //容量

}ST;

操作栈的函数:

//初始化
void StackInit(ST* pst);

//销毁栈
void StackDestroy(ST* pst);

//栈顶推入
void StackPush(ST* pst, STDataType x);

//栈顶弹出
void StackPop(ST* pst);

//获取栈顶元素
STDataType StackTop(ST* pst);

//检测栈是否为空
bool StackEmpty(ST* pst);

//获取栈的有效元素个数
int StackSize(ST* pst);

完整的栈的代码在最后


二、队列

队列(Queue)是一种基本的数据结构,它遵循先进先出(First In, First Out,FIFO)的原则。这意味着最先进入队列的元素将最先被移出,就像排队一样。队列常被用于需要按顺序处理的场景,比如任务调度、广度优先搜索、打印任务等。

以下是队列的一些关键特性和基本操作:

1. 特性:

  • 先进先出(FIFO): 队列中最早进入的元素首先被移除。

  • 操作受限: 队列主要支持两个操作:入队(Enqueue)和出队(Dequeue)。

  • 队头和队尾: 队列的前端称为队头(Front),用于出队操作;队列的后端称为队尾(Rear),用于入队操作。

2. 操作:

  • 入队(Enqueue): 向队尾添加元素。

  • 出队(Dequeue): 从队头移除元素。

  • 查看队头元素(Front): 查看队头的元素,但不移除它。

  • 检查队列是否为空: 判断队列中是否有元素。

  • 检查队列是否已满(对于有限队列): 在使用有限大小的队列时,可以检查队列是否已满。

在实际编程中,队列可以使用数组、链表或其他数据结构来实现。例如,使用数组时需要考虑队列的大小和溢出的问题,而使用链表时可以更方便地处理动态大小的队列。

在这里插入图片描述


队列的实现

队列也可以数组和链表的结构实现,使用链表的结构实现更优一些,因为如果使用数组的结构,出队列在数组头上出数据,效率会比较低。

在这里插入图片描述

Queue结构体

typedef int QDataType;

//节点
typedef struct QueueNode {
	QDataType val;
	struct QueueNode* next;
}QNode;

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);

附录

栈实现的完整代码

“Stack.h”

#pragma once
#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* pst);

//销毁栈
void StackDestroy(ST* pst);

//栈顶推入
void StackPush(ST* pst, STDataType x);

//栈顶弹出
void StackPop(ST* pst);

//获取栈顶元素
STDataType StackTop(ST* pst);

//检测栈是否为空
bool StackEmpty(ST* pst);

//获取栈的有效元素个数
int StackSize(ST* pst);

“Stack.c”

#include"Stack.h"

void StackInit(ST* pst) {
	assert(pst);

	pst->a = NULL;
	pst->capacity = 0;
	pst->top = 0;//指向栈顶下一个元素
}

void StackDestroy(ST* pst) {
	assert(pst);

	free(pst->a);
}

void StackPush(ST* pst, STDataType x) {
	assert(pst);

	if (pst->top == pst->capacity) {
		int newcapacity = pst->capacity = 0 ? 4 : 2 * pst->capacity;
		STDataType* temp = realloc(pst->a,sizeof(STDataType)*newcapacity);
		if (temp == NULL) {
			perror("realloc fail");
			return;
		}

		pst->a = temp;
		pst->capacity = newcapacity;
	}

	pst->a[pst->top] = x;
	pst->top++;
}

void StackPop(ST* pst) {
	assert(pst);
	//不为空
	assert(pst->top > 0);

	pst->top--;
}

STDataType StackTop(ST* pst) {
	assert(pst);
	//不为空
	assert(pst->top > 0);

	return pst->a[pst->top - 1];
}

bool StackEmpty(ST* pst) {
	assert(pst);

	return pst->top == 0;
}

int StackSize(ST* pst) {
	assert(pst);

	return pst->top;
}

“test.c”

#include"Stack.h"

int main() {
	ST s;
	StackInit(&s);
	StackPush(&s,1);
	StackPush(&s,2);
	StackPush(&s,3);
	printf("%d ", StackTop(&s));
	StackPush(&s, 4);
	printf("%d ", StackTop(&s));

	while (!StackEmpty(&s)) {
		printf("%d ", StackTop(&s));
		StackPop(&s);
	}
	
	return 0;
}

队列实现的完整代码

“Queue.h”

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

typedef int QDataType;

//节点
typedef struct QueueNode {
	QDataType val;
	struct QueueNode* next;
}QNode;

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 = 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 == NULL) {
		pq->ptail = pq->phead = newnode;
	}
	else {
		pq->ptail->next = newnode;
		pq->ptail = newnode;
	}

	pq->size++;
}

void QueuePop(Queue* pq) {
	assert(pq->phead);
	assert(pq);

	QNode* del = pq->phead;
	pq->phead = pq->phead->next;
	free(del);
	del = NULL;

	if (pq->phead == NULL)
		pq->ptail = NULL;

	pq->size--;
}

QDataType QueueFront(Queue* pq) {
	assert(pq);
	assert(pq->phead);

	return pq->phead->val;
}

QDataType QueueBack(Queue* pq) {
	assert(pq);
	assert(pq->ptail);

	return pq->ptail->val;
}

bool QueueEmpty(Queue* pq) {
	assert(pq);

	return pq->phead == NULL;
}

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);
	QueuePush(&q,3);
	QueuePush(&q,4);
	QueuePush(&q,5);
	while (!QueueEmpty(&q)) {
		printf("%d",QueueFront(&q));
		QueuePop(&q);
	}
}

在这里插入图片描述
如果你喜欢这篇文章,点赞👍+评论+关注??哦!
欢迎大家提出疑问,以及不同的见解。

文章来源:https://blog.csdn.net/weixin_73551991/article/details/135317346
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。