03-数据结构-栈与队列

1.栈

77a8072800534dd1b6072ce98752205d.png

栈和队列是两种操作受限的线性表。如上图所示显示栈的结构

栈：先进后出，入栈（数据进入） 和出栈（数据出去）均在栈顶操作。

常见栈的应用场景包括括号问题的求解，表达式的转换和求值，函数调用和递归实现

1.1 栈的代码实现

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

typedef int STDataType;
typedef struct node
{
	STDataType x;
	struct node* next;
}node;
typedef struct Stack
{
	node* head;
	int nums;		// 长度
}Stack;

// 初始化栈 
void StackInit(Stack* ps)
{
	assert(ps);
	ps->head = NULL;
	ps->nums = 0;
}

// 入栈 
void StackPush(Stack* ps, STDataType data)
{
	assert(ps);
	node* new_node = (node*)malloc(sizeof(node));
	new_node->x = data;
	new_node->next = ps->head;
	ps->head = new_node;
	ps->nums++;
}

// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
int StackEmpty(Stack* ps)
{
	assert(ps);
	return ps->nums == 0;
}

// 出栈 
STDataType StackPop(Stack* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	STDataType ret = ps->head->x;
	node* del = ps->head;
	ps->head = ps->head->next;
	free(del);
	ps->nums--;
	return ret;
}

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

// 销毁栈 
void StackDestroy(Stack* ps)
{
	assert(ps);
	node* tmp = ps->head;
	while (tmp)
	{
		ps->head = ps->head->next;
		free(tmp);
		tmp = ps->head;
	}
	ps->head = NULL;
	ps->nums = 0;
}

int main()
{
	Stack sta;
	StackInit(&sta);
	StackPush(&sta, 1);
	StackPush(&sta, 2);
	StackPush(&sta, 3);
	StackPush(&sta, 4);
	StackPush(&sta, 5);
	std::cout << StackSize(&sta) << std::endl;
	while (!StackEmpty(&sta))
	{
		printf("%d\n", StackPop(&sta));
	}
}

1.2 进制转化

#include <iostream>
#include <malloc.h>

using namespace std;

/**** 结 构 体 声 明 ****/
typedef struct scStack{
    struct scStack *next;
    int elem;
}scStack;

/*
    余数入栈
*/
scStack *push(scStack *stack,int elem){
    scStack *newStack = (scStack *)malloc(sizeof(scStack));
    newStack->elem = elem;
    newStack->next = stack;
    stack = newStack;
    return stack;
}

/*
    进制转换
*/
scStack *sysConvert(int num,int system,scStack *sys){
    while(num > 0){
        sys = push(sys,num % system);
        num /= system;
    }
    return sys;   //返回栈顶
}

/*
   余数出栈
*/
void pop(scStack *stack){
    while(stack){
        scStack *top = stack;
        top->elem >= 10 ? printf("%c",top->elem + 'a' - 10) : printf("%d",top->elem);
        stack = stack->next;
        free(top);
    }
    cout<<endl<<"转换完毕！"<<endl;
}

/*
    主函数
*/
int main(){
    scStack *stack = NULL; //初始化栈
    int num,system;
    cout<<"请输入一个10进制数：";
    cin>>num;
    cout<<"请输入想要转换为多少进制：";
    cin>>system;
    stack = sysConvert(num,system,stack);
    pop(stack);
    return 0;
}

1.3 括号匹配

#include<stdio.h>

#define MaxSize 10

typedef struct {    // 定义顺序栈
    int data[MaxSize];  // 静态数组存放栈中元素
    int top;    // 栈顶指针：指向目前栈顶元素的位置
} SeqStack;

void InitStack(SeqStack &S) {
    S.top = -1;
}

bool StackEmpty(SeqStack S) {
    if(S.top == -1) {
        return true;
    } else {
        return false;
    }
}

bool Push(SeqStack &S, char x) {
    if(S.top == MaxSize - 1) {
        return false;
    }
    S.top = S.top + 1;
    S.data[S.top] = x;
    return true;
}

