数据结构===栈

文章目录

  • 栈的定义
  • 实现一个栈
    • 用数组实现栈
    • 用链表实现栈
    • 支持动态扩容的栈
  • 栈的应用
  • 小结

栈的定义

栈是一种先进后出的数据结构。它的操作受限。

栈，是一种先进后出，或者后进先出的数据结构。跟数组和链表相比，有一定的限制性。毕竟，它也有自己的适用场景，比如：函数调用，表达式求值等等。栈有2个操作，入栈，出栈。时间复杂度都是O(1)。

实现一个栈

实现一个栈：怎么实现呢，有2种方式，用数组实现或者用链表实现。用数组实现的叫做顺序栈，用链表实现的叫做链式栈。

用数组实现栈

先用数组实现，不考虑扩容的情况，代码如下：

class Stack:
    def __init__(self):
        self.stack = []

    # 入栈操作
    def push(self, item):
        self.stack.append(item)

    # 出栈操作
    def pop(self):
        if not self.is_empty():
            return self.stack.pop()
        else:
            return None

    # 查看栈顶元素
    def peek(self):
        if not self.is_empty():
            return self.stack[-1]
        else:
            return None

    # 判断栈是否为空
    def is_empty(self):
        return len(self.stack) == 0

    # 获取栈的大小
    def size(self):
        return len(self.stack)

这是python的实现方式。可以再看下java的实现方式，如下图：

public class Stack {
    private int[] elements;
    private int top;
    private int capacity;

    // 初始化栈，设置初始容量
    public Stack(int capacity) {
        this.capacity = capacity;
        elements = new int[capacity];
        top = -1; // 初始时栈顶为-1，表示栈为空
    }

    // 入栈操作
    public void push(int item) {
        if (!isFull()) {
            top++;
            elements[top] = item;
        } else {
            System.out.println("栈已满，无法添加元素");
        }
    }

    // 出栈操作
    public int pop() {
        if (!isEmpty()) {
            return elements[top--];
        } else {
            System.out.println("栈为空，无法删除元素");
            return -1; // 或者可以抛出一个异常
        }
    }

    // 查看栈顶元素
    public int peek() {
        if (!isEmpty()) {
            return elements[top];
        } else {
            System.out.println("栈为空，没有元素可查看");
            return -1; // 或者可以抛出一个异常
        }
    }

    // 检查栈是否为空
    public boolean isEmpty() {
        return top == -1;
    }

    // 检查栈是否已满
    private boolean isFull() {
        return top == capacity - 1;
    }

    // 获取栈的大小
    public int size() {
        return top + 1;
    }

    // 展示栈的内容（可选）
    public void displayStack() {
        if (isEmpty()) {
            System.out.println("栈为空");
        } else {
            for (int i = top; i >= 0; i--) {
                System.out.print(elements[i] + " ");
            }
            System.out.println();
        }
    }

    // 主函数，用于测试栈的实现
    public static void main(String[] args) {
        Stack stack = new Stack(5); // 创建一个容量为5的栈

        stack.push(1);
        stack.push(2);
        stack.push(3);

        stack.displayStack(); // 显示栈的内容

        System.out.println("栈顶元素: " + stack.peek());

        stack.pop();
        stack.pop();

        stack.displayStack(); // 再次显示栈的内容

        System.out.println("栈的大小: " + stack.size());
        System.out.println("栈是否为空: " + stack.isEmpty());
    }
}

用链表实现栈

用数组实现完了，再用链表实现，如下图：

class Node:
    def __init__(self, data=None):
        self.data = data
        self.next = None

class Stack:
    def __init__(self):
        self.top = None

    # 入栈操作
    def push(self, data):
        if self.top is None:
            self.top = Node(data)
        else:
            new_node = Node(data)
            new_node.next = self.top
            self.top = new_node

    # 出栈操作
    def pop(self):
        if self.top is None:
            return None
        else:
            popped = self.top.data
            self.top = self.top.next
            return popped

    # 查看栈顶元素
    def peek(self):
        return self.top.data if self.top else None

    # 判断栈是否为空
    def is_empty(self):
        return self.top is None

# 测试代码
s = Stack()
s.push(1)
s.push(2)
s.push(3)
print(s.pop())  # 输出：3
print(s.peek())  # 输出：2
print(s.is_empty())  # 输出：False

java的实现方式，如下图：

public class Node<T> {
    private T data;
    private Node<T> next;

    public Node(T data) {
        this.data = data;
        this.next = null;
    }

    public T getData() {
        return data;
    }

    public void setData(T data) {
        this.data = data;
    }

