# 数据结构 (II)
最编程
2024-10-19 07:10:29
...
栈和队列
一.栈的顺序存储结构
特点:先进后出
栈是一种只能在一端进行插入或删除操作的线性表。
表中允许插入删除操作的一端为栈顶(top),表的另一端为栈底(bottom),
1 结构体的定义
#include <stdio.h>
typedef int ElemType;
#define MAX_SIZE 100
typedef struct {
int data[MAX_SIZE]; // 用于存储栈中的元素
int top; // 栈顶指针,指向栈顶元素的索引
} SqStack;
2 初始化栈
栈顶指针赋值为-1
void InitStack(SqStack *&s) {
s = (SqStack *) malloc(sizeof(SqStack));//申请一个顺序栈空间
s->top = -1;//栈顶指针赋值为-1
}
3 销毁栈
释放节点空间
void DestroyStack(SqStack *&s) {
free(s);
}
4 判断栈是否为空
指针为-1
bool StackEmpty(SqStack *&s) {
return (s->top == -1);
}
5 进栈
先判断栈是否为满
注意先将指针++,再对栈顶元素进行赋值
bool PushStack(SqStack *&s, ElemType e) {
if (s->top == MAX_SIZE - 1) {//栈满的情况
return false;
}
s->top++;
s->data[s->top] = e;//先加再赋值(s-data[++s->top])
return true;
}
6 出栈
先对栈元素赋值,再将指针--
bool Pop(SqStack *&s, ElemType &e) {
if (s->top == -1) {//栈空的情况
return false;
}
e=s->data[s->top];
s->top--;
return true;
}
7 获取栈顶元素
bool GetTop(SqStack *s,ElemType &e){
if (s->top==-1)
return false;
e=s->data[s->top];
return true;
}
补充:共享栈
- 顺序栈采用一个数组存放栈中的元素。如果需要用到两个类型相同的栈,这时若为它们各自开辟一个数组空间,极有可能出现这样的情况:第一个栈已经满了,再进栈就溢出了,而另一个栈还有许多的空间。
- 共享栈是为了更有效地利用存储空间,两个栈的空间相互调节,只有在整个存储空间被占满时才会发生上溢。其存储数据的时间复杂度均为O(1),所以对存取效率没有什么影响。
- 栈空条件:栈0空为top==-1;栈1空为top1==MaxSize.
- 栈满条件:top==top1-1
- 元素进栈操作:进栈0操作为top0++;data[top0]=x;进栈1操作为top1--;data[top1]=x
- 元素出栈操作:出栈0操作为x=data[top0];top0--;出栈1操作为x=data[top1];top1++
- 在上述操作中,data数组表示共享栈的存储空间,top0和top1分别为两个栈的栈顶指针,这样该共享栈通过data,top0和top1来标识,也可以将他们设计为一个结构体类型。
二.栈的链式存储结构
栈中的数据元素的逻辑关系呈线性关系,所以栈可以像线性表一样采用链式存储结构
下一篇: 面试问题:Redis (viii)
推荐阅读
-
C# II 中的多态性应用说明示例(使用隐藏方法)
-
# 数据结构 (II)
-
[图形] 蒙特卡罗积分法及其方差计算导论-II。
-
超文本传输协议 HTTP - II.HTTP 报文
-
LeetCode] 动态编程 - 95.动态编程 - 95.不同的二叉搜索树 II(附完整 Python/C++ 代码) - 基本思想
-
数据结构 图的邻接表表示法 有向 + 无向图的深度优先搜索遍历(C 代码 + 终端输入内容)
-
数据结构 - B 树和 B+ 树 - II.
-
Java 游戏超级马里奥 - II 代码编写
-
Java 项目实践 II 基于 Java + Spring Boot + MySQL 的匹配网站设计与实施(源代码 + 数据库 + 文档)
-
.rds 文件数据结构和内容 查看方法