当前位置： 首页 > ops >正文

数据结构4线性表——顺序栈

ops 2025/8/20 0:29:31

前言：

本专栏属于数据结构相关内容，附带一些代码加深对一些内容的理解，为方便读者观看，本专栏内的所有文章会同时附带C语言和Python对应的代码，（可自行通过目录跳转到对应的部分）辅助不同主修语言的读者去更好的理解对应的内容，若是代码0基础的读者，可先去博主其他专栏学习一下基础的语法及知识点：

魔法天才的跳转链接：

C语言：C基础_Gu_shiwww的博客-CSDN博客
Python语言：python1_Gu_shiwww的博客-CSDN博客
其他数据结构内容可见：数据结构_Gu_shiwww的博客-CSDN博客

什么是栈

        只能在一端进行插入和删除操作的线性表（又称为堆栈），进行插入和删除操作的一端称为栈顶（杯子顶部），另一端称为栈底（杯子底部）

        栈遵循先进后出（first in last out）的原则

1 顺序栈的特点

逻辑结构：线性结构
物理结构：顺序结构
操作：创建、入栈、出栈、判空、判满

​

2 代码实现顺序栈

首先明确，栈如同我们生活中的泡腾片等，我们只能从一侧取出药片，在瓶口我们也只能看到最顶部的药片，所以我们在代码实现顺序栈的时候，可以设计一个top指针，指向我们的栈顶元素，这样栈的入栈和出栈操作都需要依靠栈顶指针top

C语言编程实现顺序栈

C.* 函数接口

#ifndef __SEQSTACK_H__
#define __SEQSTACK_H__typedef int datatype;  //封装存入的数据的数据类型
typedef struct seqstack
{datatype *data;    //指向数组首位的指针int maxlen;        //保存栈的最大长度(数组元素个数)int top;           //可以叫栈针，但本质是最后一个有效元素下标，和之前学的顺序表的last一样。
}seqstack_t, *seqstack_p;//1.创建一个空栈，len代表创建栈时的最大长度。
seqstack_t *createEmptySeqStack(int len);
//2.判断是否为满,满返回1 未满返回0
int isFullSeqStack(seqstack_t *p);
//3.入栈,data代表入栈的数据
int pushStack(seqstack_t *p, int data);
//4.判断栈是否为空
int isEmptySeqStack(seqstack_t *p);
//5.出栈，返回出栈数据
int popSeqStack(seqstack_t *p);#endif

C.1 创建空栈

//创建一个空栈，len代表创建栈时的最大长度
seqstack_t *createEmptySeqStack(int len)
{//1.申请空间存放栈的结构体seqstack_t *p = (seqstack_t *)malloc(sizeof(seqstack_t));if (NULL == p){perror("createEmptySeqStack p malloc err");return NULL;}//2.初始化p->maxlen = len; //保存栈的最大长度p->top = -1;     //类似与之前顺序表的last,表示栈顶也就是最后一个有效元素的下标，此时没有数据入栈，可以置为-1,那么入栈第一个元素之后就可以加一变成0了，因为数组第一个元素下标为0。    p->data = (int *)malloc(sizeof(datatype) * len);if (NULL == p->data){perror("createEmptySeqStack p->data malloc err");return NULL;}return p;
}

创建空栈，len代表最大的数据个数，函数内部首先开辟一个结构体，结构体内部有maxlen（最大数据个数）、top（栈顶指针）、data（指向数组首地址元素的指针）。因为data是一个指针，可以直接将malloc开辟的空间的首地址赋给data，这样data就指向了开辟了maxlen长度的数组的首地址。下面跟着容错判断，看数组的开辟是否成功

C.2 判满

//判断是否为满,满返回1 未满返回0
int isFullSeqStack(seqstack_t *p)
{return p->top  == p->maxlen -1;
}

top指向栈顶指针，但top实际还表示着最后一个有效元素的下标，当top与maxlen-1的值相同时，此刻开辟的空间已经存满了数据，栈为满，可以将判断语句的结果作为函数的返回值

C.3 入栈

//入栈,data代表入栈的数据
int pushStack(seqstack_t *p, int data)
{//1.容错判断if (isFullSeqStack(p)){printf("pushStack: isFullSeqStack\n");return -1;}//2.往上移动栈针p->top++;//3.将数据入栈p->data[p->top] = data;return 0;
}

首先容错判断，如果栈已满，不能再进行入栈操作，进入if语句给用户一个栈满的提示。若栈未满，栈顶指针top向后移动一个位置，数组对应下标的位置赋值为传进来的参数data

C.4 判空

//判断栈是否为空
int isEmptySeqStack(seqstack_t *p)
{return p->top == -1;
}

