数据结构严蔚敏版精简版-栈和队列以及c语言代码实现

1栈的定义和特权

栈(stack)是限定仅在表尾进行插入或删除操作的线性表。

注：虽然说栈的实现就是一端插入和删除，但不一定是在“表尾”，这个“表尾”是广义的。

头插法实现链栈

尾插法实现链栈

因此，对栈来说，表尾端有其特殊含义，称为栈顶(top),相应地，表头端称为栈底(bottom)。不含元素的空表称为空栈。

2队列的定义和特权

和栈相反，队列(queue)是一种先进先出(First In First Out, FIFO)的线性表。它只允许在表 的一端进行插入，而在另一端删除元素。

如果入队序列为1，2，3，4出队序列也为1，2，3，4

队列在程序设计中也经常出现。一个最典型的 例子就是操作系统中的作业排队。在允许多道程序 运行的计算机系统中，同时有几个作业运行。如果运行的结果都需要通过通道输出，那就要按请求 输入的先后次序排队。每当通道传输完毕可以接受新的输出任务时，队头的作业先从队列中退出 做输出操作。凡是申请输出的作业都从队尾进入队列。

python实现LRU置换算法和先进先出算法

2.1循环队列

假设当前队列分配的最大空间为6,则当队列处于图d所示的状态时不可再继续 插入新的队尾元素，否则会出现溢出现象，即因数组越界而导致程序的非法操作错误。事实 上，此时队列的实际可用空间并未占满，所以这种现象称 为“假溢出＂。这是由＂队尾入队，队头出队”这种受限制 的操作造成的。

最常用的方式是少用一个元素空间， 即队列空间大小为m时，有m-1个元素就认为是队满。这样判断队 空的条件不变， 即当头、尾指针的值相同时，则认为队空；而当尾指针在循环意义上加1后是等 千头指针，则认为队满。因此，在循环队列中队空和队满的条件是：

队空的条件： Q.front = Q.rear

队满的条件： (Q rear+ 1)%M心CQSIZE= Q.front

入队尾指针变化：Q.front=(Q.front+1)%m

出队头指针变化：Q.front=(Q.front+1)%m

void EnQueue(Queue *Q,Elemtype x)//入队 
{
	if((Q->tail+1)%MAX_QUEUE==Q->front)
		{
		printf("已满\n");
		return;
		}
	Q->base[Q->tail]=x;
	Q->tail=(Q->tail+1)%MAX_QUEUE;
	printf("%d已经入队\n",x); 
}
void DeQueue(Queue *Q)//出队 
{	printf("%d出队\n",Q->base[Q->front]);
	Q->front=(Q->front+1)%MAX_QUEUE;
}

3栈和队列的实现c语言

3.1顺序栈的实现

#define STACK_INC_SIZE 3
#include<stdio.h>
#include<malloc.h>
#include<assert.h>
#include <iostream>
#define MAX_SIZE 8

#define Elemtype char 
typedef struct stack{
	Elemtype *base;
	int top;
	int stacksize;
}Sqstack;

void Initstack(Sqstack *S)//初始化 
{
	S->base=(Elemtype*)malloc(sizeof(Elemtype)*MAX_SIZE);
	S->stacksize=8;
	S->top=0; 
 } 
 void show(Sqstack *S)//查看栈内元素 
 {
 	for(int i=S->top-1;i>=0;i--)
 	{
 		printf("%d\n",S->base[i]);
	}
 }
 bool IsFull(Sqstack *S)//判断是否满 
 {
 	return S->top>=S->stacksize; 
  } 
 bool IsEmpty(Sqstack *S)//判断是否为空栈 
 {
 	return S->top==0;
 }
 bool Inc(Sqstack *s)//栈满了则扩容，如果内存不够扩容则失败 
 {
 	Elemtype *newbase=(Elemtype*)realloc(s->base,sizeof(Elemtype)*(s->stacksize+STACK_INC_SIZE));
 	if(newbase==NULL)
 	{
 		printf("满了");
		 return false; 
	 }
	 s->base=newbase;
	 s->stacksize+=STACK_INC_SIZE;
	 return true;
 }
 
 void push(Sqstack *S,Elemtype x)//入栈 
 {
	if(IsFull(S)&&!Inc(S))
	{
		printf("满了,%d不能入栈\n",x);
		return;
	}
	S->base[S->top++]=x;
 }
 void pop(Sqstack *S)//出栈 
 {
 	if(IsEmpty(S))
 	{
 		printf("空的");
 		return;
	 }
	 S->top--;
 }
