首页 > 其他分享 >数据结构——栈和队列

数据结构——栈和队列

时间：2024-10-05 23:47:13浏览次数：8  
标签：assert pq ps 队列 Queue phead 数据结构

数据结构——栈和队列

文章目录

一、栈

1.概念

  • 栈：⼀种特殊的线性表，其只允许在固定的⼀端进⾏插⼊和删除元素操作。
  • 栈顶和栈底：进⾏数据插⼊和删除操作的⼀端称为栈顶，另⼀端称为栈底。
  • 压栈：栈的插⼊操作叫做进栈/压栈/⼊栈，⼊数据在栈顶。
  • 出栈：栈的删除操作叫做出栈，出数据也在栈顶。
  • 栈的特点： 栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。

2.结构

栈底层结构选型

栈的实现⼀般可以使⽤数组或者链表实现，相对⽽⾔数组的结构实现更优⼀些。分析如下：

1.数组：

时间复杂度为O(1)，但需要增容：realloc；

操作系统后面的空间足够时是原地增容，不够时需要进行异地增容，需要额外开辟大的存储空间，拷贝旧数据，释放旧空间，这里虽然会存在一定的性能消耗，但是因为我们的增容都是乘2倍的进行，所以哪怕是异地增容，它增容的次数都很少，效率消耗可以不计，不需要频繁的向操作系统申请空间。

2.单链表：

（1）.栈顶在尾部：压栈相当于链表的尾插，出栈相当于尾删，都需要根据头结点phead进行遍历找到尾结点，时间复杂度均为O(N);

（2）.栈顶在头部：压栈相当于链表的头插，时间复杂度为O(1)。出栈：就是让下一个结点作为新的头结点，然后把头结点释放掉，栈顶在头结点的位置，时间复杂度为O(1)；

3.双向链表：

时间复杂度都是一样的，均为O(1)。因为双链表中有2个指针，单链表中只有一个，所有双链表比单链表更占内存，首先排除。

更推荐数组的原因：缓存的问题。

数组申请的空间是一块连续的空间，链表每个节点的地址空间不一定是连续的。

比如我们现在要向数组或者是顺序表里面去存储数据，那么CPU会去执行指令，先去访问内存，内存会去读取一片连续的数据进行缓存，防止之后再用，避免频繁地去访问。在这方面数组比链表更优。

这里我们选择数组作为栈的底层结构。
  • 逻辑结构：线性的
  • 物理结构：线性的

3.栈的实现

在这里插入图片描述

定义栈的结构：

typedef int STDataType;
typedef struct Stack
{
	STDataType* arr;
	int capacity;//栈的空间大写
	int top;//栈顶
}ST;
3.1初始化
void STInit(ST* ps)
{
	assert(ps);
	ps->arr = NULL;
	ps->capacity = ps->top = 0;
}
3.2销毁
void STDestroy(ST* ps)
{
	assert(ps);
	if (ps->arr)
		free(ps->arr);
	ps->arr = NULL;
	ps->top = ps->capacity = 0;
}
3.3入数据
void StackPush(ST* ps, STDataType x)
{
	assert(ps);
	//1.判断空间是否足够
	if (ps->capacity == ps->top)
	{
		int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		STDataType* tmp = (STDataType*)realloc(ps->arr, newCapacity * sizeof(STDataType));
		if (tmp == NULL)
		{
			perror("realloc fail!");
			exit(1);
		}
		ps->arr = tmp;
		ps->capacity = newCapacity;
	}
	//空间一定够
	ps->arr[ps->top++] = x;
}
3.4出数据
void StackPop(ST* ps)
{
	assert(ps&&ps->top!=0);
	--ps->top;
}
3.5取栈顶元素
STDataType StackTop(ST* ps)
{
	assert(ps&&ps->top!=0);
	return ps->arr[ps->top - 1];
}
3.6获取栈中有效元素个数
int STSize(ST* ps)
{
	assert((ps));
	return ps->top;
}

4.完整代码

4.1.Stack.h

该部分是栈结构的定义、函数的声明.

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
//定义栈的结构
typedef int STDataType;
typedef struct Stack
{
	STDataType* arr;
	int capacity;//栈的空间大写
	int top;//栈顶
}ST;

void STInit(ST* ps);
void STDestroy(ST* ps);

//栈顶---入数据，出数据
void StackPush(ST* ps, STDataType x);
void StackPop(ST* ps);

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

bool StackEmpty(ST* ps);

//获取栈中有效元素个数
int STSize(ST* ps);
4.2.Stack.c

该部分是函数功能的实现.

#include"Stack.h"

