美文网首页
数据结构之栈

数据结构之栈

作者: TioSun | 来源:发表于2020-07-21 21:25 被阅读0次

栈是一种很有意思的数据结构,它的特点是先入后出。大家可以想象一下弹夹,先被压入弹夹的子弹反而会后射出。

栈的特点

  1. 先入后出
  2. 只能从一端入栈或出栈

栈的构造


// 顺序栈
public class ArrayStack {
  private String[] items;  // 栈内元素
  private int current;       // 栈顶下标,-1代表空栈
  private int size;           //栈的大小

  // 构建一个容量为size的栈
  public ArrayStack(int size) {
    this.items = new String[size];
    this.size = size;
    this.current = -1;
  }

  // 入栈操作
  public boolean push(String item) {
    // 当栈顶下标等于容量-1时标识栈满,直接返回false,入栈失败。
    if (current == size-1) {
        return false;
    }
    // 移动栈顶指针
    current++
    // 将item放到栈顶
    items[current] = item;
    return true;
  }
  
  // 出栈操作
  public String pop() {
    // 栈为空,则直接返回null
    if (current == -1) {
       return null;
    }
    // 返回栈顶元素
    String tmp = items[current];
    current--;
    return tmp;
  }
  // 查看栈顶元素
  public String peek() {
    if (current == -1) {
       return null;
    }
    return items[current];
  }
}

可以看出不管是入栈还是出栈,空间复杂度和时间复杂度都是O(1)

栈的应用

栈适用于需要知道最近一次操作或者数据的场合。如leetCode第20题:
给定一个只包括 '(',')','{','}','[',']' 的字符串,判断字符串是否有效。
解题思路:
遍历字符,遇到左扩号则压栈,遇到右扩号则弹出栈顶元素和有扩号进行匹配,若匹配成功则继续遍历,匹配失败则直接返回字符串非法

推荐练习

leetCode 20: 有效的扩号
leetCode 739: 每日温度
leetCode 227: 基本计算器2

相关文章

  • Android面试题总结(题目+复习链接)

    数据结构 1.栈实现原理 java数据结构与算法之栈(Stack)设计与实现 - CSDN博客 2.链表实现原理 ...

  • 数据结构之栈 原理 栈是一种比较常见的数据结构,它的操作可以看做是数组的子集,因为栈只能从栈顶取元素和添加元素,并...

  • 数据结构之---栈

    数据结构之---栈 顺序栈 内部采用数组实现 结构图; 定义结构体: 函数声明 进栈以及出栈 图示: 其余操作 链...

  • Activity启动模式精讲

    讲解本技术点之前需要准备的技术点回顾 栈数据结构 数据结构图文解析之:栈的简介及C++模板实现 - melonst...

  • 数据结构之栈的链式存储结构

    之前写了栈的顺序存储结构,对栈的定义和操作进行了说明 数据结构之栈的顺序存储结构 现在接着写栈的链式存储结构 栈的...

  • 栈和队列

    1、栈 栈是一种先进先出的数据结构。栈顶进栈,栈顶出栈。 数据结构 栈的初始化 进栈 出栈 栈的最小值 2、队列 ...

  • Java 基础 35 数据结构和ArrayList集合的相关案例

    1.1 数据结构 什么是数据结构?数据的组织方式.维基百科 1.1.1 常见数据结构之栈和队列 1.1.2常见数据...

  • 实战PHP数据结构基础之栈

    栈和队列 栈和队列和之前讲到的实战PHP数据结构基础之双链表 一样都是线性结构。 栈有什么特点 栈遵循后进先出的原...

  • 004 go语言实现栈

    1 数据结构 数据结构: 要实现的功能:0 栈的初始化1 获取栈长度2 入栈3 出栈4 清空栈内容5 判断栈是否为...

  • java高级知识点

    1.数据结构 程序=数据结构+算法 栈:后进先出,线性结构 入栈:push 出栈:pop假如已知入栈顺序是ab...

网友评论

      本文标题:数据结构之栈

      本文链接:https://www.haomeiwen.com/subject/tmiwkktx.html