数据结构之栈 た 入场券 2022-10-14 10:49 170阅读 0赞 **一.什么是栈?** 本文将介绍一个重要的数据结构—栈,和之前讲到的链表、数组一样也是一种数据呈线性排列的数据结构,不过在这种结构中,我们只能访问最新添加的数据。栈就像是一摞书,拿到新书时我们会把它放在书堆的最上面,取书时也只能从最上面的新书开始取。 **栈** ![在这里插入图片描述][20210521093834131.png] 如上就是栈的概念图,现在存储在栈中的只有数据 Blue。往栈中添加数据的时候,新数据被放在最上面。 ![在这里插入图片描述][2021052109390075.png] 然后,我们往栈中添加了数据 Green。往栈中添加数据的操作叫作入栈。 ![在这里插入图片描述][20210521093919869.png] 接下来,数据 Red 入栈。 ![在这里插入图片描述][20210521093935175.png] 从栈中取出数据时,是从最上面,也就是最新的数据开始取出的,即 Red。从栈中取出数据的操作叫作出栈。 ![在这里插入图片描述][20210521093955403.png] 如果再进行一次出栈操作,取出的就是 Green 了。 像栈这种最后添加的数据最先被取出,即后进先出的结构,我们称为 Last In First Out,简称 LIFO。 与链表和数组一样,栈的数据也是线性排列,但在栈中,添加和删除数据的操作只能在一端进行,访问数据也只能访问到顶端的数据,想要访问中间的数据时,就必须通过出栈操作将目标数据移到栈顶才行。 介绍完栈的基本知识后,接下来举一个例子,比如大家正在看公众号文章,那我就拿微信的订阅号为例。 **二.如何理解栈?** 首先你打开订阅号,是一个公众号列表,之后你点击了一个公众号,进入了相应的文章列表界面。点击了某某文章。 好了,现在你想返回订阅号怎么办呢?向右滑两次吧,第一次回到文章列表界面,第二次回到订阅号界面。 这时候你就发现了,这些界面的储存结构可以说是一个栈结构,你打开文章详情页面,必须经过两次入栈才能达到,你想回到订阅号界面(位于栈底),必须经历两次出栈把前面两个界面移除。 **三.栈的实现** 看到这里,相信你已经对栈有了初步的理解,栈主要包含两个操作,入栈和出栈,也就是在栈顶插入一个数据和从栈顶删除一个数据。光理解还不够,我们还要动手去实现栈,接下来让我们来看一看如何用代码实现一个栈。 栈有两种存储结构,即顺序存储和链式存储,也就是说栈既可以用数组来实现,也可以用链表来实现。用数组实现的栈,我们叫作顺序栈,用链表实现的栈,我们叫作链式栈。 首先来看下用数组实现的栈是怎么样的,其实现如下图所示: ![在这里插入图片描述][20210521094321714.png] 那么我先用 Java 语言来实现下顺序栈,代码如下: /** * 基于数组实现的顺序栈 * * @author wupx * @date 2020/02/11 */ public class ArrayStack { /** * 数组 */ private String[] items; /** * 栈中元素个数 */ private int count; /** * 栈的大小 */ private int n; /** * 初始化数组,申请一个大小为 n 的数组空间 * * @param n */ public ArrayStack(int n) { this.items = new String[n]; this.n = n; this.count = 0; } /** * 入栈 * * @param item * @return */ public boolean push(String item) { // 数组空间不够了,直接返回 false,入栈失败。 if (count == n) { return false; } // 将 item 放到下标为 count 的位置,并且 count 加一 items[count] = item; ++count; return true; } /** * 出栈 * * @return */ public String pop() { // 栈为空,则直接返回 null if (count == 0) { return null; } // 返回下标为 count-1 的数组元素,并且栈中元素个数 count 减一 String tmp = items[count - 1]; --count; return tmp; } } 另外一种就是链式栈,它的实现如下图所示: ![在这里插入图片描述][20210521094355860.png] 再用链表去实现栈,代码如下: /** * 基于链表实现的链式栈 * * @author wupx * @date 2020/02/11 */ public class LinkedListStack { private Node top = null; /** * 入栈 * * @param value */ public void push(int value) { Node newNode = new Node(value, null); // 判断是否栈空 if (top != null) { newNode.next = top; } top = newNode; } /** * 出栈 * * @return */ public int pop() { if (top == null) { // -1 表示栈中没有数据 return -1; } int value = top.data; top = top.next; return value; } public void printAll() { Node p = top; while (p != null) { System.out.print(p.data + " "); p = p.next; } System.out.println(); } private static class Node { private int data; private Node next; public Node(int data, Node next) { this.data = data; this.next = next; } public int getData() { return data; } } } 在对栈有了更深一步的理解和实践后,让我们来看下它的空间、时间复杂度各是多少呢? 不管是顺序栈还是链式栈,我们存储数据只需要一个大小为 n 的数组就够了。在入栈和出栈过程中,只需要一两个临时变量存储空间,所以空间复杂度是 O(1)。 入栈和出栈只会影响到最后一个元素,不涉及其他元素的整体移动,所以无论是以数组还是以链表实现,入栈、出栈的时间复杂度都是 O(1)。 **总结** 看完之后,相信大家都对栈有了一定的了解,让我们总结下这篇文章的内容,栈是一种线性逻辑结构,只支持入栈和出栈操作,遵循后进先出的原则(FILO)。栈既可以通过数组实现,也可以通过链表来实现,不管基于数组还是链表,入栈、出栈的时间复杂度都为 O(1)。 [20210521093834131.png]: /images/20221014/3e6a22d02ff74d1da812aa3e21670d5e.png [2021052109390075.png]: /images/20221014/345375d02703444388539ce82e9cdb9a.png [20210521093919869.png]: /images/20221014/a4b2c4feab61436aa4cd11c00a13be8e.png [20210521093935175.png]: /images/20221014/d3316d690e7049299b03466bc97df78f.png [20210521093955403.png]: /images/20221014/2d289c4b9469420ba4800274582cb806.png [20210521094321714.png]: /images/20221014/21655e0b927a42619850303a81224f14.png [20210521094355860.png]: /images/20221014/4440347ff8b64ac398a51e056dd71d5f.png
相关 数据结构之栈 一.什么是栈? 本文将介绍一个重要的数据结构—栈,和之前讲到的链表、数组一样也是一种数据呈线性排列的数据结构,不过在这种结构中,我们只能访问最新添加的数据。栈就像是一摞书, た 入场券/ 2022年10月14日 10:49/ 0 赞/ 171 阅读
相关 数据结构之栈 栈的介绍 1)栈是一个先入后出的有序列表 2)允许插入和删除的一端,为变化的一端,称为栈顶,另一端是固定的一端,为栈底 数组模拟栈 ![在这里插入图片描述][ ╰+攻爆jí腚メ/ 2022年08月31日 13:23/ 0 赞/ 164 阅读
相关 数据结构之栈 栈是一种先进后出的线性结构,只允许在一端插入删除,属于逻辑结构。 栈的定义 package com.zhiru; / 栈是一种先进后出 男娘i/ 2022年08月11日 03:27/ 0 赞/ 177 阅读
相关 数据结构之栈 1、定义:栈(stack)是限制在插入和删除只能在一个位置进行操作的一种表结构,该合位置是表的末端,称作栈顶(top),对栈的基本操作的push()进栈和pop()出栈,一般栈 ╰半夏微凉°/ 2022年08月06日 01:05/ 0 赞/ 196 阅读
相关 数据结构之栈 栈是一种数据结构,特点是先进后出。比较通俗的说那就一个容器一端是封闭的,只能是先来的后出去。 先是写一个使用数组的栈类ArrayStack. / ArraySt 秒速五厘米/ 2022年07月12日 03:43/ 0 赞/ 216 阅读
相关 数据结构之栈 头文件: using namespace std; template <class T> class MyStack { 妖狐艹你老母/ 2022年05月27日 05:39/ 0 赞/ 197 阅读
相关 数据结构之栈 一、顺序栈 1.0 理解栈 栈是一种比线性表还要简单的数据结构,因为他就是对线性表的限制后的数据结构 即 只允许在线性表的尾部进行插入和删除操作 偏执的太偏执、/ 2022年05月25日 02:37/ 0 赞/ 241 阅读
相关 数据结构之栈 什么是栈 从栈的操作特性上来看,栈是一种 “操作受限”的线性表,只允许在一端插入和删除数据,且满足先进后出、后进先出的特性。 实现一个栈 栈可以用数组或链表来实现 Bertha 。/ 2022年05月16日 14:29/ 0 赞/ 230 阅读
相关 数据结构之栈 数据结构栈的相关学习: 简介 限定仅在表尾进行插入和删除操作的线性表。允许插入和删除的一端成为栈顶,另一端成为栈低,不含任何元素的栈成为空栈,栈又称为先进先出的线性表 今天药忘吃喽~/ 2022年02月05日 05:09/ 0 赞/ 281 阅读
还没有评论,来说两句吧...