【数据结构】11 堆栈（顺序存储和链式存储）

定义

可认为是具有一定约束的线性表，插入和删除操作都在一个称为栈顶的端点位置。也叫后入先出表（LIFO）
类型名称：堆栈（STACK）
数据对象集： 一个有0个或者多个元素的有穷线性表。
操作集：
（1）Stack CreateStack( int MaxSize)
生成空堆栈，其最大长度为MaxSize
（2）bool IsFull(Stack)
判断栈S是否已满。
（3）bool Push(Stack S, ElementType X)
将元素X压入堆栈
（4）ElementType Pop(Stack S)
删除并返回栈顶元素

例3.5 如果将abcd四个字符按顺序压入堆栈，是否可能产生cabd这样的序列，共可能产生多少种输出？
一个字符出入栈：只可能是A进——A出
两个字符出入栈： 2种情况
A进A出 B进B出
A进B进 B出A出
三个字符出入栈： 5种情况
A进B进C进 C出B出A出
A进B进 B出 C进 C出
A进B进 B出A出 C进C出
A进A出 B进B出 C进C出
A进A出 B进C进 C出B出
四个字符： 14种情况

  1. A在第一位出 A_ _ _
    对应3个字符出入栈 -5种情况
  2. A在第二位 _ A _ _
    只能B出来后A才能出 BA_ _
    对应2个字符出入栈 -2种情况
  3. A在第三位 _ _ A _
    前两位必是 B或者C
    最后一位必是D
    2种情况
  4. A在第四位 _ _ _ A
    对应三个字符出入栈 5种情况

堆栈的实现

顺序栈的实现

由一个一维数组和一个记录栈顶元素位置的变量组成，另外还有一个记录堆栈最大容量的变量MaxSize。
习惯将栈底放在数组下标小的那端，栈顶位置用一个整型变量Top记录当前栈顶元素的下标值。当Top指向-1时，表示空栈；当Top指向MaxSize-1时表示栈满。
顺序栈类型Stack表示如下：

typedef int ElementType;
typedef int Position;
typedef struct SNode* PtrToSNode;struct SNode {ElementType* Data;Position Top;int MaxSize;};typedef PtrToSNode Stack;

顺序栈的创建

Stack CreateStack(int MaxSize) {Stack S = (Stack)malloc(sizeof(SNode) * 1);S->Data = (ElementType * )malloc(sizeof(ElementType) * MaxSize);S->Top = -1;S->MaxSize = MaxSize;return S;
}

进栈


bool IsFull(Stack S) {if (S->Top == S->MaxSize - 1) {return true;}return false;
}bool Push(Stack S, ElementType X) {if (IsFull(S)) {printf("The Stack is full!\n");return false;}(S->Top)++;S->Data[S->Top] = X;return true;}

出栈

bool IsEmpty(Stack S) {if (S->Top == -1) {return true;}return false;
}ElementType Pop(Stack S) {if (IsEmpty(S)) {printf("The Stack is empty!\n");return -1;}int temp = S->Data[S->Top];(S->Top)--;return temp;}

完整代码

# include <stdio.h>
#include < stdlib.h>typedef int ElementType;
typedef int Position;
typedef struct SNode* PtrToSNode;struct SNode {ElementType* Data;Position Top;int MaxSize;};typedef PtrToSNode Stack;Stack CreateStack(int MaxSize) {Stack S = (Stack)malloc(sizeof(SNode) * 1);S->Data = (ElementType * )malloc(sizeof(ElementType) * MaxSize);S->Top = -1;S->MaxSize = MaxSize;return S;
}bool IsFull(Stack S) {if (S->Top == S->MaxSize - 1) {return true;}return false;
}bool Push(Stack S, ElementType X) {if (IsFull(S)) {printf("The Stack is full!\n");return false;}/*(S->Top)++;S->Data[S->Top] = X;*/S->Data[++(S->Top)] = X;return true;}bool IsEmpty(Stack S) {if (S->Top == -1) {return true;}return false;
}ElementType Pop(Stack S) {if (IsEmpty(S)) {printf("The Stack is empty!\n");return -1;}/*int temp = S->Data[S->Top];(S->Top)--;return temp;*/return (S->Data[(S->Top)--]);}void print_s(Stack S) {int t = S->Top;while (t != -1) {printf("Node: %d\n", S->Data[t]);(t)--;}
}int main() {Stack S = NULL;int MaxSize = 10;S = CreateStack(MaxSize);ElementType X;int N;scanf_s("%d", &N);while (N--) {scanf_s("%d", &X);if (Push(S, X) == false) {printf("Push error!\n");}}print_s(S);int out = Pop(S);printf("out : %d\n", out);print_s(S);}