Elemtype Gettop(Sqstack *S) //获取栈顶元素 
 {
 	if(IsEmpty(S))
 	{
 		return false;
	 }
	 return S->base[S->top-1];
 }
 int length(Sqstack *S)//长度 
 {
 	return S->top;
 }
 void clear(Sqstack *S)//清空栈 
 {
 	S->top=0;
 }
 void destory(Sqstack *S)//销毁栈 
 {
 	free(S->base);
 	S->base=NULL;
 	S->stacksize=S->top==0;
 }
 
void conversion(int value)//进制转换 
{	Sqstack s;
	Initstack(&s);
	
	while(value)
	{
		push(&s,value%8);
		value=value/8;
	}
	while(!IsEmpty(&s))
{	int v;
	v=Gettop(&s);
	pop(&s);
	printf("%d",v);
	}	
}

bool Cheack(char *str)//括号匹配 
{ char v;
	Sqstack s;
	Initstack(&s);
	while(*str !='0')
	{
		if(*str=='['||*str=='(')
		{
			push(&s,*str);
		}
		else if(*str==']')
	{
		 v=Gettop(&s);
		if(v!='[')
			return false;
			pop(&s);
	}
	else if(*str==')')
	{
		 v=Gettop(&s);
		if(v!='(')
			return false;
			pop(&s);
	}
	++str;
	}
	return IsEmpty(&s);
}
int main(void)
{
	char *str="[())]";
	bool flag=Cheack(str);
	if(flag)
	{
		printf("OK\n");
	}
	else{
		printf("False");
	}
	
	
 } 
/*
int main()
{
	Elemtype Itim;
	Sqstack S;
	Initstack(&S);
	//conversion(13456);
	/*for(int i=1;i<=10;i++)
	push(&S,i);
	show(&S);
	Itim=Gettop(&S);
	printf("%d出栈\n",Itim);
	pop(&S);
	show(&S);
	}*/

3.2队列的实现

由于队列的实现比较简单，文章的开头就给出了2种链栈的实现方式，由于循环队列一直是队列的热门考点，这里只实现循环队列。

#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>

#define Elemtype int
#define MAX_QUEUE 8//最大数量为8个 
typedef struct Queue{
	Elemtype *base;//基地址 
	int front;//队头头 
	int tail;//队尾 
}Queue;

void InitQueue(Queue *Q)//初始化队列 
{
	Q->base=(Elemtype*)malloc(sizeof(Elemtype)*MAX_QUEUE);
	Q->front=Q->tail=0;
}

void EnQueue(Queue *Q,Elemtype x)//入队 
{
	if((Q->tail+1)%MAX_QUEUE==Q->front)
		{
		printf("已满\n");
		return;
		}
	Q->base[Q->tail]=x;
	Q->tail=(Q->tail+1)%MAX_QUEUE;
	printf("%d已经入队\n",x); 
}

void show(Queue *Q)//展示队列 
{
	for(int i=Q->front;i!=Q->tail;)
	{
	
	printf("%d  ",Q->base[i]);
	i=(i+1)%MAX_QUEUE;
	}
	
	printf("\n");
}
void DeQueue(Queue *Q)//出队 
{	printf("%d出队\n",Q->base[Q->front]);
	Q->front=(Q->front+1)%MAX_QUEUE;
}
int lenQueue(Queue *Q) 
{
	return (Q->tail-Q->front);
}
void Gethead(Queue *Q,Elemtype *x)//获取对头元素 
{
if(Q->front==Q->tail)
	return;
	
	*x=Q->base[Q->front];
}
void ClearQueue(Queue *Q)//清空 
{
	Q->front=Q->tail=0;
}
void DestroyQueue(Queue *Q)//销毁 
{
	ClearQueue(Q);
	free(Q->base);
	Q->base=NULL;
}

