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

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

🧑‍💻作者: @情话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) 顺序栈的操作 编程要求 测试说明 任务描述 本关任务是实现 step1/SeqStack.cpp 中的 SS_IsFull 、 SS_IsEmpty 、 SS_Length 、 SS_Push 和 SS_Pop 五个操作函数,以实现判断栈是否为满、是否为空、求栈元素个数、进栈和出栈等功能。 相关

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

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

    2024年02月11日
    浏览(36)
  • 【数据结构】若元素以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日
    浏览(42)
  • 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日
    浏览(54)
  • 一文搞明白STM32芯片存储结构

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

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

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

    2024年02月15日
    浏览(60)
  • 算法 数据结构分类 数据结构类型介绍 数据结构线性非线性结构 算法合集 (一)

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

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

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

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

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

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

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

    2024年02月07日
    浏览(50)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包