首页 > 其他分享 >栈和队列的实现

栈和队列的实现

时间:2024-08-30 16:21:50浏览次数:11  
标签:ps pq 队列 void Queue 实现 front Stack

1 栈

栈:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端
称为栈顶,另一端称为栈底。栈中的数据元素遵守后进先出LIFO(Last In First Out)的原则。
压栈:栈的插入操作叫做进栈/压栈/入栈,入数据在栈顶。
出栈:栈的删除操作叫做出栈。出数据也在栈顶。

1.1 栈的实现

栈的实现一般可以使用数组或者链表实现,相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。

1.1.1栈的接口声明

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


typedef int STDATATYPE;

typedef struct Stack
{
	STDATATYPE * _a;
	int _top;
	STDATATYPE _capatity;
}Stack;
//初始化栈
void StackInit(Stack* ps);
//入栈
void StackPushBack(Stack* ps,STDATATYPE x);
//出栈
void StackPopBack(Stack* ps);
//获取栈顶元素
STDATATYPE* StackTop(Stack* ps);
//获取栈内有效元素个数
int StackSize(Stack* ps);
//判空
int StackEmpty(Stack* ps);
//销毁栈
void StackDestory(Stack* ps);

1.1.2 初始化栈

//初始化栈
void StackInit(Stack* ps)
{
	assert(ps);
	ps->_top = 0;
	ps->_a = (STDATATYPE*)malloc(sizeof(STDATATYPE)*4);
	ps->_capatity = 4;
}

 1.1.3 入栈

//入栈
void StackPushBack(Stack* ps, STDATATYPE x)
{
	assert(ps);
	if (ps->_top == ps->_capatity)
	{
		STDATATYPE* tmp = (STDATATYPE*)realloc(ps->_a,sizeof(ps->_capatity)*ps->_capatity * 2);//此处为_capatity类型大小乘个数乘倍数
		ps->_capatity *= 2;
		if (tmp != NULL)
		{
			ps->_a = tmp;
		}
		else
		{
			printf("内存不足\n");
		}
	}
	ps->_a[ps->_top] = x;
	ps->_top++;
	
}

1.1.4 出栈

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

 1.1.5 获取栈顶元素

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

1.1.6 获取栈内有效元素个数

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

1.1.7 判空

//判空
int StackEmpty(Stack* ps)
{
	return ps->_top > 0 ? 0 : 1;
}

1.1.8 销毁栈

//销毁栈
void StackDestory(Stack* ps)
{	
	assert(ps);
	free(ps->_a);
}

2 队列

2.1 队列的实现

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

2.1.1 队列的接口声明

#pragma once
#include <stdlib.h>
#include <stdio.h>
#include <assert.h>
typedef int QUDATATYPE;

typedef struct QueueNode
{
	struct QueueNode *_pnext;
	QUDATATYPE data;
}QueueNode;

typedef struct Queue
{
	QueueNode* _front;
	QueueNode* _rear;
}Queue;

//初始化队列
void QueueInit(Queue* pq);
//入队
void QueuePush(Queue* pq,QUDATATYPE x);
//出队
void QueuePop(Queue* pq);
//获取队头元素
QUDATATYPE QueueFront(Queue* pq);
//获取队尾元素
QUDATATYPE QueueBack(Queue* pq);
//获取对内有效元素个数
int QueueSize(Queue* pq);
//判空
int QueueEmpty(Queue* pq);
//销毁队列
void QueueDestory(Queue* pq);

 2.1.2 初始化队列

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

2.1.3入队

//入队
void QueuePush(Queue* pq,QUDATATYPE x)
{
	QueueNode* node = (QueueNode*)malloc(sizeof(QueueNode));
	node->data = x;
	assert(pq);
	if (pq->_rear == NULL)
	{
		pq->_rear = node;
		pq->_front = node;
	}
	else
	{
		pq->_rear->_pnext = node;
		pq->_rear = node;
	}
	pq->_rear->_pnext = NULL;
}

2.1.4出队

//出队
void QueuePop(Queue* pq)
{
	assert(pq);
	QueueNode* tmp = pq->_front->_pnext;
	free(pq->_front);
	pq->_front = tmp;
	
}

2.1.5 获取队头元素

//获取队头元素
QUDATATYPE QueueFront(Queue* pq)
{
	assert(pq);
	return pq->_front->data;
}

2.1.6 获取队尾元素

//获取队尾元素
QUDATATYPE QueueBack(Queue* pq)
{
	assert(pq);
	return pq->_rear->data;
}

2.1.7 获取队内有效元素个数

int QueueSize(Queue* pq)
{

	assert(pq);
	QueueNode* cur=pq->_front;
	int count=0;
	while (cur)
	{
		count++;
		cur=cur->_pnext;
	}
	return count;
}

2.1.8 判空

int QueueEmpty(Queue* pq)
{
	assert(pq);
	if (pq->_front ==NULL)
	{
		return 1;
	}
	return 0;
}

2.1.9 销毁队列

