数据结构-栈

栏目: 后端 · 发布时间: 5年前

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

数据结构-栈

定义

栈(英语: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/y...

项目简介:

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

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

以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

Bulletproof Web Design

Bulletproof Web Design

Dan Cederholm / New Riders Press / 28 July, 2005 / $39.99

No matter how visually appealing or packed with content a Web site is, it isn't succeeding if it's not reaching the widest possible audience. Designers who get this guide can be assured their Web site......一起来看看 《Bulletproof Web Design》 这本书的介绍吧!

HTML 压缩/解压工具
HTML 压缩/解压工具

在线压缩/解压 HTML 代码

URL 编码/解码
URL 编码/解码

URL 编码/解码

XML、JSON 在线转换
XML、JSON 在线转换

在线XML、JSON转换工具