bool Pop(SeqStack &S, char &x) {
    if(S.top == -1) {
        return false;
    }
    x = S.data[S.top];
    S.top = S.top - 1;
    return true;
}

bool bracketCheck(char str[], int length) {
    SeqStack S;
    InitStack(S);
    for(int i = 0;i < length;i++) {
        if(str[i] == '(' || str[i] == '[' || str[i] == '{') {
            Push(S, str[i]);
        } else {
            if(StackEmpty(S)) {
                return false;
            }
            char topElem;
            Pop(S, topElem);
            if(str[i] == ')' && topElem != '(') {
                return false;
            }
            if(str[i] == ']' && topElem != '[') {
                return false;
            }
            if(str[i] == '}' && topElem != '{') {
                return false;
            }
        }
    }
    return StackEmpty(S);
}

int main() {
    char A[] = "[([][])]";
    if(bracketCheck(A, 8)) {
        printf("A The match is successful\n");
    }
	else
	{
		printf("A The match is faild\n");
	}
	
	char B[] = "[([][]]";
    if(bracketCheck(B, 8)) {
        printf("B The match is successful\n");
    }
	else
	{
		printf("B The match is faild\n");
	}
}

1.4 递归

//X有n个盘子，从上到下有从小到大的顺序，有三个柱子X，Y, Z,把n个盘子从X移到Z，
//Y为辅助，并在移动过程中有一个约束条件就是大盘永远不能在小盘上面。
//
#include <stdio.h>
#include <stdlib.h>

#define MAXSIZE 100

typedef int ElemType;//盘子的结构
typedef struct//柱子（栈）的结构
{
    char name;
    ElemType* base;
    ElemType* top;
}StackType;
 
int initstack(StackType* s,char name)
{
    s->name=name;
    s->base=(ElemType*)malloc(MAXSIZE*sizeof(ElemType));
    if(s->base==NULL)
        exit(0);
    s->top=s->base;
    return 1;
 
 
}
 
int push(StackType* s,ElemType e)
{
    if(s->top-s->base>=MAXSIZE)
        exit(0);
    *(s->top)=e;
    s->top++;
    return 1;
}
 
ElemType pop(StackType* s)
{
    if(s->top==s->base)
        exit(0);
    s->top--;
    return *(s->top);
}
 
int main()
{
    int all;
    int i;
    StackType X;
    StackType Y;
    StackType Z;
    initstack(&X,'X');
    initstack(&Y,'Y');
    initstack(&Z,'Z');
    while(1)
    {
    printf("请输入X柱子开始有多少个盘子\n");
    scanf("%d",&all);
    for(i=all;i>0;i--)
    {
        push(&X,i);
    }
    hannota(all,&X,&Y,&Z);
    }
 
 
    return 1;
}
 
int hannota(int n,StackType* x,StackType* y,StackType* z)
{
    if(1==n)
    {
        move(x,z);
        printf("from %c to %c\n",x->name,z->name);
        return 1;
    }
    hannota(n-1,x,z,y);//先解决n-1个盘子移到辅助柱子Y的汉洛塔问题
    move(x,z);//最后一个从x移到Z
    printf("from %c to %c\n",x->name,z->name);
    hannota(n-1,y,x,z);//解决n-1个盘子移到柱子z的汉洛塔问题
    return 1;
}
 
int move(StackType* s1,StackType* s2)
{
    ElemType temp;
    temp=pop(s1);
    push(s2,temp);
    return 1;
}

2.队列

队列的应用场景包括计算机系统中各种资源的管理，消息缓冲器的管理和广度优先搜索遍历等。

队列是先进先出，如上图所示，队列从队尾入队，从队头出队。队列有顺序队列，链队列和循环队列

2.1 链队列的代码实现