void QueueDestory(Queue* pq)
{
	assert(pq);
	QueueNode* next = NULL;
	if (pq->_front != NULL)
	{
		next = pq->_front->_pnext;
	}
	
	while (pq->_front)
	{
		free(pq->_front);
		pq->_front = next;
		if(next!=NULL)
			next = next->_pnext;
	}
	pq->_front = NULL;
	pq->_rear = NULL;
}

标签:ps,pq,队列,void,Queue,实现,front,Stack
From: https://blog.csdn.net/m0_63703622/article/details/141688328

相关文章

  • Apache顶级项目ShardingSphere — SQL Parser的设计与实现
    导语:SQL作为现代计算机行业的数据处理事实标准,是目前最重要的数据处理接口之一,从传统的DBMS(如MySQL、Oracle),到主流的计算框架(如spark,flink)都提供了SQL的解析引擎,因此想对sql进行精细化的操作,一定离不开SQLParser。ApacheShardingSphere是一套开源的分布式数据库中间件解决方......
  • Java中的并发控制算法:如何实现高效的锁机制与无锁编程
    Java中的并发控制算法:如何实现高效的锁机制与无锁编程大家好,我是微赚淘客系统3.0的小编,是个冬天不穿秋裤,天冷也要风度的程序猿!在多线程环境中,如何保证数据的正确性和一致性是个重要的问题。为了解决这个问题,Java提供了多种并发控制算法,主要包括锁机制和无锁编程。本文将介......
  • 基于协同过滤算法的电影推荐系统的设计与实现(论文+源码)_kaic
    摘 要现在观看电影已逐渐成为人们日常生活中最常见的一种娱乐方式,人们通常会在周末或在休息、吃饭时间不由自主地在各种视频软件中搜索当前火热的影视节目。但是现在的视频软件电影推荐功能不够完善,所以需要开发出一套系统来使用户只需要简单操作就能找到喜爱的影片。针对这......
  • Apache顶级项目ShardingSphere — SQL Parser的设计与实现
    导语:SQL作为现代计算机行业的数据处理事实标准,是目前最重要的数据处理接口之一,从传统的DBMS(如MySQL、Oracle),到主流的计算框架(如spark,flink)都提供了SQL的解析引擎,因此想对sql进行精细化的操作,一定离不开SQLParser。ApacheShardingSphere是一套开源的分布式数据库中间件解决方案......
  • springboot+vue安心养老一站通服务系统的设计与实现【程序+论文+开题】计算机毕业设计
    系统程序文件列表开题报告内容研究背景随着社会老龄化的加速,养老问题已成为全球性的社会挑战。传统的养老模式面临着资源分配不均、服务效率低下、信息孤岛等诸多问题,难以满足老年人日益增长的多元化、个性化需求。在此背景下,安心养老一站通服务系统的设计与实现显得尤为重......
  • MYSQL实现Oracle中decode函数
    背景:写oracle脚本迁移mysql时,mysql不支持decode函数思路:理解decode函数使用方法及参数含义1、decode(expression,value,result1,result2)     理解:如果expression=value,则输出result1,否则输出result22、decode(expression,value1,result1,value2,result2,value3,res......
  • WebTopo连同ARMxy实现数字化转型可视化解决方案
    随着工业4.0的迅猛发展,企业对于实时数据监控、设备管理和智能化生产的需求日益增加。为了满足这些需求,WebTopo与ARMxy携手推出了一套高效、灵活的数字化转型可视化解决方案。本文将详细介绍WebTopo软件、钡铼ARMxy系列BL340嵌入式计算机,并探讨它们如何共同支持数字化转型。一、WebT......
  • Redis高可用方案:使用Keepalived实现主备双活
    注意:请确保已经安装Redis和keepalived,本文不在介绍如何安装。1、使用版本说明Redis版本:5.0.2Keepalived版本:1.3.5Linux版本:Centos7.9查看Redis版本:/usr/local/redis/bin/redis-cli-v查看Keepalived版本信息:rpm-qa|grepkeepalived或者keepalived-v2、功能实......
  • 神策SDK不支持Windows客户端全埋点,怎么实现用户统计分析?
    本文将介绍,ClkLog针对神策不支持全埋点的客户端实现用户访问基础统计分析-1。● ClkLog客户遇到的问题ClkLog的用户访问基础统计分析功能是基于神策SDK的全埋点来实现的。我们遇到有些客户是使用C++、C#等语言来开发的客户端,然而神策此类SDK(如C++,C#等)仅提供自定义事件埋点,并未......
  • SZARP协助ARMxy边缘计算机实现智能工厂可视化解决方案
    在智能工厂的构建中,SZARP与ARMxy边缘计算机的协同作用,实现了设备的实时监控、深入的数据分析和有效的预测性维护,极大地提高了生产效率和产品质量。通过智能制造可视化技术,企业能够清晰地掌握生产流程的每一个环节,实现资源的最优分配和流程的最优化管理。一、SZARP简介SZARP集成了数......