因为top代表栈顶数据的下标，当top为-1的时候，栈内数组无此下标，此刻栈内无任何数据，为空。可以将p->top == -1的结果作为此函数的返回值

C.5 出栈

//出栈
int popSeqStack(seqstack_t *p)
{//1.容错判断if (isEmptySeqStack(p)){printf("popSeqStack: isEmptySeqStack\n");return -1;}//2.往下移动栈针p->top--;//3.将栈要出栈数据返回return p->data[p->top + 1];
}

为保证代码的健壮性，出栈与入栈开始时要有相同操作，首先判断栈是否为空，空栈无数据可出。然后将top指针向下移动，此时top后一个位置的元素依旧存在，但是因为top指针的缘故，该数据不会被访问到，若想要拿到被删除数据的值，可以通过top+1得到。于是可以将p->data[p->top+1]作为此函数的返回值

C.6 完整代码（可运行）

#include<stdio.h>
#include <stdlib.h>typedef int datatype;  //封装存入的数据的数据类型
typedef struct seqstack
{datatype *data;   //指向数组首位的指针int maxlen;  //保存栈的最大长度(数组元素个数)int top;        //可以叫栈针，但本质是最后一个有效元素下标，和之前学的顺序表的last一样。
}seqstack_t, *seqstack_p;//创建一个空栈，len代表创建栈时的最大长度
seqstack_t *createEmptySeqStack(int len)
{//1.申请空间存放栈的结构体seqstack_t *p = (seqstack_t *)malloc(sizeof(seqstack_t));if (NULL == p){perror("createEmptySeqStack p malloc err");return NULL;}//2.初始化p->maxlen = len; //保存栈的最大长度p->top = -1;     //类似与之前顺序表的last,表示栈顶也就是最后一个有效元素的下标，此时没有数据入栈，可以置为-1,那么入栈第一个元素之后就可以加一变成0了，因为数组第一个元素下标为0。    p->data = (int *)malloc(sizeof(datatype) * len);if (NULL == p->data){perror("createEmptySeqStack p->data malloc err");return NULL;}return p;
}//判断是否为满,满返回1 未满返回0
int isFullSeqStack(seqstack_t *p)
{return p->top  == p->maxlen -1;
}//入栈,data代表入栈的数据
int pushStack(seqstack_t *p, int data)
{//1.容错判断if (isFullSeqStack(p)){printf("pushStack: isFullSeqStack\n");return -1;}//2.往上移动栈针p->top++;//3.将数据入栈p->data[p->top] = data;return 0;
}//判断栈是否为空
int isEmptySeqStack(seqstack_t *p)
{return p->top == -1;
}//出栈
int popSeqStack(seqstack_t *p)
{//1.容错判断if (isEmptySeqStack(p)){printf("popSeqStack: isEmptySeqStack\n");return -1;}//2.往下移动栈针p->top--;//3.将栈要出栈数据返回return p->data[p->top + 1];
}int main(int argc, char const *argv[])
{seqstack_t *p = createEmptySeqStack(5);for (int i = 1; i <= 6; i++)pushStack(p, i); //最后一次调用报：pushStack: isFullSeqStack，因为栈已经满了//只要栈不为空就出栈printf("出栈：");while(!isEmptySeqStack(p))//出栈的顺序是 5 4 3 2 1 ，因为栈的思想先进后出{printf("%d ",popSeqStack(p));}printf("\n");return 0;
}

Python语言编程实现

P.* 函数接口

class Stack:max_len = 32  # 保存栈的最大长度# 始终代表当前栈内最后一个有效元素的下标，称为栈顶指针top = -1data = [0] * max_len  # 顺序栈的存储空间# 1、判断是否为满, 满返回True,未满返回Falsedef is_full(self):pass# 2. 入栈def push(self, data: int):  # data代表入栈的数据pass# 3.判断栈是否为空def is_empty(self):pass# 4.出栈def pop(self):pass# 5. 清空栈def clear(self):pass# 6.获取栈顶数据(注意不是出栈操作，如果出栈，相当于删除了栈顶数据，只是将栈顶的数据获取到，不需要移动栈针)def get_top(self):pass# 7. 求栈的有限长度def get_length(self):pass

P.1 判满

# 1、判断是否为满, 满返回True,未满返回False
def is_full(self):return self.top + 1 == self.max_len

top作为栈顶数据的指针，同时也是栈顶数据的下标，下标从0开始，若栈顶下标+1与栈的最大长度相同，则代表栈内位置全部填满数据，可将该判断语句的结果作为函数返回值

P.2 入栈

# 2. 入栈
def push(self, data: int):  # data代表入栈的数据if self.is_full():print("push error")returnself.top += 1self.data[self.top] = data