void STInit(ST* ps)
{
	assert(ps);
	ps->arr = NULL;
	ps->capacity = ps->top = 0;
}
void STDestroy(ST* ps)
{
	assert(ps);
	if (ps->arr)
		free(ps->arr);
	ps->arr = NULL;
	ps->top = ps->capacity = 0;
}

void StackPush(ST* ps, STDataType x)
{
	assert(ps);
	//1.判断空间是否足够
	if (ps->capacity == ps->top)
	{
		int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		STDataType* tmp = (STDataType*)realloc(ps->arr, newCapacity * sizeof(STDataType));
		if (tmp == NULL)
		{
			perror("realloc fail!");
			exit(1);
		}
		ps->arr = tmp;
		ps->capacity = newCapacity;
	}
	//空间一定够
	ps->arr[ps->top++] = x;
}
void StackPop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));

	--ps->top;
}
bool StackEmpty(ST* ps)
{
	assert(ps);
	return ps->top == 0;
}

STDataType StackTop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));

	return ps->arr[ps->top - 1];
}

int STSize(ST* ps)
{
	assert(ps);
	return ps->top;
}
4.3.test.c

该部分用于测试，函数的调用.

#include"Stack.h"

void STTest()
{
	ST st;
	STInit(&st);
	/
	StackPush(&st, 1);
	StackPush(&st, 2);
	StackPush(&st, 3);
	StackPush(&st, 4);
	printf("size:%d\n", STSize(&st));
	//StackPop(&st);
	//循环出栈，直到栈为空
	while (!StackEmpty(&st))
	{
		STDataType data = StackTop(&st);
		printf("%d ", data);
		//出栈
		StackPop(&st);
	}
	printf("size:%d\n", STSize(&st));

	
	//STDestroy(&st);
}
int main()
{
	STTest();
	return 0;
}

二、队列

1.概念

  • 队列：只允许在⼀端进⾏插⼊数据操作，在另⼀端进⾏删除数据操作的特殊线性表。

  • ⼊队列：进⾏插⼊操作的⼀端称为队尾。

  • 出队列：进⾏删除操作的⼀端称为队头。

  • 队列的特点：队列中的数据元素遵守先进先出FIFO(First In First Out)的原则。

2.结构

队列底层结构选型

队列也可以数组和链表的结构实现，使⽤链表的结构实现更优⼀些。分析如下：

1.数组:

前队头后队尾；入队的时间复杂度为O(1),但出队的时间复杂度O(N)。

2单链表:

头结点定为队头，最后一个结点定为队尾；