#include <stdio.h>
#include <malloc.h>
typedef char ElemType;
typedef struct DataNode
{	
	ElemType data;
	struct DataNode *next;
} DataNode;				//链队数据结点类型
typedef struct
{	
	DataNode *front;
	DataNode *rear;
} LinkQuNode;			//链队类型
void InitQueue(LinkQuNode *&q)
{	
	q=(LinkQuNode *)malloc(sizeof(LinkQuNode));
	q->front=q->rear=NULL;
}
void DestroyQueue(LinkQuNode *&q)
{
	DataNode *p=q->front,*r;//p指向队头数据结点
	if (p!=NULL)			//释放数据结点占用空间
	{	r=p->next;
		while (r!=NULL)
		{	free(p);
			p=r;r=p->next;
		}
	}
	free(p);
	free(q);				//释放链队结点占用空间
}
bool QueueEmpty(LinkQuNode *q)
{
	return(q->rear==NULL);
}
void enQueue(LinkQuNode *&q,ElemType e)
{	DataNode *p;
	p=(DataNode *)malloc(sizeof(DataNode));
	p->data=e;
	p->next=NULL;
	if (q->rear==NULL)		//若链队为空,则新结点是队首结点又是队尾结点
		q->front=q->rear=p;
	else
	{	q->rear->next=p;	//将p结点链到队尾,并将rear指向它
		q->rear=p;
	}
}
bool deQueue(LinkQuNode *&q,ElemType &e)
{	DataNode *t;
	if (q->rear==NULL)		//队列为空
		return false;
	t=q->front;				//t指向第一个数据结点
	if (q->front==q->rear)  //队列中只有一个结点时
		q->front=q->rear=NULL;
	else					//队列中有多个结点时
		q->front=q->front->next;
	e=t->data;
	free(t);
	return true;
}
int main()
{
	LinkQuNode *q;     //创建队列q  
	ElemType e;
	InitQueue(q);   //初始化队
	enQueue(q,'a');
	enQueue(q,'b');
	enQueue(q,'c'); //依次进队a,b,c
	deQueue(q,e);
	printf("%c\n",e);   //出队元素a 
	deQueue(q,e);
	printf("%c\n",e);  //出队元素b 
	deQueue(q,e);
	printf("%c\n",e);  //出队元素c
	DestroyQueue(q);  //销毁队 
	return 0; 
}

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

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

相关文章

记录每日LeetCode 162.寻找峰值与1901.寻找峰值II Java实现

记录每日LeetCode 162.寻找峰值与1901.寻找峰值II Java实现

寻找峰值 题目描述&#xff1a; 峰值元素是指其值严格大于左右相邻值的元素。 给你一个整数数组 nums&#xff0c;找到峰值元素并返回其索引。数组可能包含多个峰值&#xff0c;在这种情况下&#xff0c;返回 任何一个峰值 所在位置即可。 你可以假设 nums[-1] nums[n] -…
阅读更多...
Unity3d C#利用Editor编辑器拓展实现配置UI背景样式一键设置UI背景样式功能（含源码）

Unity3d C#利用Editor编辑器拓展实现配置UI背景样式一键设置UI背景样式功能（含源码）

前言 在开发UI滚动列表的时候&#xff0c;经常会有每项的背景图不统一的情况&#xff0c;会间隔重复的情况居多。这种情况下&#xff0c;手动去设置间隔一行的背景图或者颜色是比较麻烦的。在此背景下&#xff0c;笔者尝试写个小工具&#xff0c;在搭建UI时配置一下循环背景的…
阅读更多...
开发知识点-09Rust

开发知识点-09Rust

Rust Rust 语言通常用于编写系统级软件、网络服务器和高性能应用程序&#xff0c;它具有以下特点&#xff1a;1. 高性能和内存安全&#xff1a;Rust 在保证高性能的同时&#xff0c;利用其所有权模型和借用检查器等特性确保内存安全&#xff0c;避免了 C/C 等语言的内存错误和崩…
阅读更多...
MySQL数据库——SQL语法

MySQL数据库——SQL语法

Structured Query Language&#xff08;结构化查询语言&#xff09;&#xff0c;简称SQL&#xff0c;是用于操作关系型数据库的标准编程语言。SQL提供了一种与数据库交互的方式&#xff0c;可以用于查询、插入、更新和删除数据库中的数据。 1. SQL通用语法 SQL语句可以写在一…
阅读更多...
Jenkins Docker Cloud在Linux应用开发CI中的实践

