首页 > 编程语言 >408 数据结构栈算法

408 数据结构栈算法

时间：2024-07-28 20:17:24浏览次数：10  
标签：return int ElemType 栈顶 next 算法 数据结构 data 408

第二章 栈

2.1顺序栈

顺序栈的基本操作

#define MAXSIZE 128
typedef int ElemType;
typedef struct {
	ElemType data[MAXSIZE];		//用数组实现对栈中元素的存取
	int top;					//栈顶指针
	int length;					//栈的长度
}SqStack;

//初始化栈
void initStack(SqStack& S);

//判断栈是否x为空，为空返回true，否则返回false
bool isEmpty(SqStack S);

//如果栈S没有满，将x入栈
bool push(SqStack& S, ElemType x);

//如果栈不为空，则将栈顶元素出栈，并返回
ElemType pop(SqStack& S);

//如果栈顶不为空，返回栈顶元素
ElemType peek(SqStack S);

//销毁栈，释放栈所占的存储空间
void destroy(SqStack& S);

顺序栈的代码实现

#define MAXSIZE 128
typedef int ElemType;
typedef struct {
	ElemType data[MAXSIZE];		//用数组实现对栈中元素的存取
	int top;					//栈顶指针
	int length;					//栈的长度
}SqStack;
//初始化栈
void initStack(SqStack& S) {
	//对申请的数组空间依次进行初始化防止不当操作出现脏数据
	for (int i = 0; i < MAXSIZE; i++) {
		S.data[i] = 0;
	}
	
	S.top = 0;	//默认栈顶指向0下标
	S.length = 0;//初始化长度为0
}

//判断栈是否x为空，为空返回true，否则返回false
bool isEmpty(SqStack S) {
	return S.length == 0;
}

//如果栈S没有满，将x入栈
bool push(SqStack& S, ElemType x) {
	//栈已满
	if (S.top >= MAXSIZE) {
		return false;
	}
	S.data[S.top++] = x;	//先赋值后移动top索引
	S.length++;				//栈长+1
}

//如果栈不为空，则将栈顶元素出栈，并由x返回
ElemType pop(SqStack& S) {
	if (isEmpty(S)) {		//规定-999为空，如果栈空返回空
		return -999;
	}
	S.length--;		//表长-1
	return S.data[--S.top];	//删除栈顶时，先将栈顶指针下移
}

