1. Toy模板网首页
  2. > Toy博客

【数据结构】我家三岁表弟都明白的栈和队列，你不会不了解吧？

10月前 作者：情话0.0 分类：Toy博客 阅读(35) 违法举报

这篇具有很好参考价值的文章主要介绍了【数据结构】我家三岁表弟都明白的栈和队列，你不会不了解吧？。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

🧑‍💻作者： @情话0.0
📝专栏：《数据结构》
👦个人简介：一名双非编程菜鸟，在这里分享自己的编程学习笔记，欢迎大家的指正与点赞，谢谢！

【数据结构】我家三岁表弟都明白的栈和队列，你不会不了解吧？,数据结构,栈,队列,线性表

一、栈

1.栈的基本概念

  栈是只允许在一端进行插入或删除操作的线性表。首先栈是一种线性表，但是对其限定该线性表只能在某一端进行插入或删除操作。
  栈顶：进行数据插入和删除操作的一端；
  栈底：不允许进行插入和删除的另一端；
  空栈：不含任何元素的空表。

栈中的元素遵守后进先出LIFO（Last In First Out）的原则。

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

【数据结构】我家三岁表弟都明白的栈和队列，你不会不了解吧？,数据结构,栈,队列,线性表

2.栈的顺序存储（数组实现）

  栈是一种操作受限的线性表，可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。
  采用顺序存储的栈称为顺序栈，它利用一组地址连续的存储单元（数组）存放自栈底到栈顶的数据元素，同时附设一个指针（top）指示当前栈顶元素的位置。

栈的顺序存储类型描述如下：

typedef int SDataType;

typedef struct Stack
{
	SDataType* array;
	int capacity; //栈的容量
	int top; //栈的元素个数
}Stack;

2.1 栈的初始化

void StackInit(Stack* ps)
{
	assert(ps);
	ps->array = (SDataType*)malloc(sizeof(SDataType)* 5);
	ps->capacity = 5;
	ps->top = 0;
}

栈顶指针：ps->top,初始化设置ps->top=0,指向栈顶元素的上层存储单元。

2.2 检查栈满

void CheckCapacity(Stack* ps)
{
	assert(ps);
	if (ps->top == ps->capacity)
	{
		SDataType* arr = (SDataType*)realloc(ps->array, sizeof(SDataType)* (ps->capacity)*2);
		if (arr == NULL)
		{
			return;
		}
		ps->array = arr;
		ps->capacity *= 2;
	}
}

栈满条件为ps->top == ps->capacity，若空间已满，就进行2倍扩容。

2.3 入栈：尾插

void StackPush(Stack* ps, SDataType data)
{
	assert(ps);
	CheckCapacity(ps);
	ps->array[ps->top++] = data;
}

进栈操作：栈不满时，先将数据存储到top指针指向的存储空间，再将top指针加 1 ；栈满时先扩容，在插入元素。

2.4 出栈：尾删

void StackPop(Stack* ps)
{
	assert(!StackEmpty(ps));
	ps->top--;
}

出栈操作：先对栈进行断言判断是否为空，非空时只需将top指针减 1 即可，因为下一次进栈直接会将已经出栈的元素覆盖掉。

2.5 获取栈顶元素

SDataType StackTop(Stack* ps)
{
	assert(!StackEmpty(ps));
	return ps->array[ps->top - 1];
}

2.6 获取栈中有效元素的个数

int StackSize(Stack* ps)
{
	assert(ps);
	return ps->top;
}

由于使用数组来实现，所以栈顶指针的数据和有效元素个数相等。

2.7 检测栈是否为空

int StackEmpty(Stack* ps)
{
	assert(ps);
	return ps->top == 0;
}

2.8 销毁栈

void StackDestroy(Stack* ps)
{
	assert(ps);
	free(ps->array);
	ps->capacity = 0;
	ps->top = 0;
	ps->array = NULL;
}