出队相当于头删，时间复杂度为O(1)，入队相当于尾插，时间复杂度为O(N）(因为需要遍历ptail)，如果定义一个尾结点ptail(额外增加一个指针），那么时间复杂度可以从O(N)降到O(1)，由此，我们选择链表。

要是反过来，队头定义成最后一个节点的话，删除最后一个节点，我们不能找到最后一个节点的前一个节点。所以不行！！

更推荐链表的原因：因为如果使⽤数组的结构，出队在数组头上出数据，效率会⽐较低。

底层结构是链表

这里我们选择单链表作为队列的底层结构。
  • 逻辑结构：线性的
  • 物理结构：不一定是线性的

3.队列的实现

在这里插入图片描述

定义队列的结构：

//定义队列结点的结构
typedef int QDataType;
typedef struct QueueNode
{
	QDataType data;
	struct QueueNode* next;
}QueueNode;

typedef struct Queue
{
	QueueNode* phead;//队头
	QueueNode* ptail;//队尾
	int size;//保存队列有效数据个数
}Queue;
3.1初始化
void QueueInit(Queue* pq)
{
	assert(pq);
	pq->phead = pq->ptail = NULL;
	pq->size = 0;
}
3.2入队列（队尾）
void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	//申请新的结点
	QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
	if (newnode == NULL)
	{
		perror("malloc fail!");
		exit(1);
	}
	newnode->data = x;
	newnode->next = NULL;
	if (pq->phead == NULL)
	{
		pq->phead = pq->ptail = newnode;
	}
	else
	{
		//队列不为空
		pq->ptail->next = newnode;
		pq->ptail = newnode;
	}
	pq->size++;
}
3.3出队列（队头）
void QueuePop(Queue* pq)
{
	assert(pq&&pq->phead!=NULL&&pq->ptail!=NULL);

	//只有一个结点的情况，避免ptail变成野指针
	if (pq->ptail == pq->phead)
	{
		free(pq->phead);
		pq->phead = pq->ptail = NULL;
	}
	else
	{
		//删除对头结点
		QueueNode* next = pq->phead->next;
		free(pq->phead);
		pq->phead = next;
	}
	--pq->size;
}
3.4取队头数据
QDataType QueueFront(Queue* pq)
{
	assert(pq&&pq->phead!=NULL&&pq->ptail!=NULL);
	return pq->phead->data;
}
3.5取队尾数据
QDataType QueueBack(Queue* pq)
{
	assert(pq&&pq->phead!=NULL&&pq->ptail!=NULL);
	return pq->ptail->data;
}
3.6队列有效元素个数

在这里，大家可以思考一下下面代码有什么问题？

//队列有效元素个数
int QueueSize(Queue* pq)
{
	assert(pq);
	int size = 0;
	QueueNode* pcur = pq->phead;
	while (pcur)
	{
		size++;
		pcur = pcur->next;
	}
	return size;
}

想到了吗？

答案是：队列不可以遍历，队列只能一端进一端出，要不然岂不是每个结点都能取到了？而且它的时间复杂度是O(N),要是进行频繁的遍历的话，程序效率会比较低。

我们可以在定义队列结构时，就多定义一个size(用于保存队列有效数据个数)，这里在上面我已经定义好了，可以直接使用，如下：

int QueueSize(Queue* pq)
{
	assert(pq);
	return pq->size;
}
3.7销毁队列
void QueueDestroy(Queue* pq)
{
	assert(pq&&pq->phead!=NULL&&pq->ptail!=NULL);

	QueueNode* pcur = pq->phead;
	while (pcur)
	{
		Queue* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	pq->phead = pq->ptail = NULL;
	pq->size = 0;
}

4.完整代码

4.1.Queue.h

该部分是栈结构的定义、函数的声明.

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

//定义队列结构
typedef int QDataType;
typedef struct QueueNode
{
	QDataType data;
	struct QueueNode* next;
}QueueNode;

typedef struct Queue
{
	QueueNode* phead;
	QueueNode* ptail;
	int size;//保存队列有效数据个数
}Queue;

void QueueInit(Queue* pq);

// ⼊队列，队尾
void QueuePush(Queue* pq, QDataType x);
// 出队列，队头
void QueuePop(Queue* pq);
//队列判空
bool QueueEmpty(Queue* pq);

//取队头数据
QDataType QueueFront(Queue* pq);
//取队尾数据
QDataType QueueBack(Queue* pq);
//队列有效元素个数
int QueueSize(Queue* pq);
//销毁队列
void QueueDestroy(Queue* pq);
4.2.Queue.c

该部分是函数功能的实现.

#include"Queue.h"
void QueueInit(Queue* pq)
{
	assert(pq);
	pq->phead = pq->ptail = NULL;
	pq->size = 0;
}

void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	//申请新的结点
	QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
	if (newnode == NULL)
	{
		perror("malloc fail!");
		exit(1);
	}
	newnode->data = x;
	newnode->next = NULL;
	if (pq->phead == NULL)
	{
		pq->phead = pq->ptail = newnode;
	}
	else
	{
		//队列不为空
		pq->ptail->next = newnode;
		pq->ptail = newnode;
	}
	pq->size++;
}
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->phead == NULL && pq->ptail == NULL;
}
void QueuePop(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	//只有一个结点的情况，避免ptail变成野指针
	if (pq->ptail == pq->phead)
	{
		free(pq->phead);
		pq->phead = pq->ptail = NULL;
	}
	else
	{
		//删除对头结点
		QueueNode* next = pq->phead->next;
		free(pq->phead);
		pq->phead = next;
	}
	--pq->size;
}
QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->phead->data;
}
QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));

	return pq->ptail->data;
}
//队列有效元素个数
int QueueSize(Queue* pq)
{
	assert(pq);
	/*int size = 0;
	QueueNode* pcur = pq->phead;
	while (pcur)
	{
		size++;
		pcur = pcur->next;
	}
	return size;
	*/
	return pq->size;
}

void QueueDestroy(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));

	QueueNode* pcur = pq->phead;
	while (pcur)
	{
		Queue* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	pq->phead = pq->ptail = NULL;
	pq->size = 0;
}
4.3.test.c

该部分用于测试，函数的调用.

#include"Queue.h"

void QueueTest01()
{
	Queue q;
	QueueInit(&q);
	QueuePush(&q, 1);
	QueuePush(&q, 2);
	QueuePush(&q, 3);
	QueuePush(&q, 4);

	//QueuePop(&q);
	printf("head:%d\n", QueueFront(&q));
	printf("tail:%d\n", QueueBack(&q));
	printf("size:%d\n", QueueSize(&q));
	QueueDestroy(&q);
}

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

