专栏首页村雨遥关于 “栈” 的那点破事

关于 “栈” 的那点破事

目录
  • 1. 基本知识
    • 1.1 什么是栈
    • 1.2 栈的特点
    • 1.3 栈的操作
  • 2. 栈的实现
    • 2.1 顺序栈
    • 2.2 链式栈

1. 基本知识

1.1 什么是栈

用生活中最实际的例子来说,类似于砌砖,加入我们要砌一堵墙,我们肯定是从下往上砌,先拿的砖头就砌在最下边,后拿的砖头就砌到最上边。但是如果监工觉得这堵墙不合适,我们就需要把这堵墙拆了重砌,这时候我们需要先把上面的砖先取掉,才能取下面的砖。而这种先进后出,后进先出的结构就叫做 “栈”。

1.2 栈的特点

先进后出,后进先出。

1.3 栈的操作

栈最常用的操作无非两种,分别是 出栈 和 入栈。

2. 栈的实现

2.1 顺序栈

所谓顺序栈,就是基于数组来实现栈。出入栈的操作实际上就是根据下标获取相应元素,所以时间复杂度为

O(1)

。但是基于数组的操纵存在一个问题就是当栈满时,此时就需要动态扩容,此时就相当于给数组扩容,比较麻烦。

/**
* 基于数组而实现的顺序栈
*/
public class ArrayStack{
    private String[] arr; // 数组
    private int count; // 栈中元素个数
    private int size; // 栈大小

    // 构造函数
    public ArrayStack(int size){
        this.arr = new String[size];
        this.size = size;
        this.count = 0;
    }

    // 入栈
    public boolean push(String item){
        // 数组空间不足,入栈失败
        if(count == size){
            return false;
        }
        // 将插入元素放到下标为 count 的位置
        arr[count] = item;
        // 数组长度 +1
        ++count;
        return true;
    }

    // 出栈,并返回出栈元素
    public String pop(){
        // 栈为空,直接返回 null
        if(count == 0){
            return null;
        }
        // 返回最后一个元素
        String tmp = arr[count - 1];

        // 数组长度 -1

        return tmp;
    }
}

2.2 链式栈

链式栈是基于链表来实现栈,不用考虑顺序栈中的动态扩容问题。而出入栈也只是针对栈顶元素操作,此时时间复杂度为

O(1)

  1. 定义栈节点
public class Node{
    private int data; // 数据域
    private Node next; // 指针域

    // 构造函数
        // 构造函数
    public Node(int data){
        this.data = data;
        this.next = null;
    }

    public Node(int data, Node next){
        this.data = data;
        this.next = next;
    }

    // 获取数据域
    public int getData(){
        return data;
    }

}
  1. 基于链表实现栈
/**
* 基于链表实现栈
*/

public class LinkedListStack{
    // 栈顶指针
    private Node top = null;

    // 入栈
    public void push(int value){
        // 创建一个节点
        Node node = new Node(value);

        // 判断栈是否为空,为空则作为栈顶元素
        if(top == null){
            top = node;
        } else {
          // 否则则加入 top 栈节点前
            node.next = top;
            top = node;
        }
    }

    // 出栈
    public int pop(){
        // 若栈顶节点为 null,则栈为空
        if(top == null){
            return -1;
        }

        // 不为 null 则执行出栈操作
        int val = top.data;
        top = top.next;
        // 返回出栈值
        return val;
    }

    // 遍历栈元素
    public void printStack(){
        // 强栈顶指针赋给 p
        Node p = top;
        // 循环遍历栈
        while(p != null){
            System.out.println(p.data);
            p = p.next;
        }
    }
}

本文分享自微信公众号 - 村雨遥(cunyu1943),作者:村雨遥

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-09-07

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode 905. 按奇偶排序数组

    905. 按奇偶排序数组: https://leetcode-cn.com/problems/sort-array-by-parity/

    村雨遥
  • Java 版 C 语言经典 100 例(16 - 20

    村雨遥
  • 时间复杂度与空间复杂度,看这一篇就够了!

    若存在函数 ,使得当 趋向无穷大时, 的极限值为不等于 0 的常数,则称 是 的同数量级函数,记作 ,称 为算法的渐进时间复杂度,简称 时间复杂度,用大...

    村雨遥
  • 干货|十分钟快速掌握CPLEX求解VRPTW数学模型(附JAVA代码及CPLEX安装流程)

    提到带时间窗车辆路径问题(vehicle routing problems with time windows,VRPTW),就不得不先说说车辆路径问题(...

    短短的路走走停停
  • Vue移动端框架Mint UI教程-数据渲染到页面(六)

    拿到res.data之后,要赋值给page实例里面的data 所以在data里面设置一个默认的空数组

    王小婷
  • 数据挖掘之聚类算法K-Means总结

    序   由于项目需要,需要对数据进行处理,故而又要滚回来看看paper,做点小功课,这篇文章只是简单的总结一下基础的Kmeans算法思想以及实现; 正文:   ...

    Gxjun
  • C# 泛型的简单理解(安全、集合、方法、约束、继承)

    泛型允许你在编译时实现类型安全。它们允许你创建一个数据结构而不限于一特定的数据类型。然而,当使用该数据结构时,编译器保证它使用的类型与类型安全是相一致的。泛型提...

    aehyok
  • 数据清洗 Chapter07 | 简单的数据缺失处理方法

    使用Scipy库的interpolate模块实现拉格朗日插值 步骤如下: 1、确定非缺失值的索引 2、找出含有缺失值列的其他值 3、调用lagran...

    不温卜火
  • 树状数组解析

    prefixSum(idx):求从数组第一个位置到第idx(含idx)个位置所有数字的和。

    黑白格
  • Android开发之瀑布流控件的实现与使用方法示例

    本文实例讲述了Android开发之瀑布流控件的实现与使用方法。分享给大家供大家参考,具体如下:

    砸漏

扫码关注云+社区

领取腾讯云代金券