注意：这里的top指针指向栈顶元素的上层存储空间，所以进栈操作为ps->array[ps->top++] = data，出栈操作为ps->top--，。若栈顶指针初始化为ps->top=-1,即top指向栈顶元素，则入栈操作为ps->array[++ps->top]=data,出栈操作不变。栈空判断条件为ps->top==-1,栈满判断条件为++ps->top==ps->capacity。

3. 源代码

3.1 stack.h

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <string.h>
typedef int SDataType;


typedef struct Stack
{
	SDataType* array;
	int capacity;
	int top;
}Stack;

void StackInit(Stack* ps);

// 入栈：尾插
void StackPush(Stack* ps, SDataType data);

// 出栈：尾删
void StackPop(Stack* ps);

// 获取栈顶元素
SDataType StackTop(Stack* ps);

// 获取栈中有效元素的个数
int StackSize(Stack* ps);

// 检测栈是否为空
int StackEmpty(Stack* ps);

// 销毁栈
void StackDestroy(Stack* ps);

3.2 stack.c

#include "stack.h"



void StackInit(Stack* ps)
{
	assert(ps);
	ps->array = (SDataType*)malloc(sizeof(SDataType)* 5);
	ps->capacity = 5;
	ps->top = 0;
}


void CheckCapacity(Stack* ps)
{
	assert(ps);
	if (ps->top == ps->capacity)
	{
		SDataType* arr = (SDataType*)realloc(ps->array, sizeof(SDataType)* (ps->capacity)*2);
		if (arr == NULL)
		{
			return;
		}
		ps->array = arr;
		ps->capacity *= 2;
	}
}

// 入栈：尾插
void StackPush(Stack* ps, SDataType data)
{
	assert(ps);
	CheckCapacity(ps);
	ps->array[ps->top++] = data;

}

// 出栈：尾删
void StackPop(Stack* ps)
{
	assert(!StackEmpty(ps));
	ps->top--;
}

// 获取栈顶元素
SDataType StackTop(Stack* ps)
{
	assert(!StackEmpty(ps));
	return ps->array[ps->top - 1];
}

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

// 检测栈是否为空
int StackEmpty(Stack* ps)
{
	assert(ps);
	return ps->top == 0;
}

// 销毁栈
void StackDestroy(Stack* ps)
{
	assert(ps);
	free(ps->array);
	ps->capacity = 0;
	ps->top = 0;
	ps->array = NULL;
}

void Print(Stack* ps)
{
	assert(ps);
	int i = 0;
	while (i < ps->top)
	{
		printf("%d ", ps->array[i]);
		i++;
	}
	printf("\n");
}
void test()
{
	Stack ps;
	StackInit(&ps);
	StackPush(&ps, 0);
	StackPush(&ps, 1);
	StackPush(&ps, 2);
	StackPush(&ps, 3);
	StackPush(&ps, 4);
	StackPush(&ps, 5);
	Print(&ps);
	StackPop(&ps);
	Print(&ps);
	int ret = StackTop(&ps);
	printf("%d\n", ret);
	ret = StackSize(&ps);
	printf("%d\n", ret);
}

3.3 test.c

#include "stack.h"

int main()
{
	test();
	return 0;
}

二、队列

1.队列的基本概念

  队列也是一种操作受限的线性表，只允许在表的一端进行插入，而在表的另一端进行删除。向队列中插入元素称为入队；删除元素称为出队。
  队头：允许删除的一端，又称队首；
  队尾：允许插入的一端；
  空队列：不含任何元素的空表。

  队列中的元素遵守后进先出FIFO（First In First Out）的原则。
【数据结构】我家三岁表弟都明白的栈和队列，你不会不了解吧？,数据结构,栈,队列,线性表

2.队列的链式存储

  队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低。
  队列的链式表示称为链队列，它实际上是一个同时带有队头指针和队尾指针的单链表。头指针指向队头结点，尾指针指向队尾结点，即单链表的最后一个结点。
【数据结构】我家三岁表弟都明白的栈和队列，你不会不了解吧？,数据结构,栈,队列,线性表

队列的链式存储类型描述如下：