用一个数组实现两个堆栈

在这里插入图片描述

结构体
typedef struct DSNode* DStack;
struct DSNode
{ElementType* Data;Position Top1;Position Top2;int MaxSize;
};
创建
DStack CreateDStack(int MaxSize) {DStack S = (DStack)malloc(sizeof(DSNode) * 1);S->Data = (ElementType*)malloc(sizeof(ElementType) * MaxSize);S->Top2 = -1;S->Top1 = MaxSize;S->MaxSize = MaxSize;return S;
}
入栈

bool PushX(DStack S, ElementType X, int Tag) {if (S->Top1 - S->Top2 == 1) {printf("the stack is full!\n");return false;}if (Tag == 1) {(S->Top1)--;S->Data[S->Top1] = X;}else{(S->Top2)++;S->Data[S->Top2] = X;}return true;
}
出栈

ElementType PopX(DStack S, int Tag) {if (Tag == 1) {if (S->Top1 == S->MaxSize) {printf("the stack1 is empty!\n");return -1;}else {return S->Data[(S->Top1)++];}}else {if (S->Top2 == -1) {printf("the stack2 is empty!\n");return -1;}else {return S->Data[(S->Top2)--];}}}
完整代码
# include <stdio.h>
#include < stdlib.h>typedef int ElementType;
typedef int Position;typedef struct DSNode* DStack;
struct DSNode
{ElementType* Data;Position Top1;Position Top2;int MaxSize;
};DStack CreateDStack(int MaxSize) {DStack S = (DStack)malloc(sizeof(DSNode) * 1);S->Data = (ElementType*)malloc(sizeof(ElementType) * MaxSize);S->Top2 = -1;S->Top1 = MaxSize;S->MaxSize = MaxSize;return S;
}bool PushX(DStack S, ElementType X, int Tag) {if (S->Top1 - S->Top2 == 1) {printf("the stack is full!\n");return false;}if (Tag == 1) {(S->Top1)--;S->Data[S->Top1] = X;}else{(S->Top2)++;S->Data[S->Top2] = X;}return true;
}ElementType PopX(DStack S, int Tag) {if (Tag == 1) {if (S->Top1 == S->MaxSize) {printf("the stack1 is empty!\n");return -1;}else {return S->Data[(S->Top1)++];}}else {if (S->Top2 == -1) {printf("the stack2 is empty!\n");return -1;}else {return S->Data[(S->Top2)--];}}}void print_ds(DStack S) {printf("print S1:\n");int t = S->Top1;while (t != S->MaxSize) {printf("Node: %d\n", S->Data[t]);(t)++;}printf("print S2:\n");t = S->Top2;while (t != -1) {printf("Node: %d\n", S->Data[t]);(t)--;}
}int main() {int MAXSIZE = 10;DStack S = CreateDStack(MAXSIZE);ElementType X;int N;scanf_s("%d", &N);while (N--) {scanf_s("%d", &X);if (PushX(S, X, 1) == false) {printf("Push error!\n");}if (PushX(S, X, 2) == false) {printf("Push error!\n");}}print_ds(S);int out = PopX(S,1);printf("out : %d\n", out);print_ds(S);}