Jenkins Docker Cloud在Linux应用开发CI中的实践

Jenkins Docker Cloud在Linux应用开发CI中的实践 背景 通过代码提交自动触发CI自动构建、编译、打包是任何软件开发组织必不可少的基建&#xff0c;可以最大程度保证产物的一致性&#xff0c;方便跨组跨部门协作&#xff0c;代码MR等。 Docker在流水线中越来越重要&#xff…
阅读更多...
行为型设计模式（一）模版方法模式 迭代器模式

行为型设计模式（一）模版方法模式 迭代器模式

模板方法模式 Template 1、什么是模版方法模式 模版方法模式定义了一个算法的骨架&#xff0c;它将其中一些步骤的实现推迟到子类里面&#xff0c;使得子类可以在不改变算法结构的情况下重新定义算法中的某些步骤。 2、为什么使用模版方法模式 封装不变部分&#xff1a;模版…
阅读更多...
Home Assistant HAOS版如何安装HACS

Home Assistant HAOS版如何安装HACS

环境&#xff1a; Home Assistant 11.2 SSH & Web Terminal 17.0 问题描述&#xff1a; Home Assistant HAOS版如何安装HACS 解决方案&#xff1a; 1.打开WEB 里面的终端输入下面命令 wget -O - https://hacs.vip/get | bash -如果上面的命令执行后卡住不动&#xff…
阅读更多...
得物-Golang-记一次线上服务的内存泄露排查

得物-Golang-记一次线上服务的内存泄露排查

1.出现内存泄漏 1.1 事发现场 在风和日丽的一天&#xff0c;本人正看着需求、敲着代码&#xff0c;展望美好的未来。突然收到一条内存使用率过高的告警。 1.2 证人证词 告警的这个项目&#xff0c;老代码是python的&#xff0c;最近一直在go化。随着go化率不断上升&#xff…
阅读更多...
maven 项目导入异常问题

maven 项目导入异常问题

问题如下 一、 tomcat正再运行的包是哪一个 不同构建、打包情况下分别运行 out\artifacts下 当直接去Project Structure下去构建artifacts 后&#xff0c;运行tomcat 则会在out下target下 reimport项目后,则会在artifacts自动生成部署包。删除tomcat之前deployment 下的包(同…
阅读更多...
Android studio Android SDK下载安装

Android studio Android SDK下载安装

我们访问地址 https://developer.android.google.cn/studio?hlzh-cn 拉下来直接点击下载 然后来下来 勾选 然后点击下载 下载好之后 我们双击打开 点击下一步 确认上面的勾选 然后下一步 这里 我们选择一下安装目录 然后点击下一步 安装 安装完之后点击进行下一步 Fin…
阅读更多...
JDK各个版本新特性

JDK各个版本新特性

JDK8新特性 Java 8 发布于 2014 年 3 月份&#xff0c;可以说是 Java 6 之后最重要的版本更新&#xff0c;深受开发者的喜爱。 函数式编程和 Lambda 表达式 Stream 流 参考&#xff1a;https://mp.weixin.qq.com/s/7hNUjjmqKcHDtymsfG_Gtw 单从“Stream”这个单词上来看&…
阅读更多...
【数据结构】栈的使用|模拟实现|应用|栈与虚拟机栈和栈帧的区别

【数据结构】栈的使用|模拟实现|应用|栈与虚拟机栈和栈帧的区别

目录 一、栈(Stack) 1.1 概念 1.2 栈的使用 1.3 栈的模拟实现 1.4 栈的应用场景 1. 改变元素的序列 2. 将递归转化为循环 3. 括号匹配 4. 逆波兰表达式求值 5. 出栈入栈次序匹配 6. 最小栈 1.5 概念区分 一、栈(Stack) 1.1 概念 栈&#xff1a;一种特殊的线性表&…
阅读更多...
解决腾讯云CentOS 6硬盘空间不足问题：从快照到数据迁移