typedef int QDataType;
typedef struct QNode //队列的每个节点（链表）
{
	int data;
	struct QNode* next;
}QNode;

typedef struct Queue //队列
{
	QNode* front; //队头指针
	QNode* rear; //队尾指针
	int size; //队列元素个数
}Queue;

2.1 队列初始化

void QueueInit(Queue* q)
{
	assert(q);
	q->front = NULL;
	q->rear = NULL;
	q->size = 0;
}

2.2 入队

void QueuePush(Queue* q, QDataType data)
{
	assert(q);
	QNode* newNode = (QNode*)malloc(sizeof(QNode)); //创建结点
	newNode->next = NULL;
	newNode->data = data;

	if (QueueEmpty(q)) //队列为空
	{
		q->front = newNode;
	}
	else //队列中已有元素
	{
		q->rear->next = newNode;
	}
	q->rear = newNode;
	q->size++;
}

2.3 出队

void QueuePop(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(q)); //断言：队列为空
	QNode* delNode = q->front;
	if (q->front == q->rear) //队列中只有一个元素
	{
		q->front = q->rear = NULL;
	}
	else //队列有多个元素
	{
		q->front = delNode->next;
	}
	free(delNode);
	q->size--;
}

2.4 获取队头元素

QDataType QueueFront(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(q));
	return q->front->data;
}

2.5 获取队尾元素

QDataType QueueBack(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(q));
	return q->rear->data;
}

2.6 获取队列中有效元素的个数

int QueueSize(Queue* q)
{
	assert(q);
	return q->size;
}

2.7 检测队列是否为空

int QueueEmpty(Queue* q)
{
	assert(q);
	return q->rear == NULL;
}

2.8 销毁队列

void QueueDestroy(Queue* q)
{
	assert(q);
	QNode* cur = q->front;
	while (cur)
	{
		q->front = cur->next;
		free(cur);
		cur = q->front;
	}

	q->front = q->rear = NULL;
	q->size = 0;
}

3. 源代码

3.1 queue.h

#include <stdio.h>
#include <assert.h>
#include <stdbool.h>
#include <malloc.h>

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

typedef struct Queue
{
	QNode* front;
	QNode* rear;
	int size;
}Queue;

void QueueInit(Queue* q);
void QueuePush(Queue* q, QDataType data);
void QueuePop(Queue* q);
QDataType QueueFront(Queue* q);
QDataType QueueBack(Queue* q);
int QueueSize(Queue* q);
int QueueEmpty(Queue* q);
void QueueDestroy(Queue* q);
void QueueTest();

3.2 queue.c

#include "Queue.h"


void QueueInit(Queue* q)
{
	assert(q);
	q->front = NULL;
	q->rear = NULL;
	q->size = 0;
}
void QueuePush(Queue* q, QDataType data)
{
	assert(q);
	QNode* newNode = (QNode*)malloc(sizeof(QNode));
	newNode->next = NULL;
	newNode->data = data;

	if (QueueEmpty(q))
	{
		q->front = newNode;
	}
	else
	{
		q->rear->next = newNode;
	}
	q->rear = newNode;
	q->size++;
}
void QueuePop(Queue* q)
{
	assert(q);
	if (QueueEmpty(q))
	{
		return;
	}
	QNode* delNode = q->front;
	if (q->front == q->rear)
	{
		q->front = q->rear = NULL;
	}
	else
	{
		q->front = delNode->next;
	}
	free(delNode);
	q->size--;
}
QDataType QueueFront(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(q));
	return q->front->data;
}
QDataType QueueBack(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(q));
	return q->rear->data;
}
int QueueSize(Queue* q)
{
	assert(q);
	return q->size;
}
int QueueEmpty(Queue* q)
{
	assert(q);
	return q->rear == NULL;
}
void QueueDestroy(Queue* q)
{
	assert(q);
	QNode* cur = q->front;
	while (cur)
	{
		q->front = cur->next;
		free(cur);
		cur = q->front;
	}

	q->front = q->rear = NULL;
	q->size = 0;
}

