【数据结构】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);


}

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

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

相关文章

【医学知识图谱 自动补全 关系抽取】生成模型 + 医学知识图谱 = 发现三元组隐藏的关系实体对

【医学知识图谱 自动补全 关系抽取】生成模型 + 医学知识图谱 = 发现三元组隐藏的关系实体对

生成模型 医学知识图谱 发现三元组新关系实体对 提出背景问题&#xff1a;如何自动发现并生成医疗领域中未被标注的实体关系三元组&#xff1f;CRVAE模型 提出背景 论文&#xff1a;https://dl.acm.org/doi/pdf/10.1145/3219819.3220010 以条件关系变分自编码器&#xff08;…
阅读更多...
【51单片机】定时器（江科大）

【51单片机】定时器（江科大）

7.1定时器 1.定时器介绍: 51单片机的定时器属于单片机的内部资源,其电路的连接和运转均在单片机内部完成 2. 定时器作用: (1)用于计时系统,可实现软件计时,或者使程序每隔一固定时间完成一项操作 (2)替代长时间的Delay,提高CPU的运行效率和处理速度 定时器在单片机内部就像一个…
阅读更多...
模型 “焦糖布丁”理论

模型 “焦糖布丁”理论

系列文章 主要是 分享 思维模型&#xff0c;涉及各个领域&#xff0c;重在提升认知。关注需求本质。 1 “焦糖布丁”理论的应用 1.1 “焦糖布丁”理论-海底捞的创新 海底捞以其优质的服务而闻名&#xff0c;它的成功之处在于深刻理解了消费者的需求和任务&#xff0c;并提供了…
阅读更多...
【运维测试】测试理论+工具总结笔记第1篇：测试理论的主要内容（已分享，附代码）

【运维测试】测试理论+工具总结笔记第1篇：测试理论的主要内容（已分享，附代码）

本系列文章md笔记&#xff08;已分享&#xff09;主要讨论测试理论测试工具相关知识。Python测试理论的主要内容&#xff0c;掌握软件测试的基本流程&#xff0c;知道软件测试的V和W模型的优缺点&#xff0c;掌握测试用例设计的要素&#xff0c;掌握等价类划分法、边界值法、因…
阅读更多...
React18原理: 时间分片技术选择

React18原理: 时间分片技术选择

渲染1w个节点的不同方式 1 &#xff09;案例1&#xff1a;一次渲染1w个节点 <div idroot><div><script type"text/javascript">function randomHexColor() {return "#" ("0000" (Math.random() * 0x1000000 << 0).toS…
阅读更多...
【51单片机】蜂鸣器（江科大）

【51单片机】蜂鸣器（江科大）

11.1蜂鸣器 1.蜂鸣器介绍 蜂鸣器是一种将电信号转换为声音信号的器件,常用来产生设备的按键音、报警音等提示信号 蜂鸣器按驱动方式可分为有源蜂鸣器和无源蜂鸣器 有源蜂鸣器:内部自带振荡源,将正负极接上直流电压即可持续发声,频率固定 无源蜂鸣器:内部不带振荡源,需…
阅读更多...
【MATLAB】小波神经网络回归预测算法

【MATLAB】小波神经网络回归预测算法

有意向获取代码&#xff0c;请转文末观看代码获取方式~也可转原文链接获取~ 1 基本定义 小波神经网络回归预测算法是一种利用小波变换和人工神经网络相结合的方法&#xff0c;用于解决回归预测问题。下面将详细介绍该算法的原理与方法&#xff1a; 小波变换&#xff1a; 小波变…
阅读更多...
Codeforces Round 924 (Div. 2)

Codeforces Round 924 (Div. 2)

Codeforces Round 924 (Div. 2) Codeforces Round 924 (Div. 2) A. Rectangle Cutting 题意&#xff1a;给出a*b的矩形&#xff0c;沿着其中一个边恰好一分为二后可以组成一个新的矩形 思路&#xff1a;判断其中一个边是否可以被2整除以及二分后是否等于另一个边即可 AC cod…
阅读更多...
C++进阶（十六）特殊类设计

C++进阶（十六）特殊类设计

&#x1f4d8;北尘_&#xff1a;个人主页 &#x1f30e;个人专栏:《Linux操作系统》《经典算法试题 》《C》 《数据结构与算法》 ☀️走在路上&#xff0c;不忘来时的初心 文章目录 一、请设计一个类&#xff0c;不能被拷贝二、请设计一个类&#xff0c;只能在堆上创建对象三、…
阅读更多...
腾讯云幻兽帕鲁服务器配置怎么选择合适？

腾讯云幻兽帕鲁服务器配置怎么选择合适？

腾讯云幻兽帕鲁服务器配置怎么选&#xff1f;根据玩家数量选择CPU内存配置&#xff0c;4到8人选择4核16G、10到20人玩家选择8核32G、2到4人选择4核8G、32人选择16核64G配置&#xff0c;腾讯云百科txybk.com来详细说下腾讯云幻兽帕鲁专用服务器CPU内存带宽配置选择方法&#xff…
阅读更多...
8868体育助力西甲最新积分榜 皇马4球大胜稳坐榜一

8868体育助力西甲最新积分榜 皇马4球大胜稳坐榜一