链式存储的实现

栈顶指针Top就是链表的栈顶结点，栈中的其他结点通过他们的指针Next链接起来，栈底结点的Next为NULL

数据结构

typedef int ElementType;
typedef struct SNode* PtrToSNode;struct SNode {ElementType Data;PtrToSNode Next;
};typedef PtrToSNode Stack;

创建


Stack CreateStack(Stack S) {S = (Stack)malloc(sizeof(SNode) * 1);S->Next = NULL;return S;
}

入栈


bool Push(Stack S, ElementType X) {Stack temp = (Stack)malloc(sizeof(SNode));temp->Data = X;temp->Next = S->Next;S->Next = temp;return true;}

出栈

ElementType Pop(Stack S) {if (S->Next == NULL) {printf("the stack is empty!\n");return -1;}ElementType re = S->Next->Data;S->Next = S->Next->Next;return re;}

完整代码

# include <stdio.h>
#include < stdlib.h>typedef int ElementType;
typedef struct SNode* PtrToSNode;struct SNode {ElementType Data;PtrToSNode Next;
};typedef PtrToSNode Stack;Stack CreateStack(Stack S) {S = (Stack)malloc(sizeof(SNode) * 1);S->Next = NULL;return S;
}bool Push(Stack S, ElementType X) {Stack temp = (Stack)malloc(sizeof(SNode));temp->Data = X;temp->Next = S->Next;S->Next = temp;return true;}ElementType Pop(Stack S) {if (S->Next == NULL) {printf("the stack is empty!\n");return -1;}ElementType re = S->Next->Data;S->Next = S->Next->Next;return re;}void prints(Stack S) {Stack t = S->Next;while (t != NULL) {printf("Node: %d\n", t->Data);t = t->Next;}
}int main() {Stack S = NULL;S = CreateStack(S);ElementType X;int N;scanf_s("%d", &N);while (N--) {scanf_s("%d", &X);if (Push(S, X) == false) {printf("Push error!\n");}}prints(S);ElementType out = Pop(S);printf("out : %d\n", out);prints(S);}

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

如若内容造成侵权/违法违规/事实不符，请联系瞎胡闹网进行投诉反馈，一经查实，立即删除！

相关文章

Obsidian Publish的开源替代品Perlite

Obsidian Publish的开源替代品Perlite

前几天就有网友跟我说&#xff0c;freenom 的免费域名不可用了&#xff0c;10 号的时候老苏进后台看了一下&#xff0c;还有一半的域名显示为 ACTIVE&#xff0c;似乎是以 2024年6月 为限。但到 11 号&#xff0c;老苏发现博客 (https://laosu.cf) 已经访问不了了&#xff0c;这…
阅读更多...
【Linux】信号保存与信号捕捉处理

【Linux】信号保存与信号捕捉处理

信号保存与信号捕捉 一、信号保存1. 信号的发送2. 理解信号保存&#xff08;1&#xff09;信号保存原因&#xff08;2&#xff09;信号保存概念 3. 信号保存系统接口&#xff08;1&#xff09;sigset_t&#xff08;2&#xff09;sigprocmask()&#xff08;3&#xff09;sigpend…
阅读更多...
GraphicsMagick 的 OpenCL 开发记录（三十七）

GraphicsMagick 的 OpenCL 开发记录（三十七）

文章目录 如何写ScaleImage()的硬件加速函数&#xff08;十一&#xff09; <2022-05-06 周五> 如何写ScaleImage()的硬件加速函数&#xff08;十一&#xff09; “如何写ScaleImage()的硬件加速函数&#xff08;十&#xff09;”这里的代码写得比较随意&#xff0c;其中…
阅读更多...
vscode远程连接失败

vscode远程连接失败