void QueuePrint(Queue* q)
{
	assert(q);
	QNode* cur = q->front;
	while (cur)
	{
		printf("%d--->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}

void QueueTest()
{
	Queue q;
	QueueInit(&q);
	QueuePush(&q, 1);
	QueuePush(&q, 2);
	QueuePush(&q, 3);
	QueuePush(&q, 4);
	QueuePush(&q, 5);
	QueuePush(&q, 6);
	QueuePrint(&q);
	QueuePop(&q);
	QueuePrint(&q);
	int ret = QueueFront(&q);
	printf("%d\n", ret);
	ret = QueueBack(&q);
	printf("%d\n", ret);
}

3.3 test.c

#include "Queue.h"

int main()
{
	QueueTest();
	return 0;
}

队列扩展：循环队列

  将循环队列臆造为一个环状的空间，即把存储队列元素的表从逻辑上视为一个环，称为循环队列。当队首指针q->front=maxszie-1后，再前进一个位置就自动到0。

初始化时：q->front = q->rear = 0;
队首指针进1：q->front = (q->front + 1) % MaxSize;
队尾指针进1；q->rear = (q->rear + 1) % MaxSize;
队列长度：(q->rear + MaxSize - q->front) % MaxSize;
出队入队时：指针都按顺时针方向进1;

从下图可以看出对空的条件是q->front = q->rear ，若入队元素的速度快于出队元素的速度，则尾指针很快就会赶上队首指针，可以看出队满时也有q->front = q->rear。为了区分队满还是队空，我们选择浪费一个空间不存储元素，约定以队头指针在队尾指针的下一个位置作为队满的标志。

队满条件：(q->rear + 1) % MaxSize == q->front;
队空条件：q->front = q->rear = 0;
队列中元素个数：(q->rear + MaxSize - q->front) % MaxSize。

【数据结构】我家三岁表弟都明白的栈和队列，你不会不了解吧？,数据结构,栈,队列,线性表

总结

以上为对栈和队列的介绍，一定要注意最开始对其的初始化条件：比如栈的top指针到底指向哪里非常关键。相对来说栈与队列理解起来也比较轻松，主要是明白它们各自的属性特征。
  文章若有不足的地方还请大佬指正！！！

【数据结构】我家三岁表弟都明白的栈和队列，你不会不了解吧？,数据结构,栈,队列,线性表文章来源地址https://www.toymoban.com/news/detail-820407.html

到了这里，关于【数据结构】我家三岁表弟都明白的栈和队列，你不会不了解吧？的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • 头歌（C语言）-数据结构与算法-栈的实现-第1关：实现一个顺序存储的栈

    头歌（C语言）-数据结构与算法-栈的实现-第1关：实现一个顺序存储的栈

    任务描述 相关知识 栈的基本概念 栈结构的定义（C） 顺序栈的操作 编程要求 测试说明 任务描述 本关任务是实现 step1/SeqStack.cpp 中的 SS_IsFull 、 SS_IsEmpty 、 SS_Length 、 SS_Push 和 SS_Pop 五个操作函数，以实现判断栈是否为满、是否为空、求栈元素个数、进栈和出栈等功能。 相关

    2024年02月07日
    浏览(65)
  • 期末不知道如何复习数据结构的话，不妨点进来看看。看明白保你过。

    期末不知道如何复习数据结构的话，不妨点进来看看。看明白保你过。

         💯 博客内容：复习数据结构 😀 作  者：陈大大陈 🚀 个人简介：一个正在努力学技术的准前端，专注基础和实战分享 ，欢迎私信！ 💖 欢迎大家：这里是CSDN，我总结知识和写笔记的地方，喜欢的话请三连，有问题请私信 😘 😘 😘 目录 顺序表 单链表 双向链表

    2024年02月11日
    浏览(38)

  • 【数据结构】若元素以a,b,c,d,e的顺序进入一个初始为空的栈中，每个元素进栈，出栈各一次，要求出栈的第以元素为d，则合法的出栈序列共有多少种？

    若元素以a,b,c,d,e的顺序进入一个初始为空的栈中，每个元素进栈，出栈各一次，要求 出栈的第以元素为d，则合法的出栈序列共有多少种？ 首先他是以a,b,c,d,e,的顺序入栈 题目要求第一个出栈的是d，所以只能abcd入栈，这样栈中还有abc3种元素 e还没有入栈，e可以有4个时机入栈

    2024年02月06日
    浏览(43)
  • Tecplot数据结构——结构数据（结构网格）与非结构数据（非结构网格）

    Tecplot数据结构——结构数据（结构网格）与非结构数据（非结构网格）

    结构数据可以是一维、二维或三维的，下面以二维的数据格式为例。 在记事本中写入以下字符，并将文件以.plt或.dat为后缀命名。 其中数据总数为I*J=20，结构数据顺序为point格式，顺序为：(I,J)=(1,1), (I,J)=(2,1), … (I,J)=(Imax,1), (I,J)=(1,2), (I,J)=(2,2), (I,J)=(Imax,2), … (I,J)=(Imax,Jmax).

    2024年02月15日
    浏览(55)
  • 一文搞明白STM32芯片存储结构

    一文搞明白STM32芯片存储结构

            本篇介绍STM32芯片的存储结构，ARM公司负责提供设计内核，而其他外设则为芯片商设计并使用，ARM收取其专利费用而不参与其他经济活动，半导体芯片厂商拿到内核授权后，根据产品需求，添加各类组件，生产芯片售卖。图1为STM32的组成示意图，其中Cortex-M3内核、

    2024年02月14日
    浏览(40)
  • 数据结构与算法——数据结构有哪些，常用数据结构详解

    数据结构与算法——数据结构有哪些，常用数据结构详解

    数据结构是学习数据存储方式的一门学科，那么，数据存储方式有哪几种呢？下面将对数据结构的学习内容做一个简要的总结。 数据结构大致包含以下几种存储结构： 线性表，还可细分为顺序表、链表、栈和队列； 树结构，包括普通树，二叉树，线索二叉树等； 图存储结构

    2024年02月15日
    浏览(63)

  • 算法 数据结构分类 数据结构类型介绍 数据结构线性非线性结构 算法合集 （一）

     数据结构分为：                            a.线性结构                            b.非线性结构  a.线性结构：                       数据与结构存在一对一的线性关系； a . 线性结构 存储 分为：                                   顺序存储

    2024年02月10日
    浏览(53)
  • 结构化数据、非结构化数据、半结构化数据

    结构化数据、非结构化数据、半结构化数据

    结构化的数据一般是指可以使用关系型数据库表示和存储，可以用二维表来逻辑表达实现的数据。例如：需要多少个属性，每个属性什么类型，每个属性的取值范围等等，类似下图所示， 提前定义好了一个二维矩阵的元数据 ，包含有列名称、列的类型、列的约束等：   可见

    2024年02月09日
    浏览(67)
  • 【数据结构】何为数据结构。

    【数据结构】何为数据结构。

    🚩 WRITE IN FRONT 🚩    🔎 介绍：\\\"謓泽\\\"正在路上朝着\\\"攻城狮\\\"方向\\\"前进四\\\" 🔎 🏅 荣誉：2021|2022年度博客之星物联网与嵌入式开发TOP5|TOP4、2021|2022博客之星TOP100|TOP63、阿里云专家博主、掘金优秀创作者、全网粉丝量6w+、全网访问量100w+ 🏅 🆔 文章内容由 謓泽 原创 如需相关

    2024年02月08日
    浏览(61)
  • 【数据结构】什么是数据结构?

    【数据结构】什么是数据结构?

    🦄 个人主页 :修修修也 🎏 所属专栏 :数据结构 ⚙️ 操作环境 : Visual Studio 2022 目录 🎏数据结构的定义 🎏结语 数据结构(Data Structure)是计算机 存储 , 组织数据的方式 ,指 相互之间存在一种或多种特定关系的数据元素的集合 . 这么讲可能有些抽象,放一张图大家可能好理解一

    2024年02月07日
    浏览(52)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包