三、总结

在数据结构的丰富多样的领域中，栈和队列作为两种基本的线性数据结构，各自以其独特的特点和应用场景，展现了它们在数据处理中的不可或缺性。
希望本篇博客对你的学习有所帮助，有任何问题，欢迎在评论区留言哦~

标签：assert,pq,ps,队列,Queue,phead,数据结构
From： https://blog.csdn.net/zoelinkailuo/article/details/142720785

相关文章

  • 消息队列面试01
    基础知识特点：（1）服务解耦：服务之间通过消息中介（如RabbitMQ、Kafka）进行通信，减少直接依赖。（2）异步处理：提高当前请求速度，代价是系统调用的降速，可能带来业务不一致。（3）削峰（流量控制）：消息产生速度>消息消费速度（先把请求存起来）（4）增强系统可靠性：     I.MQ给consumerAC......
  • 代码随想录算法训练营 | 134. 加油站，135. 分发糖果，860.柠檬水找零，406.根据身高重建队
    134.加油站题目链接：134.加油站文档讲解︰代码随想录(programmercarl.com)视频讲解︰加油站日期：2024-10-04想法：1.总汽油大于等于消耗一定能跑完，2.当前剩余汽油小于0了，只能从下一站开始重新计算Java代码如下：classSolution{publicintcanCompleteCircuit(int[]gas,int......
  • [北大集训 2021] 简单数据结构
    简单数据结构，但本蒟蒻觉得并不简单呐！容易发现这题的几个好用的性质：1.只要被第一个操作影响的都能够保持单调，容易一起维护。2.操作都是全局的！3.没被操作一影响的都可以表示为\(ki+a_i\)的形式。利用这些性质，我们考虑把没被操作一影响的项放在\(S\)集合，被操作一影响的项放......
  • [消息队列]kafka高性能/高吞吐量
    Kafka每秒可以处理一百万条以上消息，吞吐量达到每秒百万级。那么Kafka为什么那么高的吞吐量呢？简单来说有以下几点原因：页缓存技术Kafka是基于操作系统的页缓存来实现写入的。操作系统本身有一层缓存，叫做pagecache，是在内存里的缓存，我们也可以称之为oscache，意思就是操作系统自己......
  • 信息学奥赛复赛复习10-CSP-J2020-03表达式求值-栈、后缀表达式、isdigit函数、c_str函
    PDF文档公众号回复关键字:202410031P7073[CSP-J2020]表达式[题目描述]小C热衷于学习数理逻辑。有一天，他发现了一种特别的逻辑表达式。在这种逻辑表达式中，所有操作数都是变量，且它们的取值只能为0或1，运算从左往右进行。如果表达式中有括号，则先计算括号内的子表达式的......
  • python3 队列的使用
    在leetcode如下题目中使用队列637.二叉树的层平均值：#Definitionforabinarytreenode.#classTreeNode:#def__init__(self,val=0,left=None,right=None):#self.val=val#self.left=left#self.right=rightclassSolutio......
  • 10.3数据结构
    二叉树表示与储存：parlchrch二叉树遍历：前序，中序，后序遍历先序遍历先根、左子树、右子树中序遍历左子树、根、右子树后序遍历左子树、右子树、根无根树的遍历......
  • 63_索引管理_内核级知识点：深入探秘type底层数据结构
    type，是一个index中用来区分类似的数据的，类似的数据，但是可能有不同的fields，而且有不同的属性来控制索引建立、分词器field的value，在底层的lucene中建立索引的时候，全部是opaquebytes类型，不区分类型的lucene是没有type的概念的，在document中，实际上将type作为一个document的field来......
  • 单调队列优化 DP
    单调队列可以\(O(n)\)求出子区间的最值，且顺序上要求区间的左端点和右端点单调不降。引入P1886滑动窗口/【模板】单调队列定义一个队列\(q\)，我们让\(q\)中的元素满足单调不降。因此当\(x\)入队时，从前往后让不在当前范围的元素出队，从后往前将\(<x\)的元素全部出队，然......
  • 2024.10.1 总结（集训；数据结构 主要是线段树）
    XK又来给我们讲课了。开心！1.Baka'sTrick两种理解：双栈模拟队列。[找到若干个划分点，使得每个区间包含恰好一个划分点。维护划分点到划分点段的前缀、后缀信息。在在线的实现中，在队列中维护仅仅一个划分点，维护它到前面每个点和它到后面每个点的信息。当这个划分点出队时，把队......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99