首先容错判断，若栈已满则无数据可以进入，未满则移动top指针到下一个位置，通过top下标访问data数据域，将传入的形参data写道对应下标位置

P.3 判空

# 3.判断栈是否为空
def is_empty(self):return self.top == -1

依旧使用top，top对应栈顶数据的下标，当它的值为-1时，证明栈内无任何元素，可以将该判断语句作为判空函数的返回值

P.4 出栈

# 4.出栈
def pop(self):if self.is_empty():print("pop error")returnself.top -= 1return self.data[self.top + 1]

出栈与入栈时相同首先进行容错判断。若栈不空直接将top值前移一位。若想得到出栈数据的值，可通过top+1得到该数据（因为top的移动只是有效下标的移动，并没有删除该数据，依旧可以通过下标进行访问，属于逻辑删除）

P.5 清空栈

# 5. 清空栈
def clear(self):self.top = -1

top作为最后有效元素的下标，只需将其置为-1，就可以在逻辑上清空整个栈

P.6 获取栈顶数据

# 6.获取栈顶数据(注意不是出栈操作，如果出栈，相当于删除了栈顶数据，只是将栈顶的数据获取到，不需要移动栈针)
def get_top(self):if self.is_empty():print("get_top error")returnreturn self.data[self.top]

容错判断判空，不为空则直接将top下标的值作为函数的返回值

P.7 求栈有效长度

# 7. 求栈的有限长度
def get_length(self):return self.top + 1

最简单的一集，top作为最后一个有效数据的下标，且下标从0开始，那top+1就是栈的有效长度。直接将top+1作为函数的返回值

P.8 完整代码（可运行）

class Stack:max_len = 32  # 保存栈的最大长度# 始终代表当前栈内最后一个有效元素的下标，称为栈顶指针top = -1data = [0] * max_len  # 顺序栈的存储空间# 1、判断是否为满, 满返回True,未满返回Falsedef is_full(self):return self.top + 1 == self.max_len# 2. 入栈def push(self, data: int):  # data代表入栈的数据if self.is_full():print("push error")returnself.top += 1self.data[self.top] = data# 3.判断栈是否为空def is_empty(self):return self.top == -1# 4.出栈def pop(self):if self.is_empty():print("pop error")returnself.top -= 1return self.data[self.top + 1]# 5. 清空栈def clear(self):self.top = -1# 6.获取栈顶数据(注意不是出栈操作，如果出栈，相当于删除了栈顶数据，只是将栈顶的数据获取到，不需要移动栈针)def get_top(self):if self.is_empty():print("get_top error")returnreturn self.data[self.top]# 7. 求栈的有限长度def get_length(self):return self.top + 1if __name__ == '__main__':seq_stack = Stack()for i in range(6):seq_stack.push(i)print("top_data",seq_stack.get_top())print("stack_len",seq_stack.get_length())for _ in range(6):print(seq_stack.pop())

http://www.xdnf.cn/news/17960.html

相关文章：

  • Microsoft WebView2
  • Java 大视界 -- 基于 Java 的大数据分布式计算在气象灾害预警与应急响应中的应用
  • 【lucene】SegmentInfos
  • 系统思考—啤酒游戏经营决策沙盘认证
  • 论文推荐|迁移学习+多模态特征融合
  • 二叉树的三种遍历方法
  • ZKmall开源商城的数据校验之道：用规范守护业务基石
  • 【论文笔记】STORYWRITER: A Multi-Agent Framework for Long Story Generation
  • lcx、netcat、powercat--安装、使用
  • [go] 桥接模式
  • 分布式存储与存储阵列：从传统到现代的存储革命
  • Tello无人机与LLM模型控制 ROS
  • 安全审计-iptales防火墙设置
  • 立体匹配中的稠密匹配和稀疏匹配
  • 教材采购管理系统（java）
  • 力扣（接雨水）——基于最高柱分割的双指针
  • Python - 100天从新手到大师：第十一天常用数据结构之字符串
  • Flink Stream API 源码走读 - 总结
  • 双指针和codetop复习
  • Day56 Java面向对象10 方法重写
  • Vue组件基础解析
  • [系统架构设计师]系统质量属性与架构评估（八）
  • Python语言---OrangePi全志H616
  • MySQL锁机制：悲观锁VS乐观锁详解
  • vector 手动实现 及遇到的各种细节问题
  • Azure AI Search 探索总结
  • 通配符 重定向 管道符
  • 数字分类：机器学习经典案例解析
  • vscode中使用CMake Tools生成compile_commands.json文件后，如何告诉clangd这个文件在哪里呢？
  • 【Linux系统】进程间通信：System V IPC——共享内存