解决腾讯云CentOS 6硬盘空间不足问题：从快照到数据迁移

引言&#xff1a; 随着数据的不断增加&#xff0c;服务器硬盘空间不足变成了许多运维人员必须面对的问题。此主机运行了httpd&#xff08;apache服务&#xff09;&#xff0c;提供对外web访问服务,web资源挂载在**/data/wwwroot目录下,http日志存放在/data/wwwlogs目录下&…
阅读更多...
创建型设计模式 | 原型模式

创建型设计模式 | 原型模式

一、原型模式 1、原理 原型模式&#xff0c;用原型实例指定创建对象的种类&#xff0c;并且通过拷贝这些原型创建新的对象。原型模式其实就是从一个对象再创建另外一个可定制的对象&#xff0c;而且不需要知道任何创建的细节。原型像是一个模板&#xff0c;可以基于它复制好多…
阅读更多...
el-form与el-upload结合上传带附件的表单数据（前端篇）

el-form与el-upload结合上传带附件的表单数据（前端篇）

1.写在之前 本文前端采用Vue element-plus技术栈&#xff0c;前端项目参考yudao-ui-admin-vue3项目与Geeker-Admin项目。 这篇文章是el-form与el-upload结合上传带附件的表单数据&#xff08;后端篇&#xff09;-CSDN博客姐妹篇&#xff0c;后端篇文章主要讲的是后端的实现逻…
阅读更多...
左移运算符(＜＜),右移运算符(＞＞)

左移运算符(＜＜),右移运算符(＞＞)

#include <stdio.h>int main() {int a 10, b 10, c -10, d -10;int a1 0, a2 0, a3 0, a4 0, a5 0; int b1 0, b2 0, b3 0, b4 0, b5 0; int c1 0, c2 0, c3 0, c4 0, c5 0; int d1 0, d2 0, d3 0, d4 0, d5 0;//a10,左移a1 a << 1; a2…
阅读更多...
JDK各个版本特性讲解-JDK14特性

JDK各个版本特性讲解-JDK14特性

JDK各个版本特性讲解-JDK14特性 一、Java14概述二、语法层面的变化1. instanceof2. switch表达式3. 文本块的改进4. Records记录类型 二、关于GC1.G1的NUMA内存分配优化2. 弃用SerialCMS,ParNewSerial Old3.删除CMS4.ZGC on macOS and Windows 三、其他变化1.友好的空指针异常提…
阅读更多...
【动态规划】08路径问题_下降路径最小和_C++（medium）

【动态规划】08路径问题_下降路径最小和_C++（medium）

题目链接&#xff1a;leetcode下降路径最小和 目录 题目解析&#xff1a; 算法原理 1.状态表示 2.状态转移方程 3.初始化 4.填表顺序 5.返回值 编写代码 题目解析&#xff1a; 题目让我们求通过 matrix 的下降路径 的 最小和 由题可得&#xff1a; 在下一行选择的元…
阅读更多...
纸白银投资开户有什么条件？

纸白银投资开户有什么条件？

在金融市场中&#xff0c;白银作为一种重要的贵金属&#xff0c;一直以来都备受投资者的关注。而纸白银&#xff0c;作为白银投资的一种形式&#xff0c;更是因其交易灵活、风险相对较小的特点&#xff0c;吸引了大量的投资者。那么&#xff0c;纸白银投资开户有什么条件呢&…
阅读更多...
国产Apple Find My认证芯片哪里找，伦茨科技ST17H6x芯片可以帮到您

国产Apple Find My认证芯片哪里找，伦茨科技ST17H6x芯片可以帮到您

深圳市伦茨科技有限公司&#xff08;以下简称“伦茨科技”&#xff09;发布ST17H6x Soc平台。成为继Nordic之后全球第二家取得Apple Find My「查找」认证的芯片厂家&#xff0c;该平台提供可通过Apple Find My认证的Apple查找&#xff08;Find My&#xff09;功能集成解决方案。…
阅读更多...
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站