    public Node<T> getNext() {
        return next;
    }

    public void setNext(Node<T> next) {
        this.next = next;
    }
}

public class LinkedListStack<T> {
    private Node<T> top;

    public LinkedListStack() {
        this.top = null;
    }

    // 入栈操作
    public void push(T data) {
        Node<T> newNode = new Node<>(data);
        newNode.setNext(top);
        top = newNode;
    }

    // 出栈操作
    public T pop() {
        if (isEmpty()) {
            throw new IllegalStateException("Stack is empty");
        }
        T data = top.getData();
        top = top.getNext();
        return data;
    }

    // 查看栈顶元素
    public T peek() {
        if (isEmpty()) {
            throw new IllegalStateException("Stack is empty");
        }
        return top.getData();
    }

    // 判断栈是否为空
    public boolean isEmpty() {
        return top == null;
    }

    // 获取栈的大小
    public int size() {
        int size = 0;
        Node<T> current = top;
        while (current != null) {
            size++;
            current = current.getNext();
        }
        return size;
    }

    // 测试代码
    public static void main(String[] args) {
        LinkedListStack<Integer> stack = new LinkedListStack<>();
        stack.push(200);
        stack.push(300);
        stack.push(600);
        System.out.println(stack.pop());  
        System.out.println(stack.peek());  
        System.out.println(stack.isEmpty()); 
        System.out.println(stack.size());  
    }
}

好了，实现方式就是这样的。再来看看动态扩容的栈是怎么实现的。

支持动态扩容的栈

这个跟普通的栈有一个不同的地方，在入栈的时候栈满了会进行扩容，然后复制之前的数据，再进行入栈操作。用java实现，如下图：

public class DynamicArrayStack<T> {
    private static final int DEFAULT_CAPACITY = 10;
    private static final int RESIZE_FACTOR = 2;
    private Object[] elements;
    private int top;

    public DynamicArrayStack() {
        elements = new Object[DEFAULT_CAPACITY];
        top = -1;
    }

    // 入栈操作
    public void push(T item) {
        ensureCapacity();
        elements[++top] = item;
    }

    // 出栈操作
    public T pop() {
        if (isEmpty()) {
            throw new EmptyStackException();
        }
        return (T) elements[top--];
    }

    // 查看栈顶元素
    public T peek() {
        if (isEmpty()) {
            throw new EmptyStackException();
        }
        return (T) elements[top];
    }

    // 判断栈是否为空
    public boolean isEmpty() {
        return top == -1;
    }

    // 获取栈的大小
    public int size() {
        return top + 1;
    }

    // 确保数组有足够的容量
    private void ensureCapacity() {
        if (top == elements.length - 1) {
            resize();
        }
    }

    // 调整数组大小
    private void resize() {
        int newSize = elements.length * RESIZE_FACTOR;
        elements = Arrays.copyOf(elements, newSize);
    }

    // 测试代码
    public static void main(String[] args) {
        DynamicArrayStack<Integer> stack = new DynamicArrayStack<>();

        stack.push(1);
        stack.push(2);
        stack.push(3);

        System.out.println(stack.pop());  // 输出：3
        System.out.println(stack.peek());  // 输出：2
        System.out.println(stack.size());  // 输出：2
        System.out.println(stack.isEmpty());  // 输出：false
    }
}

栈的应用

栈应用非常多，比如，在浏览器里有个向前，向后的箭头，就可以用2个栈来存储；函数的调用，也是可以用栈的。例子就不多举了。

小结

这篇文章讲述了栈的数据结构。

主要是讲解了栈的数据结构，以及实现，目的是了解底层的数据结构及应用，还有动态扩容的栈，栈的时间复杂度，空间复杂度都是O(1)。基本上就这么多。至于实现，用什么语言不重要，原理懂了，写一个，应该都不是什么难事。

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

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

相关文章

汽车信息安全入门总结(2)

汽车信息安全入门总结(2)

目录 1.引入 2.汽车信息安全技术 3.密码学基础知识 4.小结 1.引入 上篇汽车信息安全入门总结(1)-CSDN博客主要讲述了汽车信息安全应该关注的点&#xff0c;以及相关法规和标准&#xff0c;限于篇幅&#xff0c;继续聊信息安全相关技术以及需要掌握的密码学基础知识。 2.汽…
阅读更多...
Costas-Barker序列模糊函数仿真

Costas-Barker序列模糊函数仿真