//如果栈顶不为空，返回栈顶元素
ElemType peek(SqStack S) {
	if (!isEmpty(S)) {
		return S.data[S.top - 1];	//如果栈不为空，返回栈顶元素。栈顶下标-1为第一个栈顶元素
	}
	return -999;
ee
//销毁栈，释放栈所占的存储空间
void destroy(SqStack& S) {
	//销毁栈手动将数据置为0。栈顶指针指向0，表长设为0
	for (int i = 0; i < S.length; i++) {
		S.data[i] = 0;
	}
	S.top = 0;
	S.length = 0;
}

void printStack(SqStack S) {
	while (S.top > 0) {
		printf("%d ", S.data[--S.top]);
	}
	printf("\n");
}

2.2链栈

typedef int ElemType;
typedef struct LNode{
	ElemType data;
	LNode* next;
}LNode,*LinkedStack;

//初始化链栈
void initLinkedStack(LinkedStack& L) {
	L = (LNode*)malloc(sizeof(LNode));	//建立头结点
	L->next = NULL;		//头结点的next指空
	L->data = 0;		//头结点的data保存栈长度
} 

//判断栈空
bool isEmpty(LinkedStack L) {
	return L->next == NULL;		//或return L->data == 0
}

//进栈（入栈）
void push(LinkedStack& L, ElemType x) {
	LNode* node = (LNode*)malloc(sizeof(LNode));	//创建新结点
	node->data = x;	//为新结点赋值
	node->next = L->next;	//头插法插入新结点
	L->next = node;
	L->data++;	//栈长+1
}

//出栈（弹栈）
ElemType pop(LinkedStack& L) {
	if (L->next == NULL) {
		return -999;	//规定-999为空，若栈空返回空
	}
	LNode* removed = L->next;		//记录待删除元素，以便释放空间
	L->next = removed->next;	//跳过被删除元素结点，头结点直接指向被删除元素的后继
	ElemType x = removed->data;	//x接收被删除元素的值以便返回
	free(removed);		//释放被删除节点空间
	L->data--;			//表长-1
	return x;
}	

//取栈顶
ElemType peek(LinkedStack L) {
	return L->next == NULL ? -999 : L->next->data;	//如果表为空返回-999,否则返回首节点的元素值
}

//销毁栈
void destroy(LinkedStack& L) {
	LNode* p = L->next;
	LNode* tail;
	while (p) {		//依次释放栈除头结点外其他元素结点的空间
		tail = p->next;
		free(p);
		p = tail;
	}
	L->data = 0;		//栈空置为0
}

//求栈长
int length(LinkedStack L) {
	return L->data;
}

//打印栈元素
void printStack(LinkedStack L) {
	if (L == NULL||L->next == NULL) {
		return;
	}
	LNode* p = L->next;
	while (p){
 		printf("%d->", p->data);
		p = p->next;
	}
	printf("\n");
}

2.3共享栈

#define MAXSIZE 16
typedef int ElemType;
typedef struct {
	int data[MAXSIZE];	//共享栈的数据
	int size;			//共享栈的总大小
	int top1;			//第一个栈的栈顶
	int top2;			//第二个栈的栈顶
}SharedStack;

//初始化共享栈
void initStack(SharedStack& S) {
	for (int i = 0; i < MAXSIZE; i++) {
		S.data[i] = 0;
	}
	S.size = 0;		//初始化栈的总大小为0
	S.top1 = 0;		//第一个栈的栈顶指针初始化指向0
	S.top2 = MAXSIZE - 1;//第一个栈的栈顶指针初始化指向MAXSIZE-1
}
//判断第一个栈是否已满
bool isFull1(SharedStack S) {
	return S.top1 > S.top2;	//当第一个栈的栈顶超过了第二个栈的栈顶证明栈已满
}
//判断第二个栈是否已满
bool isFull2(SharedStack S) {
	return S.top2 < S.top1; //当第二个栈的栈顶小于了第一个栈的栈顶证明栈已满
}

//判断第一个栈是否为空
bool isEmpty1(SharedStack S) {
	return S.top1 == 0;
}

//判断第二个栈是否为空
bool isEmpty2(SharedStack S) {
	return S.top2 == MAXSIZE - 1;
}

// 在第一个栈中入栈元素e
void push1(SharedStack& S, ElemType e) {
	//如果栈1不满在执行添加操作，添加时先添加元素后移动栈顶指针，别忘了维持共享栈的总大小
	if (!isFull1(S)) {
		S.data[S.top1++] = e;
		S.size++;
	}
}

// 在第二个栈中入栈元素e
void push2(SharedStack& S, ElemType e) {
	if (!isFull2(S)) {
		S.data[S.top2--] = e;
		S.size++;
	}
}

// 在第一个栈中出栈
ElemType pop1(SharedStack& S) {
	//如果栈不空才执行删除操作，删除时栈顶指针先减在移除
	if (!isEmpty1(S)) {
		S.size--;
		ElemType x = S.data[--S.top1];
		S.data[S.top1] = 0;	//删除完给他置为0
		return x;
	}
	return -999;//代表空栈返回空
}

// 在第二个栈中出栈
ElemType pop2(SharedStack& S) {
	if (!isEmpty2(S)) {
		S.size--;
		ElemType x = S.data[++S.top2];
		S.data[S.top2] = 0;
		return x;
	}
	return -999;
}

// 查看第一个栈栈顶元素
ElemType peek1(SharedStack S) {
	if (!isEmpty1(S)) {
		return S.data[--S.top1];
	}
	return -999;//代表空栈返回空
}

// 查看第二个栈栈顶
ElemType peek2(SharedStack S) {
	if (!isEmpty2(S)) {
		return S.data[++S.top2];
	}
	return -999;
}

//获取第一个栈的长度
int getLength1(SharedStack S) {
	return S.top1;
}

//获取第二个栈的长度
int getLength2(SharedStack S) {
	return MAXSIZE - 1 - S.top2;
}
//打印第一个栈中的元素值
void printStack1(SharedStack S) {
	for (int i = S.top1 - 1; i >= 0; i--) {
		printf("%d ", S.data[i]);
	}
	printf("\n");
}

//打印第二个栈中的元素值
void printStack2(SharedStack S) {
	for (int i = S.top2 + 1; i < MAXSIZE; i++) {
		printf("%d ", S.data[i]);
	}
	printf("\n");
}
//打印共享栈中所有的元素值
void printStack(SharedStack S) {
	for (int i = 0; i < MAXSIZE; i++) {
		printf("%d ", S.data[i]);
	}
	printf("\n");
}

标签：return,int,ElemType,栈顶,next,算法,数据结构,data,408
From： https://www.cnblogs.com/lingchuanfeng/p/18328820

相关文章

  • 408 数据结构队列算法
    第三章队列3.1顺序队列#defineMAXSIZE64typedefintElemType;typedefstruct{ ElemTypedata[MAXSIZE]; intfront; //队头指针 intrear; //队尾指针 intsize; //队列大小}SeQueue;//初始化队列voidinitQueue(SeQueue&Q){ //对数据元素进行初始化，防止出现......
  • sklearn应用朴素贝叶斯算法
    假设一个学校有45%的男生和55%的女生，学校规定不能穿奇装异服，男生的裤子只能穿长筒裤，而女生可以穿裙子或者长筒裤，已知该学校穿长筒裤的女生和穿裙子的女生数量相等，所有男生都必须穿长筒裤，请问如果你从远处看到一个穿裤子的学生，那么这个学生是女生的概率是多少？看完上述问题，......
  • 决策树分类算法（if-else原理）
    决策树算法在“决策”领域有着广泛的应用，比如个人决策、公司管理决策等。其实更准确的来讲，决策树算法算是一类算法，这类算法逻辑模型以“树形结构”呈现，因此它比较容易理解，并不是很复杂，我们可以清楚的掌握分类过程中的每一个细节。if-else原理想要认识“决策树算法”我们不妨......
  • 算法-排序算法
    一、算法和算法分析什么是算法：​ 对特定问题的求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。算法的五个重要特性：有穷性确定性可行性输入输出算法设计的要求：正确性可读性健壮性高效率与低存储算法效率的度量：​ 算法的执行时间需要依......
  • CSP-S提高组数据结构算法模板大合集
    CSP-S算法总结2.2.1基础知识与编程环境无2.2.2C++程序设计2set/nultisetmap/multimapdeque/priority_queueSTL2.2.3数据结构P1886 滑动窗口/【模板】单调队列#include<iostream>usingnamespacestd;intn,k,a[1000005];intq[1000005],h,t;......
  • 数据结构-二叉树、堆、图
    一、线索二叉树规律：在有n个节点的链式二叉树中必定存在n+1个空指针链式二叉树中有很多的空指针，可以让这些空指针指向前一个节点\后一个节点，从而在有序遍历（中序遍历）二叉树时，不需要使用递归而通过循环即可以完成，并且效率要比递归快得多一定是搜索二叉树线索二叉树的结构typ......
  • C++ 数据结构体解析
    文章目录1.定义结构体2. 访问结构成员3. 结构作为函数参数4. 指向结构的指针5. typedef关键字1.定义结构体C/C++数组允许定义可存储相同类型数据项的变量，但是结构是C++中另一种用户自定义的可用的数据类型，它允许存储不同类型的数据项。结构用于表示一条记......
  • C++和R穿刺针吸活检肿瘤算法模型模拟和进化动力学量化差异模型
    ......
  • 从零开始学数据结构系列之第四章《克鲁斯卡尔算法应用场景-公交站问题》
    文章目录往期回顾某城市新增7个站点(A,B,C,D,E,F,G)，现在需要修路把7个站点连通各个站点的距离用边线表示(权)，比如A–B距离12公里问：如何修路保证各个站点都能连通，并且总的修建公路总里程最短?以上图为例，来对克鲁斯卡尔进行演示(假设用数组R保存......
  • ssy暑假集训暴力算法学习笔记
    7.28集训第六天今天t大学的学长peop1e来给我们讲课啦！人好帅呀嘿嘿嘿....内容如下模拟退火：定义模拟退火可以分成两个部分，一个是"模拟"，一个是"退火"，先介绍什么叫退火，贴一张百度百科的图吧：\(\\\)那这"退火"的定义有啥用吗？模拟退火就是用来模拟整个退火的过程(其实没啥相似......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99