目录 解决方案尝试1解决方案尝试2 解决方案尝试1 最近通过vscode一直使用腾讯云的服务器作为远程开发环境&#xff0c;以前一直很好用。 直到最近重装了系统之后&#xff0c;发现vscode没法对云服务器进行连接了&#xff0c;即使在远程主机添加了本地的公钥也不行。直接报错:…
阅读更多...
python-自动化篇-终极工具-用GUI自动控制键盘和鼠标-pyautogui

python-自动化篇-终极工具-用GUI自动控制键盘和鼠标-pyautogui

文章目录 用GUI自动控制键盘和鼠标pyautogui 模块鼠标屏幕位置——移动地图——pyautogui.size鼠标位置——自身定位——pyautogui.position()移动鼠标——pyautogui.moveTo拖动鼠标滚动鼠标 键盘按下键盘释放键盘 开始与结束通过注销关闭所有程序 用GUI自动控制键盘和鼠标 在…
阅读更多...
springboot178智能学习平台系统

springboot178智能学习平台系统

简介 【毕设源码推荐 javaweb 项目】基于springbootvue 的 适用于计算机类毕业设计&#xff0c;课程设计参考与学习用途。仅供学习参考&#xff0c; 不得用于商业或者非法用途&#xff0c;否则&#xff0c;一切后果请用户自负。 看运行截图看 第五章 第四章 获取资料方式 **项…
阅读更多...
正则可视化工具：学习和编写正则表达式的利器

正则可视化工具：学习和编写正则表达式的利器

引言 正则表达式是一种强大的文本匹配和处理工具&#xff0c;但对于初学者和非专业开发者来说&#xff0c;编写和理解正则表达式可能是一项具有挑战性的任务。为了帮助人们更好地学习和编写正则表达式&#xff0c;正则可视化工具应运而生。本文将探讨正则可视化工具的优点&…
阅读更多...
Infuse通过Alist添加115网盘资源

Infuse通过Alist添加115网盘资源

说明 通过Alist代理管理115网盘&#xff0c;Infuse再添加Alist代理的115网盘的WebDAV 准备一台Linux服务器安装Alist 我这里用的华为云CentOS7&#xff0c;使用Docker容器 安装Alist docker run -d --restartalways -v /etc/alist:/opt/alist/data -p 5244:5244 -e PUID0 …
阅读更多...
Javaweb之SpringBootWeb案例之事务进阶的详细解析

Javaweb之SpringBootWeb案例之事务进阶的详细解析

1.3 事务进阶 前面我们通过spring事务管理注解Transactional已经控制了业务层方法的事务。接下来我们要来详细的介绍一下Transactional事务管理注解的使用细节。我们这里主要介绍Transactional注解当中的两个常见的属性&#xff1a; 异常回滚的属性&#xff1a;rollbackFor 事…
阅读更多...
Days28 ElfBoard 板]修改开机动画

Days28 ElfBoard 板]修改开机动画

1.可能需要安装的库 elfubuntu:~/work/psplash$ sudo apt-get install build-essential libncurses5-dev elfubuntu:~/work/psplash$ sudo apt-get install libtool elfubuntu:~/work/psplash$ sudo apt-get install gettext elfubuntu:~/work/psplash$ sudo apt-get install l…
阅读更多...
Tied Block Convolution: 具有共享较薄滤波器的更简洁、更出色的CNN

Tied Block Convolution: 具有共享较薄滤波器的更简洁、更出色的CNN

摘要 https://arxiv.org/pdf/2009.12021.pdf 卷积是卷积神经网络&#xff08;CNN&#xff09;的主要构建块。我们观察到&#xff0c;随着通道数的增加&#xff0c;优化后的CNN通常具有高度相关的滤波器&#xff0c;这降低了特征表示的表达力。我们提出了Tied Block Convolutio…
阅读更多...
服务器解析漏洞及任意文件下载

服务器解析漏洞及任意文件下载

1.服务器文件解析漏洞 文件解析漏洞,是指Web容器&#xff08;Apache、nginx、iis等&#xff09;在解析文件时出现了漏洞,以其他格式执行出脚本格式的效果。从而,黑客可以利用该漏洞实现非法文件的解析。 &#xff08;1) Apache linux系统中的apache的php配置文件在/etc/apac…
阅读更多...
电气器件系列四十九：室内加热器（取暖器）

