《Java小子怒闯数据结构九重天》第三重天——栈

2年前 (2022) 程序员胖胖胖虎阿

222 0 0

本专栏文章主要用于帮助Java使用者快速上手数据结构，刷算法题！

前言

自古以来数据结构界就分为九重天，据说冲破这九重天之后就可以去进攻算法界最终修炼最后成佬，受万人敬仰。

但是这谈何容易，因为每一重天都有神兽把守，想要冲破每一重天都必须收服守护的神兽才行。

守护九重天的神兽分别是：数组、字符串、栈、队列、链表、树、散列表、堆、图。可见他们的战斗力也是逐层增强的。想只凭靠自身的能力拿下他们谈何容易。

不过大家不必惊慌，我这里有一本上古秘籍《Java小子怒闯数据结构九重天》，里面有每一重天神兽的攻略。只要修炼者仔细钻研里面的每一篇，对九重天了如指掌之后，冲破这九重天也是易如反掌的。

今天为大家带来第三重天的攻略！
《Java小子怒闯数据结构九重天》第三重天——栈

1.🌀栈的基础知识

栈(Stack）：只允许在一端进行插入或删除的线性表

栈有两个概念是：栈底和栈顶。一般栈只允许在栈顶进行操作，这样就会让栈有一个特性——后进先出（LIFO:Last in, First out结构）。

栈的重要知识：

（1）栈是函数中定义的基本类型变量，对象的引用变量都在函数的栈内存中分配；
（2）栈内存特点，数据一执行完毕，变量会立即释放，节约内存空间；
（3）栈内存中的数据，没有默认初始化值，需要手动设置；

1.1 入栈

入栈push:入栈也称压栈，指的是栈的插入操作，在栈顶位置插入新的数据元素。

下图从左到右依次是入栈操作演示：
《Java小子怒闯数据结构九重天》第三重天——栈

1.2 出栈

出栈pop:出栈也称弹栈，指的是栈的删除操作，删除栈顶位置的数据元素。
下

下图从左到右依次是出栈操作演示：
《Java小子怒闯数据结构九重天》第三重天——栈
综合两幅图，我们就可以来看出来栈后进先出的操作。

2.🌀Java中实例化栈

在Java中为栈特地实现了一个类为Stack，它实现了一个标准的后进先出的栈，也定义了自己的一些方法。

初始化一个栈的写法：E表示数据类型，stack是你给栈起的名字。

Stack <E> stack = new Stack<E>();

我们在声明Stack类对象之后就可以使用，类的实例化stack来调用Stack自带的一些方法了。这些方法我们后面会仔细讲到了。

但是我们在做题中需要用到栈结构时一般不使用Stack来实现栈结构。这是为什么呢？这又是谁说的呢？

其实这并不是某个Java大佬或者大家总结出来的习惯，而是Java的官方文档中自己提出来的。

我们可以在Java官网中查一下Stack得到以下结果：
《Java小子怒闯数据结构九重天》第三重天——栈
我们对上面一大段英文进行翻译：

Stack类表示后进先出（LIFO）对象堆栈。它通过五个操作扩展了类向量，允许将向量作为堆栈处理。提供了常见的推送和弹出操作，以及一种查看堆栈顶部项目的方法、一种测试堆栈是否为空的方法，以及一种搜索堆栈中某个项目并发现其距离顶部有多远的方法。首次创建堆栈时，它不包含任何项。

Deque接口及其实现提供了一组更完整、更一致的后进先出堆栈操作，应该优先于此类使用。例如：

Deque<Integer> stack = new ArrayDeque<Integer>();

所以我们一般在做题或者使用到栈结构的时候一般都是使用下面形式来实例化栈的。

Deque<E> stack = new ArrayDeque<E> ();

那么具体为什么不使用Stack呢？

是因为Stack类继承于Vector类，而Vector是线程安全的，每个可能出现线程安全的方法上加了synchronized关键字，所以效率低。所以最后导致Stack的效率也比较低！

3.🌀Java中栈常用API

3.1 使用Stack类实现的栈

3.1.1 入栈

stack.push(value);

3.1.2 查看此堆栈顶部的对象，而不从堆栈中删除它

stack.peek();

3.1.3 删除此堆栈顶部的对象，并将该对象作为此函数的值返回

stack.pop();

3.1.4 判断栈是否为空，返回一个boolean类型的值

stack.empty();

3.2 使用Deque类实现的栈

官方推荐的是使用Deque的实现子类ArrayDeque来实现栈，不过平时我们使用到LinkedList这个实现子类也比较多。

Deque<E> stack = new ArrayDeque<E>();
Deque<E> stack = new LinkedList<E>();

ArrayDeque与LinkedList都实现了Deque接口，区别：

（1）它们的底层数据结构不同，ArrayDeque是基于数组，LinkedList是基于链表，ArrayDeque默认长度为16，当容量不够需要扩容（两倍），其扩容很费时间（需要复制原数组到新数组）。所以未知数据量时，尽量使用LinkedList
（2）ArrayDeque适合频繁访问，LinkedList适合频繁删除

ArrayDeque与LinkedList对应实现栈的方法：

ArrayDeque与LinkedList本身也有push(e)，pop()，peek() 方法，功能与Stack中的一致。

在ArrayDeque与LinkedList中，isEmpty()与Stack中的empty()方法对应。

4.🌀Java实现栈

栈底层有两种结构来实现：数组与链表。那么我们自己能否使用数组与链表来实现一个栈呢？

这当然是可以的，接下来我们就分别使用数组与链表来实现栈结构。

4.1 用数组实现栈

public class MyStack {

    //定义栈的大小
    private int maxStack;
    //底层使用数组来实现数组
    private int[] stack;
    //表示栈顶所在的位置，默认情况下如果没有数据时，使用-1
    private int top = -1;

	//构造函数
    public MyStack(int maxStack) {
        this.maxStack = maxStack;
        stack=new int[maxStack];
    }

    //判断是否已经满栈
    public boolean isFull(){
        return this.top == this.maxStack-1;
    }

    //判断栈是否是空栈
    public boolean isEmpty(){
        return  this.top == -1;
    }

	//入栈
    public void push(int val){
        //在压栈之前要先判断是否栈满
        if (isFull()){
            throw  new RuntimeException("栈已满！");
        }
        top++;//指针到下一个位置
        stack[top]=val;//添加元素

    }

    //出栈
    public int pop(){
        //在弹栈之前要先判断是否为空栈
        if (isEmpty()){
            throw new RuntimeException("栈为空");
        }
        int value= stack[top];
        top--;
        return value;
    }
    
    // 查看栈顶元素，不删除
    public int peek(){
        if (isEmpty()){
            throw new RuntimeException("栈为空");
        }
        int value= stack[top];
        return value;
	}
	
    //查看栈中所有元素
    public void list(){
        System.out.println(Arrays.toString(stack));
    }

}

4.2 用链表实现栈

//定义链表节点，即每一个栈元素
class Node{
    public int val;
    public Node next;
    
    public Node(int val){
        this.val=val;
    }
}

public class MyStack{
	//底层使用链表实现栈
    Node head=null;
    
    //默认构造方法
    public MyStack(){
    }
    
    // 入栈
    public int push(int val){
        Node node=new Node(val);
        node.next = head;
        head = node;
        return head.val;
    }
    
    // 出栈
    public int pop(){
        if(empty()){
            throw new RuntimeException("栈为空");
        }
        int val=head.val;
        head=head.next;
        return val;
    }
    
    // 查看栈顶元素，不删除
    public int peek(){
        if(empty()){
            throw new RuntimeException("栈为空");
        }
        return head.val;
    }
    
    // 判断栈是否为空
    public boolean empty(){
        return head==null;
    }
}

5.🌀栈进阶练习

Leetcode 20. 有效的括号
《Java小子怒闯数据结构九重天》第三重天——栈
题解：

栈先入后出特点恰好与本题括号排序特点一致，即若遇到左括号入栈，遇到右括号时将对应栈顶左括号出栈，则遍历完所有括号后 stack 仍然为空则返回true。

class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack= new Stack();
        for(char c : s.toCharArray()) {
            if(c == '(' || c == '{' || c == '[') {
                stack.push(c);
            }
            else if(c == ')' && !stack.empty()) {
                if(stack.pop() != '(')
                return false;
            }else if(c == '}' && !stack.empty()) {
                if(stack.pop() != '{')
                return false;
            }else if(c == ']' && !stack.empty()) {
                if(stack.pop() != '[')
                return false;
            }else return false;
        }
        if(stack.empty()) return true;
        else return false;
    }
}