数据结构-栈

数据结构-栈

定义

栈(英语:stack)又称为堆栈或堆叠,栈作为一种数据结构,它按照先进后出的原则存储数据,先进入的数据被压入栈底,最后的数据在栈顶,需要读数据的时候从栈顶开始弹出数据(最后一个数据被第一个读出来)。   由于堆叠数据结构只允许在一端进行操作,因而按照后进先出(LIFO, Last In First Out)的原理运作。栈也称为后进先出表

栈的应用场景

undo操作(撤销)

  • 例如:将操作的每组数据存入栈中,如果想要撤销,只需要弹出栈顶元素,就可以恢复上一步操作了。

程序调用的系统栈

  • 例如:A方法调用B方法得到返回值,B调用C得到返回值,A操作走到了B方法,这个时候可以将A的代码位置存储到栈中,然后走到B方法,B操作走到了C方法,这个时候可以将B的代码位置存储到栈中。最后C执行完成,根据栈的结构开始弹出数据,一步一步再走回A方法。

判断括号是否有效。下文会有代码实现(详细规则描述可以参考leetcode第20题)

  • 开括号必须用同一类型的括号闭合。
  • 开方括号必须按正确顺序闭合。
  • 例如:正确的:{[()]} {()} 等 。错误的:[{(})] [}{()] 等。

自定义栈基类的代码实现

  • 栈在java.util有一个工具类,先不用,自定义实现一个
创建一个接口,用来统一规范所有栈实现
package com.datastructure.stack;

public interface Stack<E> {

    /**
     * 向栈插入元素
     * @param e
     */
    public  void push(E e);


    /**
     * 取出最上面的元素,并且返回
     * @return
     */
    public E pop();

    /**
     * 获取栈的大小
     * @return
     */
    public int getSize();

    /**
     * 判断栈是否为空
     * @return
     */
    public boolean isEmpty();

    /**
     * 获取栈最上面的元素
     * @return
     */
    public E peek();
}
用基于数组的方式来实现一个栈(上篇文章数据结构-数组所写的自定义数组)
package com.datastructure.stack;

import com.datastructure.array.Array;

/**
 * @program: test
 * @description:
 * @author: Mr.Yang
 * @create: 2019-05-02 15:27
 **/
public class ArrayStack<E> implements Stack<E>{

    Array<E> array;

    public ArrayStack(int capacity){
        array=new Array<E>(capacity);
    }



    public ArrayStack(){
        array=new Array<E>();
    }

    @Override
    public void push(E e) {
        array.addLast(e);
    }

    @Override
    public E pop() {
        return array.removeLast();
    }

    @Override
    public int getSize() {
        return array.getSize();
    }


    @Override
    public boolean isEmpty() {
        return array.isEmpty();
    }


    @Override
    public E peek() {
        return array.getLast();
    }

    /**
     * 获取容量值
     * @return
     */
    public int getCapacity(){
        return array.getCapacity();
    }


    @Override
    public String toString(){
        StringBuffer sb = new StringBuffer();
        sb.append("stack: ");
        sb.append("[");
        for(int i=0;i<array.getSize();i++){
            sb.append(array.get(i));
            if(i!=array.getSize()-1){
                sb.append(", ");
            }
        }
        sb.append("]            right value is stack top");
        return sb.toString();
    }
}
测试代码
package com.datastructure.stack;

/**
 * @program: test
 * @description:
 * @author: Mr.Yang
 * @create: 2019-05-02 16:11
 **/
public class StackTest {

    public static void main(String[] args) {
        ArrayStack<Integer> integerArrayStack = new ArrayStack<>();
        for(int i=0;i<5;i++){
            integerArrayStack.push(i);
            System.out.println(integerArrayStack);
        }
        Integer pop = integerArrayStack.pop();
        System.out.println("----移除上级元素----value is "+pop);
        System.out.println("-------------移除之后的栈打印------------------");
        System.out.println(integerArrayStack);
    }
}
测试结果
stack: [0]            right value is stack top
stack: [0, 1]            right value is stack top
stack: [0, 1, 2]            right value is stack top
stack: [0, 1, 2, 3]            right value is stack top
stack: [0, 1, 2, 3, 4]            right value is stack top
----移除上级元素----value is 4
-------------移除之后的栈打印------------------
stack: [0, 1, 2, 3]            right value is stack top

leetCode第20题,花括号正确闭合

思路
  • 根据栈的数据结构特点,我们可以先将所有左括号‘[{(’放进栈中,然后判断当前字符如果是‘)]}’这种的右括号,但是栈顶的括号却不匹配,返回false
  • 注意控制判断
  • 这里使用java自带的栈工具类来实现
  • leetcode给的测试例子:

1

2

3

4

5

输入例子

()

()[]{}

(]

([)]

{[]}