文章目录 前言一、Costas 序列二、Barker 码三、Costas-Barker 序列模糊函数仿真1、MATLAB 核心代码2、仿真结果①、Costas-Barker 模糊函数图②、Costas-Barker 距离模糊函数图③、Costas-Barker 速度模糊函数图 四、资源自取 前言 Costas 码是一种用于载波同步的频率调制序列…
阅读更多...
基于SpringBoot+Vue高校竞赛管理系统的设计与实现

基于SpringBoot+Vue高校竞赛管理系统的设计与实现

项目介绍&#xff1a; 高校竞赛管理系统管理系统按照操作主体分为管理员和用户。管理员的功能包括字典管理、论坛管理、竞赛公告管理、获奖管理、老师管理、评审管理、评审分配管理、评审打分管理、赛事管理、赛事提交管理、赛事报名管理、用户管理、专家管理、管理员管理。用…
阅读更多...
万兴PDF专家 PDFelement Pro v10.3.8 破姐版！

万兴PDF专家 PDFelement Pro v10.3.8 破姐版！

&#x1f9d1;‍&#x1f4bb;万兴PDF专家 PDFelement Pro v10.3.8 破姐版 (https://docs.qq.com/sheet/DRVVxTHJ3RXJFVHVr)
阅读更多...
FreeRTOS软件定时器

FreeRTOS软件定时器

说明本文章基于百问网RTOS教程文档 1.硬件定时器 什么是硬件定时器&#xff0c;由硬件电路构成的定时器。在学习STM32时我们都会学到定时器&#xff0c;这个就是硬件定时器。硬件定时器不单单可以定时&#xff0c;它还可以进行PWM输出等等。硬件定时器每隔一段固定的时间会进…
阅读更多...
近几年视频取证、视频篡改检测技术发展现状及挑战

近几年视频取证、视频篡改检测技术发展现状及挑战

前言 本文主要搜集了视频取证各个子领域近几年的高影响因子/引用数的文章及其主要思想和做法&#xff0c;旨在分析目前视频篡改检测的发展现状与热点领域&#xff0c;文章中也融合了自己的一点看法和展望&#xff0c;欢迎感兴趣的同学和我多多沟通。 本文无论是文献搜集还是方…
阅读更多...
基于Spring Boot的外卖点餐系统设计与实现

基于Spring Boot的外卖点餐系统设计与实现

基于Spring Boot的外卖点餐系统设计与实现 开发语言&#xff1a;Java框架&#xff1a;springbootJDK版本&#xff1a;JDK1.8数据库工具&#xff1a;Navicat11开发软件&#xff1a;eclipse/myeclipse/idea 系统部分展示 网站首页界面图&#xff0c;通过进入网站可以查看首页、…
阅读更多...
并查集应用-连通块中点的数量and食物链

并查集应用-连通块中点的数量and食物链

文章目录 连通块中点的数量思路代码javaC 代码 食物链带扩展域的并查集代码带边权的并查集数组d的真正含义以及find()函数调用过程核心代码注意事项&#xff0c;即明白 d[i] 的含义 代码C Java 连通块中点的数量 给定一个包含 n 个点&#xff08;编号为 1∼n &#xff09;的无向…
阅读更多...
Leetcode—860. 柠檬水找零【简单】

Leetcode—860. 柠檬水找零【简单】

2024每日刷题&#xff08;122&#xff09; Leetcode—860. 柠檬水找零 实现代码 class Solution { public:bool lemonadeChange(vector<int>& bills) {int count5 0;int count10 0;for(int i 0; i < bills.size(); i) {if(bills[i] 5) {count5;} else if(bi…
阅读更多...
【自然语言处理】Word2VecTranE的实现

【自然语言处理】Word2VecTranE的实现

作业一 Word2Vec&TranE的实现 1 任务目标 1.1 案例简介 Word2Vec是词嵌入的经典模型&#xff0c;它通过词之间的上下文信息来建模词的相似度。TransE是知识表示学习领域的经典模型&#xff0c;它借鉴了Word2Vec的思路&#xff0c;用“头实体关系尾实体”这一简单的训练目…
阅读更多...
【matplot】【matlab】绘制简洁美观二维坐标系的一个例子

【matplot】【matlab】绘制简洁美观二维坐标系的一个例子

觉得下图不错美观大方&#xff0c;现仿制下图&#xff1a; import numpy as np import matplotlib.pyplot as pltdef sigmoid(x):return 1 / (1 np.exp(-x))def sigmoid_derivative(x):return sigmoid(x) * (1 - sigmoid(x))# 设置中文字体 plt.rcParams[font.family] [Tim…
阅读更多...
如何使用Go语言的标准库和第三方库？

如何使用Go语言的标准库和第三方库？

