作者: 程序员will | 来源:发表于2019-11-04 15:33 被阅读0次

数据结构之栈

原理

栈是一种比较常见的数据结构,它的操作可以看做是数组的子集,因为栈只能从栈顶取元素和添加元素,并且栈遵循先进后出原则,即First in last out(FILO).

栈的运用很广泛,比如在操作系统中,系统常常在运行过程中,会中途去执行另外的程序,随后再返回执行原程序,那么系统是如何找到之前中断程序的位置的呢?答案是系统中维护了一个系统栈。

fun A(){
....
B()
...
}
fun B(){
....
C()
....
}
fun C(){
...
...
...
}

比如在上方的程序A中,当A运行到第二行时,程序会去执行B方法,此时系统会将A2压入系统栈,随后再去执行B,当B运行到第二行时,程序又进行跳转到C方法,同理,此时程序会将B2压入栈。

那么此时栈中一共有两个元素,自顶向下分别为B2、A2,于是当程序执行完C方法时,会将B2出栈,那么程序就回到B2行接着往下执行,同理当B方法执行完,A2出栈,程序回到A2行继续执行,直到完成。

栈的基本实现

实现一个栈,这里采用的是构造一个栈结构的接口,写一个实现类实现该接口,接口类变量为上一节实现的动态数组,因为栈的操作可以看做是数组的子集。
具体代码如下:
接口类

public interface Stack<E> {
    int getSize();
    boolean isEmpty();
    void push(E e);
    E pop();
    E peek();
}

这里也运用了泛型,使其能够接受任意的类型的变量。

实现类:

public class ArrayStack<E> implements Stack<E> {
    Array<E> array;

    //有参的构造函数
    public ArrayStack(int capacity){
        array = new Array<E>(capacity);
    }

    //无参的构造函数
    public ArrayStack(){
        array = new Array<>();
    }

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

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

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

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

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

    public int getCapacity(){
        return array.getCapacity();
    }

    @Override
    public String toString(){
        StringBuilder rst = new StringBuilder();
        rst.append("Stack:");
        rst.append("[");
        for(int i = 0; i < array.getSize(); i++){
            rst.append(array.get(i));

            if(i != array.getSize()-1){
                rst.append(",");
            }
        }
        rst.append("] top");
        return rst.toString();
    }
}

测试类:

public class Main {

    public static void main(String[] args) {
        ArrayStack<Integer> stack = new ArrayStack<>();

        for(int i = 0; i < 5; i++){
            stack.push(i);
            System.out.println(stack);
        }

        stack.pop();
        System.out.println(stack);
    }
}

测试结果

Stack:[0] top
Stack:[0,1] top
Stack:[0,1,2] top
Stack:[0,1,2,3] top
Stack:[0,1,2,3,4] top
Stack:[0,1,2,3] top

这里还缺少了我们实现的动态数组类,详情可以看上一节数组章节。

应用(括号匹配)

利用栈这种类型的数据结构,可以解决一些算法问题。

比如leetcode中第20题,括号匹配的问题。

即这样的字符串"{[()]}"是正确的,但是"[(}]"这样的就是错误的,你需要设计一个方法,判断传入的这种类型的字符串是否是正确的。

class Solution {
        public boolean isValid(String s){
            Stack<Character> stack = new Stack<>();
            for (int i = 0; i < s.length(); i++){
                char c = s.charAt(i);

                if(c == '(' || c == '{' || c == '[')
                    stack.push(c);
                else {
                    if(stack.isEmpty())
                        return false;
                    char topChar = stack.pop();
                    if(c == ')' && topChar != '(')
                        return false;
                    if(c == '}' && topChar != '{'){
                        return false;
                    }
                    if(c == ']' && topChar != '['){
                        return false;
                    }
                }
            }
            return stack.isEmpty();
        }
    }

示例代码

相关文章

  • Java实现栈

    数组栈:压栈、出栈、返回栈顶元素 链式栈:压栈、出栈、返回栈顶元素

  • 数据结构之 栈

    栈结构 链式栈 一.栈结构体 1构建空栈 2栈置空 3判断栈空 4获取栈顶 5入栈 6出栈 7便利栈 二.链式栈 ...

  • 栈和队列

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

  • 递归累加数组

    入栈 5入栈 4入栈 3入栈 2入栈 1出栈 [1 0]出栈 [2 1 0]出栈 [3 2 1 0]出栈 [4 3...

  • 栈的逻辑结构和存储结构

    main()进栈s(1)进栈s(0)进栈 s(0)出栈s(1)出栈main()出栈 顺序栈 一个数组 + 指向栈顶...

  • 单调栈 2020-06-12(未经允许,禁止转载)

    1.单调栈 指栈内元素保持单调性的栈结构,分为单调增栈(栈底到栈顶元素递增)和单调减栈(栈底到栈顶元素递减) 2....

  • 链栈的操作

    链栈的定义 链栈的操作 初始化 判断栈空 入栈 出栈

  • 函数调用栈平衡

    栈平衡 栈平衡:函数调用前后的栈顶指针指向的位置不变 内平栈 外平栈 内平栈: 指的是在函数调用返回之前使栈保持...

  • 栈的简单Java实现

    栈栈的特点是先进后出,出栈、入栈都是在栈顶操作。

  • 汇编学习-入栈和出栈

    栈有两个基本的操作:入栈和出栈。入栈就是将一个新的元素放到栈顶,出栈就是从栈顶取出一个元素。栈顶的元素总是最后入栈...

网友评论

    本文标题:

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