代码实现
package com.datastructure.stack;

import java.util.Stack;

/**
 * @program: test
 * @description:
 * @author: Mr.Yang
 * @create: 2019-05-02 16:59
 **/
public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.isValid("{\"name\": \"网站\",\"num\": 3,\"sites\": [ \"Google.com\", \"Taobao.com\", \"Waibo.wang\" ]}"));
    }
    public boolean isValid(String s) {
        Stack<Character> characters = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '{' || c == '[' || c == '(') {
                characters.push(c);
            } else {
                if(characters.isEmpty()){
                    return false;
                }
                Character peek = characters.pop();
                switch (c) {
                    case '}':
                        if (!peek.equals('{')) {
                            return false;
                        }
                        continue;
                    case ']':
                        if (!peek.equals('[')) {
                            return false;
                        }
                        continue;
                    case ')':
                        if (!peek.equals('(')) {
                            return false;
                        }
                        continue;
                }
            }
        }
        return characters.isEmpty();
    }

    /*public boolean isValid(String s) {
        Stack<Character> characters = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '{' || c == '[' || c == '(') {
                characters.push(c);
            } else {
                if(characters.isEmpty()){
                    return false;
                }
                Character toChar = characters.pop();
                if(c == ')' && toChar != '('){
                    return false;
                }
                if(c == '}' && toChar != '{'){
                    return false;
                }
                if(c == ']' && toChar != '['){
                    return false;
                }
            }
        }
        return characters.isEmpty();
    }*/
}
如果想实现更多字符串关于括号的匹配,如JSON等等,可以根据栈的特点来实现

代码例子GIT地址:https://git.dev.tencent.com/yangxiaojie123/designPattern.git

项目简介:这个项目是我做测试,学习的主要项目,目前里面包含了:

  • 一些设计模式的demo(抽象工程模式,适配器模式,外观模式,命令模式,装饰者模式等等)
  • 即将学习的数据结构demo,数组,栈,后续还会持续更新数据结构,可能会有队列,链表,递归,红黑树,线段树等等一系列,如果感兴趣,欢迎留言。

本文分享自微信公众号 - JAVA知识总结与分享(summing_up_sharing)

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

原始发表时间:2019-05-02

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 还在使用 SimpleDateFormat?你的项目崩没?

    日常开发中,我们经常需要使用时间相关类,说到时间相关类,想必大家对SimpleDateFormat并不陌生。主要是用它进行时间的格式化输出和解析,挺方便快捷的,...

    程序猿DD
  • [NewLife.XCode]事务处理(算准你的每一分钱)

    NewLife.XCode是一个有10多年历史的开源数据中间件,支持nfx/netstandard,由新生命团队(2002~2019)开发完成并维护至今,以下简...

    大石头
  • [NewLife.XCode]功能设置

    NewLife.XCode是一个有10多年历史的开源数据中间件,由新生命团队(2002~2019)开发完成并维护至今,以下简称XCode。

    大石头
  • Mybatis中 $ 和 # 千万不要乱用!

    这是一次代码优化过程中发现的问题,在功能优化后发现部分数据查不到出来了,问题就在于一条sql上的#和$。

    程序猿DD
  • Oracle库Delete删除千万以上普通堆表数据的方法

    注意:下面方法以删除2014年之前的所有记录为例,请根据你的实际情况修改,防止误操作。

    Alfred Zhao
  • C++内联函数,默认参数,占位参数

    之前讲过宏定义会经过预处理器进行文本替换,缺点就在于没有类型检查,没有任何编译过程,编译器根本不知道类型是什么.

    张诺谦
  • 分享一道大多数人都会做错的JVM题

    有关Java虚拟机类加载机制相关的文章一搜一大把,笔者这里也不必再赘述一遍了。笔者这里捞出一道code题要各位大佬来把玩把玩,如果你一眼就看出了端倪,那么恭喜你...

    JAVA葵花宝典
  • [NewLife.XCode]对象字典缓存(百万军中取敌首级)

    NewLife.XCode是一个有10多年历史的开源数据中间件,支持nfx/netcore,由新生命团队(2002~2019)开发完成并维护至今,以下简称XCo...

    大石头
  • Oracle存储过程获取YYYY-MM-DD的时间格式

    总结:在Oracle存储过程想要获取YYYY-MM-DD的时间格式,可以转换成字符串处理,可以临时指定会话的NLS_DATE_FORMAT变量,还可以整体修改客...

    Alfred Zhao
  • Java语言中的生僻知识

    最近有一首名叫《生僻字》的流行歌曲火遍大江南北,创作者给佶屈聱牙的生僻字,配上了优美明快的旋律,竟然让歌曲变得琅琅上口、悦耳动听起来,平时不太常见的拒人于千里之...

    JAVA葵花宝典

扫码关注云+社区

领取腾讯云代金券