文章目录 一、如何使用Go语言的标准库示例&#xff1a;使用标准库中的fmt包打印输出 二、如何使用Go语言的第三方库示例&#xff1a;使用第三方库github.com/gin-gonic/gin创建Web服务器 总结 在Go语言中&#xff0c;标准库和第三方库的使用是日常编程中不可或缺的一部分。标准…
阅读更多...
Facebook的声音：听见社交媒体的心跳

Facebook的声音：听见社交媒体的心跳

社交媒体如今已经成为人们日常生活中不可或缺的一部分&#xff0c;而Facebook作为其中的佼佼者&#xff0c;承载着数以亿计的用户的交流、分享和连接。在这个信息爆炸的时代&#xff0c;Facebook的声音就像是社交媒体的心跳&#xff0c;传递着无数个体的情感、思想和生活。本文…
阅读更多...
NASA数据集——NASA 标准三级（L3）每月深蓝气溶胶产品提供了全球陆地和海洋上空气溶胶光学厚度（AOT）

NASA数据集——NASA 标准三级（L3）每月深蓝气溶胶产品提供了全球陆地和海洋上空气溶胶光学厚度（AOT）

VIIRS/NOAA20 Deep Blue Level 3 monthly aerosol data, 1x1 degree grid 简介 联合极地卫星系统&#xff08;JPSS&#xff09;系列 NOAA-20 仪器中的可见红外成像辐射计套件&#xff08;VIIRS&#xff09;NASA 标准三级&#xff08;L3&#xff09;每月深蓝气溶胶产品提供了全…
阅读更多...
分布式与一致性协议之Raft算法(三)

分布式与一致性协议之Raft算法(三)

Raft算法 如何复制日志 你可以把Raft算法的日志复制理解成一个优化后的二阶段提交(将二阶段优化成了一阶段)。优化后减少了一半的往返消息&#xff0c;也就是降低了一半的消息延迟&#xff0c;那日志复制的具体过程又是什么呢&#xff1f; 首先&#xff0c;领导者进入第一阶段…
阅读更多...
LT2611UX四端口 LVDS转 HDMI2.0，带音频

LT2611UX四端口 LVDS转 HDMI2.0，带音频

描述LT2611UX 是一款面向机顶盒、DVD 应用的高性能 LVDS 至 HDMI2.0 转换器。LVDS输入可配置为单端口、双端口或四端口&#xff0c;具有1个高速时钟通道和3~4个高速数据通道&#xff0c;工作速率最高为1.2Gbps/通道&#xff0c;可支持高达19.2Gbps的总带宽。LT2611UX 支持灵活的…
阅读更多...
C语言案例04 -流程控制-逻辑符的正确使用

C语言案例04 -流程控制-逻辑符的正确使用

****一.C语言逻辑运算符详解&#xff1a;逻辑与&&与逻辑或||的运用及其短路特性 你知道吗&#xff1f;逻辑运算符&&和||可是C语言世界的“流量担当”&#xff0c;它们不仅实力强大&#xff0c;还自带神秘光环——短路效应 &#x1f4dd;短路法则揭秘&#xf…
阅读更多...
CVE-2022-2602：unix_gc 错误释放 io_uring 注册的文件从而导致的 file UAF

CVE-2022-2602：unix_gc 错误释放 io_uring 注册的文件从而导致的 file UAF

前言 复现该漏洞只是为了学习相关知识&#xff0c;在这里仅仅做简单记录下 exp&#xff0c;关于漏洞的详细内容请参考其他文章&#xff0c;最后在 v5.18.19 内核版本上复现成功&#xff0c;v6.0.2 复现失败 漏洞利用 diff --git a/include/linux/skbuff.h b/include/linux/s…
阅读更多...
vscode 配置与插件记录

vscode 配置与插件记录

vscode插件 python PythonPython DebuggerruffisortPylanceJupyterJupyter KeymapJupyter Slide ShowJupyter Cell TagsautoDocstring - Python Docstring Generator ruff isort pylance autodocsting 在setting.json里这么配置&#xff0c;这样你保存时就会自动format…
阅读更多...
WordPress缓存插件有哪些？好用的缓存插件分享

WordPress缓存插件有哪些？好用的缓存插件分享

目前WordPress缓存插件有&#xff1a;WP Rocket、WP Super Cache、W3 Total Cache、Sucuri、NitroPack、SiteGround Optimizer、LiteSpeed Cache、WP-Optimize、Hummingbird、Cache Enabler、Comet Cache。 在当今的数字世界中&#xff0c;拥有一个高效的网站对于吸引和留住用…
阅读更多...
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站