数据结构和算法学习记录——特殊线性表之栈(上)-栈的概念、栈的结构、链式栈数组栈、栈的结构体定义、栈的基本接口函数、栈顶初始化函数

简介: 数据结构和算法学习记录——特殊线性表之栈(上)-栈的概念、栈的结构、链式栈数组栈、栈的结构体定义、栈的基本接口函数、栈顶初始化函数

栈的概念

栈:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。

进行数据插入和删除操作的一端称为栈顶,另一端称为栈底。栈中的数据元素遵守后进先出LIFO(Last In First Out)的原则。

压栈:栈的插入操作叫做进栈/压栈/入栈。数据在栈顶进入。出栈:栈的删除操作叫做出栈。数据也在栈顶出去。

栈的结构

链式栈

如果以尾做栈顶,进行尾插尾删,效率较低(要进行遍历),除非设计成双向链表。

如果以头做栈顶,头插头删,效率则较高,可以设计成单链表。

数组栈

压栈出栈都比较方便,且CPU高速缓存命中率更高。

故而两种结构都可以使用,非要选一种的话,更建议使用数组栈,结构更好。

小习题

1.一个栈的初始状态为空。现有元素1、2、3、4、5、A、B、C、D、E依次入栈,然后再依次出栈。则元素出栈的顺序是()。

A.12345ABCDE

B.EDCBA54321

C.ABCDE12345

D.54321EDCBA

2.若进栈序列为1、2、3、4。进栈过程中可以出栈,则下列不可能的一个出栈序列是()

A.1、4、3、2

B.2、3、4、1

C.3、1、4、2

D.3、4、2、1

答案:1.B 2.C

第二题解析

在进栈的过程中可以随时出栈,所以出栈序列可以有多种可能性。用相同的思路判断即可得到答案C。

栈的结构体定义

#include <stdlib.h>
#include <stdio.h>
#include <assert.h>
#include <stdbool.h>
//栈的结构体定义
typedef int STDataType;
typedef struct Stack
{
    STDataType* a;
    int top;
    int capacity;
}ST;

基本接口函数

//基本接口函数
void StackInit(ST* ps);
void StackDestroy(ST* ps);
void StackPush(ST* ps, STDataType x);
void StackPop(ST* ps);
STDataType StackTop(ST* ps);//取出栈顶元素
int StackSize(ST* ps);//计算栈中有多少个元素
bool StackEmpty(ST* ps);//判断栈是否为空

栈的初始化函数

初始化函数时,栈顶top的初始化可以有两种方式。在数组栈中,top表示下标。

那么top在数组栈中初始化的两种方式分别是;top = -1;top = 0;

第一种的初始化意味着top指向的是栈顶数据;

第二种的初始化意味着top指向的是栈顶数据的下一位。


end

目录
相关文章
|
3天前
|
存储
【数据结构】树和二叉树的概念及结构
数据结构——树和二叉树的概念及结构
17 3
【数据结构】树和二叉树的概念及结构
|
9天前
|
存储 算法 Python
“解锁Python高级数据结构新姿势:图的表示与遍历,让你的算法思维跃升新高度
【7月更文挑战第13天】Python中的图数据结构用于表示复杂关系,通过节点和边连接。常见的表示方法是邻接矩阵(适合稠密图)和邻接表(适合稀疏图)。图遍历包括DFS(深度优先搜索)和BFS(广度优先搜索):DFS深入探索分支,BFS逐层访问邻居。掌握这些技巧对优化算法和解决实际问题至关重要。**
12 1
|
14天前
|
算法 安全 调度
逆天改命!Python高级数据结构堆(Heap)与优先队列,让你的算法效率飙升至宇宙级!
【7月更文挑战第8天】Python的heapq模块和queue.PriorityQueue实现了堆和优先队列,提供高效算法解决方案。堆用于Dijkstra算法求解最短路径,例如在图论问题中;PriorityQueue则在多线程下载管理中确保高优先级任务优先执行。这两个数据结构提升效率,简化代码,是编程中的强大工具。
13 0
|
14天前
|
算法 搜索推荐 Java
在Java中实现高效的算法与数据结构
在Java中实现高效的算法与数据结构
|
27天前
|
算法 C语言
【数据结构与算法 经典例题】使用栈实现队列(图文详解)
【数据结构与算法 经典例题】使用栈实现队列(图文详解)
|
3天前
|
存储 前端开发 DataX
【数据结构】栈和队列
数据结构中的栈和队列
8 1
【数据结构】栈和队列
|
3天前
【数据结构OJ题】用栈实现队列
力扣题目——用栈实现队列
9 0
【数据结构OJ题】用栈实现队列
|
3天前
【数据结构OJ题】用队列实现栈
力扣题目——用队列实现栈
12 0
【数据结构OJ题】用队列实现栈
|
21天前
|
存储 缓存 算法
堆和栈的区别及应用场景
堆和栈的区别及应用场景
|
27天前
|
算法 C语言
【数据结构与算法 经典例题】使用队列实现栈(图文详解)
【数据结构与算法 经典例题】使用队列实现栈(图文详解)