int main()
{	int x;
	Queue Q;
	InitQueue(&Q);
	EnQueue(&Q,1);
	EnQueue(&Q,2);
	EnQueue(&Q,3);
	EnQueue(&Q,4);
	DeQueue(&Q);
	show(&Q);
	printf("队列长%d\n",lenQueue(&Q));
	Gethead(&Q,&x);
	printf("队头元素为%d\n",x);
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/693338.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

从GAN到WGAN（01/2）

从GAN到WGAN（01/2）

从GAN到WGAN 文章目录 一、说明二、Kullback-Leibler 和 Jensen-Shannon 背离三、生成对抗网络 &#xff08;GAN&#xff09;四、D 的最优值是多少&#xff1f;五、什么是全局最优&#xff1f;六、损失函数代表什么&#xff1f;七、GAN中的问题 一、说明 生成对抗网络 &#…
阅读更多...
13_前端工程化_ES6

13_前端工程化_ES6

1.前端工程化概念 前端工程化是使用软件工程的方法来单独解决前端的开发流程中模块化、组件化、规范化、自动化的问题,其主要目的为了提高效率和降低成本。 前后端分离&#xff08;前端代码工程化独立出来形成一个单独的app&#xff09; 1.开发分离 2.部署分离 3.服务器分离…
阅读更多...
012-Linux逻辑卷管理（LVM）

012-Linux逻辑卷管理（LVM）

前言 安装 Linux 操作系统时遇到的⼀个常见的难以决定的问题就是如何正确地评估各分区大小&#xff0c;以分配合适的硬盘空间; 基本的磁盘分区管理方式在逻辑分区划分好之后就无法改变其大小。随着 Linux的逻辑卷管理功能的出现&#xff0c;这些问题都迎刃而解&#xff0c;用户…
阅读更多...
如何计算 GPT 的 Tokens 数量？

如何计算 GPT 的 Tokens 数量？

基本介绍 随着人工智能大模型技术的迅速发展&#xff0c;一种创新的计费模式正在逐渐普及&#xff0c;即以“令牌”&#xff08;Token&#xff09;作为衡量使用成本的单位。那么&#xff0c;究竟什么是Token呢&#xff1f; Token 是一种将自然语言文本转化为计算机可以理解的…
阅读更多...
论文阅读：All-In-One Image Restoration for Unknown Corruption

论文阅读：All-In-One Image Restoration for Unknown Corruption

发表时间&#xff1a;2022 cvpr 论文地址&#xff1a;https://openaccess.thecvf.com/content/CVPR2022/papers/Li_All-in-One_Image_Restoration_for_Unknown_Corruption_CVPR_2022_paper.pdf 项目地址&#xff1a;https://github.com/XLearning-SCU/2022-CVPR-AirNet 在本文…
阅读更多...
Word Split Line

Word Split Line

Word Split Line 分割线 https://download.csdn.net/download/spencer_tseng/89413772
阅读更多...
将字符串str1复制为字符串str2

将字符串str1复制为字符串str2

定义两个字符数组str1和str2&#xff0c;再设两个指针变量p1和p2&#xff0c;分别指向两个字符数组中的有关字符&#xff0c;通过改变指针变量的值使它们指向字符串中的不同的字符&#xff0c;以实现字符的复制。编写程序&#xff1a; 运行程序&#xff1a; 程序分析&#xff1…
阅读更多...
MySQL 与 PostgreSQL 关键对比二（SQL语法）

MySQL 与 PostgreSQL 关键对比二（SQL语法）

目录 1 详细示例 1.1自动增量列 1.2 字符串连接 1.3 JSON 支持 2 总结 MySQL 和 PostgreSQL 是两种流行的开源关系数据库管理系统&#xff08;RDBMS&#xff09;。尽管它们在许多方面相似&#xff0c;但在 SQL 语法和功能上存在一些显著差异。 以下SQL语句的执行如果需要开…
阅读更多...
向量数据库是什么？

向量数据库是什么？

向量数据库是什么&#xff1f; 随着人工智能和机器学习技术的迅猛发展&#xff0c;向量数据库作为一种新型数据库引起了广泛关注。向量数据库专门用于存储和查询高维向量数据&#xff0c;是在大规模数据检索和相似性搜索领域的重要工具。 向量数据库的定义 向量数据库是一种…
阅读更多...
SLAM小题目

SLAM小题目

1、最小二乘题目&#xff1a; 假设有三个WIFI热点&#xff0c;位置分别在(x1,y1), (x2,y2), (x3,y3), 移动端测量到每一个热点的距离L1,L2和L3&#xff0c;要求解移动端的位置. #include <iostream> #include <vector> #include <cmath> class Point { pub…
阅读更多...
ssm601基于ssm框架的校园闲置物品交易平台+jsp【已测试】

ssm601基于ssm框架的校园闲置物品交易平台+jsp【已测试】

前言&#xff1a;&#x1f469;‍&#x1f4bb; 计算机行业的同仁们&#xff0c;大家好&#xff01;作为专注于Java领域多年的开发者&#xff0c;我非常理解实践案例的重要性。以下是一些我认为有助于提升你们技能的资源&#xff1a; &#x1f469;‍&#x1f4bb; SpringBoot…
阅读更多...
抓住时机的核心：坚持学习准备着

抓住时机的核心：坚持学习准备着

在这个快节奏的时代&#xff0c;时间对于每个人来说都是宝贵的。能否在合适的时间做正确的事情&#xff0c;往往决定了我们成功的概率。但同时&#xff0c;我们也要认识到&#xff0c;逆风翻盘虽少&#xff0c;却并非不可能。在这个过程中&#xff0c;投资自己&#xff0c;投资…
阅读更多...
28-LINUX--I/O复用-epoll

28-LINUX--I/O复用-epoll

一.epoll概述 epoll 是 Linux 特有的 I/O 复用函数。它在实现和使用上与 select、poll 有很大差异。首 先&#xff0c;epoll 使用一组函数来完成任务&#xff0c;而不是单个函数。其次&#xff0c;epoll 把用户关心的文件描述 符上的事件放在内核里的一个事件表中。从而无需像…
阅读更多...
计算机网络--应用层

计算机网络--应用层

计算机网络–计算机网络概念 计算机网络–物理层 计算机网络–数据链路层 计算机网络–网络层 计算机网络–传输层 计算机网络–应用层 1. 概述 因为不同的网络应用之间需要有一个确定的通信规则。 1.1 两种常用的网络应用模型 1.1.1 客户/服务器模型&#xff08;Client/Se…
阅读更多...
[office] excel工作表数据分级显示 #其他#笔记

[office] excel工作表数据分级显示 #其他#笔记

excel工作表数据分级显示 如下图1所示的工作表数据&#xff0c;我们按东区、西区、南区、北区来建立分级显示。 图1 这里先利用“创建组”命令建立分级显示。选取单元格区域A3:E5&#xff0c;单击功能区“数据”选项卡“分级显示”组中的“创建组——创建组…”命令&#xff…
阅读更多...
基于小波多分辨分析的一维时间序列信号趋势检测与去除(MATLAB R2018a)

基于小波多分辨分析的一维时间序列信号趋势检测与去除(MATLAB R2018a)

小波最开始是数学上提出的概念&#xff0c;并且在纯数学的王国里存在了一个世纪之久。最开始是为了弥补傅里叶分析的缺陷&#xff0c;即傅里叶级数发散的问题&#xff0c;并寻找出能够代替傅里叶分析的方法。从最早的一些艰难的探索开始直到慢慢发展成为一套完整系统的小波分析…
阅读更多...
Git配置 安装及使用

Git配置 安装及使用

团队开发的神 找工作必备 环境变量 配置好环境后 打开终端环境 winr cmd 我习惯在桌面打开&#xff0c;然后进入相应的文件夹 &#xff08;文件夹结构&#xff09; &#xff08;个人感觉能用cmd不用git&#xff0c;cmd更好用一些&#xff09; 进入对应的文件夹 填写自己对…
阅读更多...
Web3设计风格和APP设计风格

Web3设计风格和APP设计风格

Web3设计风格和传统APP设计风格在视觉和交互设计上有一些显著的区别。这些差异主要源于Web3技术和理念的独特性&#xff0c;以及它们在用户体验和界面设计中的具体应用。以下是Web3设计风格与传统APP设计风格的主要区别。北京木奇移动技术有限公司&#xff0c;专业的软件外包开…
阅读更多...
Elasticsearch最佳生产实践整理，推荐收藏

Elasticsearch最佳生产实践整理，推荐收藏

前言 Elasticsearch是一个底层基于Lucene的全文搜索和分析引擎&#xff0c;支持近乎实时地存储、搜索和分析大量数据的能力&#xff0c;最常用于网站搜索、日志搜索、数据分析等场景。 本文主要针对日常工作中Elasticsearch使用的一些基础概念、使用规范、注意事项、常见优化…
阅读更多...
GPU风扇不旋转：为什么会发生这种情况以及如何修复

GPU风扇不旋转：为什么会发生这种情况以及如何修复

GPU在处理数百万像素时往往会发热，因此冷却风扇静音可能会令人担忧，这是可以理解的！如果你注意到你的GPU风扇没有旋转，下面是如何评估是否存在真正的问题，以及如何解决问题。 风扇停止旋转可能是一个功能，而不是一个Bug 如果GPU没有用于密集任务或没有达到高温，则可以…
阅读更多...
最新文章

Copyright @ 2022~2023