电气器件系列四十九：室内加热器（取暖器）

这个的注意事项有好大一堆&#xff0c;有几个地方挺有意思的&#xff0c;可以了解一下。 第2条&#xff0c;查了一下&#xff0c;小太阳是真的可以把旁边的东西烤到很高的温度并起火 4、可能造成开关的损坏和发热管的损坏&#xff0c;插入异物可能吧加热管搞坏 5、小太阳是发…
阅读更多...
【数据结构】哈希表的开散列和闭散列模拟实现

【数据结构】哈希表的开散列和闭散列模拟实现

哈希思想 在顺序和树状结构中&#xff0c;元素的存储与其存储位置之间是没有对应关系&#xff0c;因此在查找一个元素时&#xff0c;必须要经过多次的比较。 顺序查找的时间复杂度为0(N)&#xff0c;树的查找时间复杂度为log(N)。 我们最希望的搜索方式&#xff1a;通过元素…
阅读更多...
python coding with ChatGPT 打卡第20天| 二叉搜索树：搜索、验证、最小绝对差、众数

python coding with ChatGPT 打卡第20天| 二叉搜索树：搜索、验证、最小绝对差、众数

相关推荐 python coding with ChatGPT 打卡第12天| 二叉树&#xff1a;理论基础 python coding with ChatGPT 打卡第13天| 二叉树的深度优先遍历 python coding with ChatGPT 打卡第14天| 二叉树的广度优先遍历 python coding with ChatGPT 打卡第15天| 二叉树&#xff1a;翻转…
阅读更多...
第72讲后台管理Container布局实现

第72讲后台管理Container布局实现

新建layout目录 登录成功后&#xff0c;跳转layout布局容器页面 login页面&#xff1a; 导入router import router from "/router";登录成功&#xff0c;跳转后台管理页面 选用布局容器&#xff1a; <template><div class"common-layout">…
阅读更多...
浅谈人工智能之深度学习~

浅谈人工智能之深度学习~

目录 前言&#xff1a;深度学习的进展 一&#xff1a;深度学习的基本原理和算法 二&#xff1a;深度学习的应用实例 三&#xff1a;深度学习的挑战和未来发展方向 四&#xff1a;深度学习与机器学习的关系 五&#xff1a;深度学习与人类的智能交互 悟已往之不谏&#xff0…
阅读更多...
寒假思维训练day20

寒假思维训练day20

更新一道1600的反向贪心 题意&#xff1a; 有n场比赛&#xff0c;且小明的智商是m&#xff0c;每场比赛需要的智商是,当时, 可以直接看题&#xff0c;当时&#xff0c;需要智商m减1才能看这道题&#xff0c;当智商为0不能继续往下看题&#xff0c;问最多能看多少题 题解&#x…
阅读更多...
UR10+gazebo+moveit吸盘抓取搬运demo

UR10+gazebo+moveit吸盘抓取搬运demo

使用ur10gazebo开发了一个简易吸盘抓取箱子码垛的仿真过程&#xff0c;机械臂控制使用的是moveit配置。 本博客对部分关键的代码进行解释。 代码运行环境&#xff1a;支持ubuntu16、 18、 20&#xff0c; ros版本是ros1&#xff08;经过测试&#xff09;。 1、搬运场景 场景的…
阅读更多...
视频讲解：优化柱状图

视频讲解：优化柱状图

你好&#xff0c;我是郭震 AI数据可视化 第三集&#xff1a;美化柱状图&#xff0c;完整视频如下所示&#xff1a; 美化后效果前后对比&#xff0c;前&#xff1a; 后&#xff1a; 附完整案例源码&#xff1a; util.py文件 import platformdef get_os():os_name platform.syst…
阅读更多...
最新文章

Copyright @ 2022~2023