西甲联赛第24轮的四场比赛于2月10日全面收官。其中&#xff0c;皇马在主场迎战吉罗纳队&#xff0c;以4-0的大比分击败对手&#xff0c;将领先优势扩大到5分&#xff0c;稳坐西甲榜首&#xff0c;掌握了争冠的主动权。 威尼修斯的世界波为皇马打开胜利之门&#xff0c;第6分钟就…
阅读更多...
侧信道攻击是什么

侧信道攻击是什么

侧信道攻击是什么? 侧信道攻击是一种利用系统的物理实现或实现的特定属性来获取信息的攻击方式。这些攻击利用了系统在执行特定操作时产生的信息泄漏&#xff0c;而不是直接攻击系统的计算或加密算法。侧信道攻击通常利用系统的功耗、电磁辐射、时间延迟等物理特性进行攻击&a…
阅读更多...
Python实现MACD指标计算：股票技术分析的利器系列（1）

Python实现MACD指标计算：股票技术分析的利器系列（1）

Python实现MACD指标计算&#xff1a;股票技术分析的利器系列&#xff08;1&#xff09; 介绍核心代码&#xff1a;EMA核心代码&#xff1a;MACD200 次交易日的收盘价格完整代码最终运行代码的效果展示DIFDEAMACD 介绍 先看看官方介绍&#xff1a; MACD (平滑异同平均线&#x…
阅读更多...
Linux——进程间通信：管道

Linux——进程间通信：管道

我们在开发过程中&#xff0c;可能会碰到两个或多个进程需要协同进行&#xff0c;这两个进 程之间有着一定的关系&#xff0c;这个进程可能会需要另一个进程的某些消息来达 到自己的目的&#xff0c;或者是一个进程控制着另一个进程&#xff0c;又或者是需要某种资 源的共享。但…
阅读更多...
BFS与DFS初级练习(排列数字，n-皇后，走迷宫)

BFS与DFS初级练习(排列数字，n-皇后，走迷宫)

BFS与DFS初步了解 DFS&#xff08;深度优先搜索&#xff09;和BFS&#xff08;广度优先搜索&#xff09;是两种常用的图遍历算法。 DFS是一种递归的搜索算法&#xff0c;它从起始节点开始&#xff0c;沿着路径依次访问与当前节点相邻的未访问节点&#xff0c;直到无法继续访问…
阅读更多...
【易学】周易入门 ③ ( 玄学五术 - 山医命相卜 | 天命无常 唯有德者居之 | 预测学模型 | 五行学说 | 五行相生 | 五行相克 )

【易学】周易入门 ③ ( 玄学五术 - 山医命相卜 | 天命无常 唯有德者居之 | 预测学模型 | 五行学说 | 五行相生 | 五行相克 )

文章目录 一、玄学五术 - 山医命相卜二、天命无常 唯有德者居之三、预测学模型四、五行学说1、五行相生2、五行相克 一、玄学五术 - 山医命相卜 玄学五术 : 山 : 修行 " 肉体 " 和 " 精神 " , 以寻求 身心超脱 ; 肉体修行 - 拳法 : 太极拳 , 五禽戏 , 易筋…
阅读更多...
那些 C语言指针 你不知道的小秘密 (完结篇)

那些 C语言指针 你不知道的小秘密 (完结篇)

本篇会加入个人的所谓‘鱼式疯言’ ❤️❤️❤️鱼式疯言:❤️❤️❤️此疯言非彼疯言 而是理解过并总结出来通俗易懂的大白话, 我会尽可能的在每个概念后插入鱼式疯言,帮助大家理解的. &#x1f92d;&#x1f92d;&#x1f92d;可能说的不是那么严谨.但小编初心是能让更多人能…
阅读更多...
BUUCTF LKWA

BUUCTF LKWA

1.访问页面。 2.选择 Variables variable 关卡 3.获得flag http://357dab81-78b8-4d74-976a-4a69dd894542.node5.buuoj.cn:81/variables/variable.php?funcpassthru&inputcat%2Fflagflag{0020ced6-8166-4fa5-87a7-7d93ee687c3e}
阅读更多...
键盘重映射禁用 CtrlAltDel 键的利弊

键盘重映射禁用 CtrlAltDel 键的利弊

目录 前言 一、Scancode Map 的规范 二、禁用 CtrlAltDel 的方法及其缺陷 三、编程实现和测试 3.1 C 实现的简易修改工具 3.2 C# 实现的窗口工具 四、总结 本文属于原创文章&#xff0c;转载请注明出处&#xff1a; https://blog.csdn.net/qq_59075481/article/details…
阅读更多...
PySQLRecon：一款功能强大的MSSQL安全测试工具

PySQLRecon：一款功能强大的MSSQL安全测试工具

关于PySQLRecon PySQLRecon是一款功能强大的MSSQL安全测试工具&#xff0c;该工具基于SQLRecon实现其功能&#xff0c;可以帮助广大红队研究人员针对MSSQL执行攻击性安全测试。 环境配置 由于该工具基于Python 3开发&#xff0c;因此我们首先需要在本地设备上安装并配置好Pyt…
阅读更多...
最新文章

Copyright @ 2022~2023