栈 和 队列

什么是栈?

        一种特殊的线性表,只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶,另一端称为栈底。栈中的数据元素遵守后进先出(LIFO - Last In First Out)的原则。

从数据结构的角度来看,栈 就是一种数据结构。

压栈 和 出栈

  • 压栈:栈的插入操作叫做进栈/压栈/入栈,入数据在栈顶。
  • 出栈:栈的删除操作叫做出栈。出数据在栈顶。


Java 虚拟机栈

        Java 虚拟机 JVM 可分五个部分

        方法区:存放类定义信息、字节码、常量等数据,在Sun HotSpot JVM中,这块也称为Perm Gen。

        堆:创建的对象信息将放入堆中,堆内部如何实现各虚拟机各不相同,对于Sun HotSpot JVM来说又分为Young Gen和Tenured Gen,更详细描述参见《[Java性能剖析]Sun JVM内存管理和垃圾回收 》

        Java栈:
对于每个执行线程,会分配一个Java栈,JVM在执行过程当中,每执行一个方法,都会为方法在当前栈中增加一个栈帧,每个栈帧的信息与具体实现相关,但一般会由3部分组成:变量区,方法参数和本地变量会放入这个位置,大小是固定的,在进行方法时会先分配好,在类定义中,会由max local来指定这块区的大小;方法信息区,会包括当前类常量池的入口地址等信息,这块大小也是固定的;操作栈,与Intel体系架构中的运算使用寄存器来进行不一样,JVM的字节码的方法调用、运算等需要的参数,都是通过操作栈来传递的。在类定义中,会由max stack指定最大的操作栈。关于Java栈的更详细描述参见《Java 栈内存介绍 》

        本地方法栈:对本地方法的调用,并不会使用Java栈而是使用本地方法栈,本地方法栈的组成取决于所使用的平台和操作系统.

        PC寄存器/程序计数器:
对于每个执行线程会分配一个PC寄存器,寄存器中存放当前字节码的执行位置 


栈帧

        在调用函数的时候,我们会为这个函数在java虚拟机栈中开辟一块内存,叫做栈帧。 


栈的使用

1.入栈 和 出栈的顺序

中缀 和 后缀 表达式的表现形式

中缀表达式:最常见的表达式,就是我们平常使用的: a + b、a - c、a * b、a/b。
还可以加括号 (5 + 4) * 3 - 2。


后缀表达式:就拿中缀的式子【(5 + 4) * 3 - 2】来说,它的后缀表达式为 54+ 3 * 2 -
再来看一个 a + b * c ,这个中缀表达式转换成 后缀表达式为 abc*+ 

中缀转后缀 和 中缀转前缀 的方法

实战题
150. 逆波兰表达式求值 - 力扣(LeetCode)

解题思维

借助栈和循环,思维是这样的:

  1. 如果 i 下标的元素 是 数字,直接入栈。
  2. 如果 i 下标的元素 是 运算符时,出栈两个数字 进行运算,再将其计算结果入栈。
  3. 以此类推!

代码阶段:

1、怎么 new 一个 Stack

进入 栈Stack 类,按下 alt + 7

2、Stack 的功能

3、另外,栈继承了 Vector 类,Vectoc 类,又实现了一些接口功能。那么,就意味着:Stack 可以调用的方法不止本身的那些功能,还可以调用 它 所继承的类 和 接口 的 一些方法 和 属性。

Ctrl + 左键 进入 Vector

简略图

代码
class Solution {
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();
        for(int i = 0; i <tokens.length;i++){
            String str = tokens[i];//获取下标为 i 字符串元素
            if(isOperator(str)){// 如果 str 是运算符 为 true,否则为false
                int num2 = stack.pop();// 获取 栈顶 的 两个数字数据(出栈)
                int num1 = stack.pop();
                switch(str){// 判断 str 具体是 哪一个字符串,就执行对应的运算,并将其结果入栈
                    case "+":
                        stack.push(num1 + num2);
                        break;
                    case "-":
                        stack.push(num1 - num2);
                        break;
                    case "*":
                        stack.push(num1 * num2);
                        break;
                    case "/":
                        stack.push(num1 / num2);
                        break;
                }
            }else{// 将 数字字符转换成 整形数据 存入 栈中
                stack.push(Integer.parseInt(str));
            }
        }
        return stack.pop();// 返回/出栈   最终存入栈中的结果
    }
    public boolean isOperator(String s){// 判断 str 是运算符 返回 true;否则,返回 false
        if(s.equals("+") || s.equals("-")|| s.equals("*") || s.equals("/")){
            return true;
        }
        return false;
    }
}

实战题 

栈的压入、弹出序列_牛客题霸_牛客网 (nowcoder.com)

解题思维 - 双指针遍历

定义两个整形指针 p1 和 p2【初始值为0】,分别指向 输入的两个数组 pushA 和 popA

我们想法:

将 i 指向的元素入栈、入栈后,i++。直到 栈顶的数据 与 出栈序列 j 的指向相等,我们将其出栈。
然后, j++,开始判断下一个。
如果 栈顶的数据 与 出栈序列 j 指向的元素不相等。则继续 将 i 指向的数据入栈。直到 栈顶的数据 与 出栈序列 j 的指向相等,我们将其出栈。
重复此操作,直到 i 遍历完 pushA数组。
如果: 入栈数组 出栈效果 可以达到 出栈数组的效果,栈里面应该是为 空的。

import java.util.*;

public class Solution {
    public boolean IsPopOrder(int [] pushA,int [] popA) {
      Stack<Integer> stack = new Stack<>();
        for(int i = 0, j = 0;i < pushA.length;i++){
            stack.push(pushA[i]);
            while(!stack.isEmpty() && j < popA.length && stack.peek() == popA[j]){
                j++;
                stack.pop();
            }
        }
        return stack.isEmpty();

    }
}

模拟实现栈 - 数组实现

参考栈的源码,观察它所具有的方法 和 属性。

由此,得出结论:Stack 底层 也可以说是一个数组。

然后,就是数组的入栈了。
但是!我们需要注意:
     数组的容量假设为5。但是,我该怎么知道 栈内 存储数据个数。
那么,我们就肯定需要一个 usedSize【初始值为0】 来记录 存入的数据个数。存入一个(usedSize++).
而且! 我们还可以通过它 来进行 入栈。
这么来想:当还没有存入 数据时,usedSize 为 0。此时,我们要入栈一个数据,我们 直接 elements[usedSize] = data。 然后,usedSize++:【细品一下:在将原先的数据“入栈”到对应的位置后,usedSize再++。是不是记录了入栈的元素个数,又为下一次入栈的数据,指定好了位置】
 

之后,就是构造一个 Stack 的 构造方法。【将底层数组初始容量定为5】

实现栈的功能
1、 push 入栈 功能

pop 出栈功能

注意!此时,我们的栈是利用数组来实现了。

peek 方法

peek 方法只是获取栈顶元素,并不涉及删除。所以,usedSize 就不用再减减了

模拟 Stack(栈) 总程序附图

模拟实现栈 - 链表实现

单向链表 + 头插
class Node{
    int val;
    Node next;
    public Node(){}

    public Node(int val,Node node){
        this.val = val;
        this.next = node;
    }

}

public class MyStackLinked {
    Node head;// 头节点 : 标记栈顶

    public void push(int x){
        Node node = new Node(x,head);
            this.head = node;
    }

    public int pop(){
        if(isEmpty()){
            throw  new RuntimeException("栈为空");
        }
        int oldVal = this.head.val;
        head = head.next;
        return oldVal;
    }
    public boolean isEmpty(){
        return this.head == null;
    }

    public int peek(){
        if(isEmpty()){
            throw  new RuntimeException("栈为空");
        }
        return head.val;
    }
}

双向链表 + 尾插
class DoubleNode{
    int val;
//    DoubleNode next;// next 用不到,加不加都不影响效果
    DoubleNode prev;
    public DoubleNode(int val,DoubleNode prev){
        this.val =val;
        this.prev = prev;
    }
}

public class MyStackDoubleLinked {
//    DoubleNode head; 头节点 用不到
    DoubleNode tail;

    public void push(int x){
        if(tail == null){
            tail = new DoubleNode(x,tail);
        }else{
            DoubleNode node = new DoubleNode(x,tail);
//            tail.next = node; 如果你还是加 next,这一步我给你准备好了
            tail = node;
        }
    }

    public int pop(){
        if(isEmpty()){
            throw new RuntimeException(" 栈为空 ");
        }
        int oldVal = tail.val;
        tail = tail.prev;
        return oldVal;
    }
    public  boolean isEmpty(){
        return tail == null;
    }

    public int peek(){
        if(isEmpty()){
            throw new RuntimeException(" 栈为空 ");
        }
        return tail.val;
    }
}

栈的面试题

LeetCode - 20. 有效的括号

解题思维
这道题跟前面 逆序波兰表达式,做法思维是相同的。
遍历 字符串,当我们 遇到 ’ ( ’ 、’ [ ‘、’ { ’ 的 时候,我们就将它入栈。
随后,继续便来字符串。直到遇到 ’ ) ‘、’ ] ‘、’ } '。我们就去判断栈顶的数据 是不是 它们对应的做符号。如果是:出栈(将栈顶数据出栈,表示这对括号有效)。反之,如果不是:直接返回 false。【因为这个乱入的符号导致整个字符串的符号无法匹配】。再或者:遍历完了字符串,栈里面还存储的左符号,没有右符号匹配了,直接返回false;
之所以说与逆波兰表达式那题相同,就是遇到了特定字符需要进行相应的操作,返回值还是需要根据 栈的内部情况决定【空为ture,否则为 false(为 true,说明字符串里面的括号都是有效的)】
 

代码如下
class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for(int i = 0;i < s.length();i++){
            char ch = s.charAt(i);
            if(ch == '(' || ch == '[' || ch == '{'){
                stack.push(ch);
            }else{
                if(stack.isEmpty()){
                    return false;
                }
                char top = stack.peek();
                if(top == '(' && ch == ')'){
                    stack.pop();
                }else if(top == '[' && ch == ']'){
                    stack.pop();
                }else if(top == '{' && ch == '}'){
                    stack.pop();
                }else{
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }
}
155. 最小栈

这题大概是这么个意思:要求我们实现一个栈,能以时间复杂度O(1),找到栈中最小的元素。
其中 top ,其实就是 peek方法:查看栈顶数据。

解题思维

首先,我们需要明白一个问题:能以时间复杂度O(1),找到栈中最小的元素是不可能的。
因为需要再遍历数组一遍,才能确定最小值。时间复杂度达到O(N)…
那么,既然一个不行,那我两个!
来看我怎么做:

代码如下
class MinStack {
    private Stack<Integer> stack;
    private Stack<Integer> stackMin;
    public MinStack() {
        stack = new Stack<>();
        stackMin = new Stack<>();
    }
    //入栈
    public void push(int val) {
        stack.push(val);
        if(stackMin.isEmpty()){
            stackMin.push(val);
        }else{
            if(val <= stackMin.peek()){
                stackMin.push(val);
            }
        }

    }
    // 出栈
    public void pop() {
        if(!stack.isEmpty()){
            int val = stack.pop();
            if(val == stackMin.peek()){
                stackMin.pop();
            }
        }

    }
    // 等价于 peek方法
    public int top() {
        return stack.peek();

    }
    // 和获取 目前 Stack 栈中最小值
    public int getMin() {
        return stackMin.peek();
    }
}

队列

普通队列【queue】:只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先进先出FIFO(First In First Out) 入队列:进行插入操作的一端称为队尾(Tail/Rear) 出队列:进行删除操作的一端称为队头。
双端队列【deque】: 出队 和 入队,则没有像普通队列那样的限制。 无论是 队头 还是 队尾,都可以出入队。

看过上面的图,我们 可以知道 双向队列,可以用来实现 栈 。因为队尾队头都可以入出对,也就是说肯定会有一个 标识 队头 和 队尾的属性,我们就可以通过这个来用队列 实现 栈 。(这个deque 会有相对应的功能 可以用来实现 栈,可以参考下方的 deque 功能展示)
再来看看 集合框架背后的数据结构图。

当然也可以 直接通过 LinkedList 实现类 来 new LinkedList 对象。因为 LInkedList 类 实现了 deque 和 queue。再加上它自身的功能,说明LinkedList 的功能 只会 更多。

queue【队列】 和 deque【双端队列】所具有的功能

普通队列 queue 基础功能 分析 与 区别
add 和 offer 入栈方法的区别

peek 和 element 返回队顶数据 方法的区别

poll 和 remove 出队方法的区别

双端队列【deque】的基础功能演示

功能细节

讲这个是为了表明一个点:如果只是一些简单的方法,可以通过接口去引用。不用直接去new 实现类
在这里插入图片描述

总结

特殊值返回值 和 异常,跟上的普通队列返回值是一样的。
返回特殊值的方法,都是最常用的方法。

总结

对于 LinkedList 来说:它不仅可以当作普通的队列、双端队列、双向链表,栈 来使用。
对于 LinkedList 来说,它有一项比较尴尬的功能 addIndex 给 某个下标添加一个元素

要知道,链表是没有下标的!
由此引申出 一个问题 :
顺序表 和 链表 的区别是什么?
ArrrayList 和 LinkedList 的区别是什么?(这个问的最多)
解答:
1、从共性出发:增删查改
【ArrrayList支持 随机 访问,LinkedList不支持。因为链表没有下标】
【 LinkedList 删除和添加元素 时间复杂 ArrrayList 要比 低,因为 不需要像顺序表做整体的位移。】
2、 从内存的逻辑出发
【ArrrayList 是一个顺序存储(底层为一个数组) ,内存 在 理论 和 物理上 都是 连续的】
【 LinkedList 是一个链式存储(由一个个节点连接而成),内存在理论上是连续的,在物理上不是连续的(因为不可能说每次new的节点,都是和原来的节点是紧挨着的!因为 new 对象,它是哪里有位置,它new哪里,没有规律的)】

模拟实现 普通队列(Queue) - 单链表实现。

需要考虑的一点就是 哪边当队头,哪边当队尾?

当然,你可以用双向链表来实现,那就很简单了!!! 所以我们这里才使用 单向链表实现

代码如下
public class TestDemo {
    public static void main(String[] args) {
        MyQueue myQueue = new MyQueue();
        myQueue.offer(1);// 入队
        myQueue.offer(2);
        // 出队
        try{
            System.out.println(myQueue.poll().val);// 1
        }catch (NullPointerException e){
            e.printStackTrace();
            System.out.println("队列为空 【poll】");
        }
        // 返回头数据
        try {
            System.out.println(myQueue.peek().val);// 2
        }catch (NullPointerException e){
            e.printStackTrace();
            System.out.println("队列为空【peek】");
        }
    }
}

附图

主程序2

队列实现
public class MyQueue {
    Node head;// 队头
    Node tail;// 队尾

    public void offer(int x){
        if(head == null){// 第一次入队
            head = new Node(x);
            tail = head;
        }else{// 从队尾 入队
            tail.next =  new Node(x);
            this.tail = this.tail.next;
        }
    }

    public Node poll(){
        if(head == null){// 队列为 空,返回 null
            return head;
        }
        Node node = head;
        this.head = head.next;
        return node;// 返回删除的头
    }

    public Node peek(){
        return head;
    }

}

循环队列

实际中我们有时还会使用一种队列 叫 循环队列。如操作系统课程讲解生产者消费者模型时可以就会使用循环队列。
环形队列通常使用数组实现。

队列面试题

LeetCode - 622. 设计循环队列
解题思维 与 步骤 - 使用第三种判断循环队列的方法

代码如下
class MyCircularQueue {
    int[] elements;
    int front;
    int rear;
    public MyCircularQueue(int k) {
        elements = new int[k+ 1];
    }
    
    public boolean enQueue(int value) {
        if(isFull()){
            return false;
        }
        elements[rear] = value;
        rear = (rear+1)%elements.length;
        return true;
    }
    
    public boolean deQueue() {
        if(isEmpty()){
            return false;
        }
        front = (front+1)%elements.length;
        return true;
    }
    
    public int Front() {
        if(isEmpty()){
            return -1;
        }
        return elements[front];
    }
    
    public int Rear() {
        if(isEmpty()){
            return -1;
        }
        int index = 0;
        if(rear == 0){
            index = elements.length - 1;
        }else{
            index = rear - 1;
        }
        return elements[index];
    }
    
    public boolean isEmpty() {
        return front == rear;
    }
    
    public boolean isFull() {
        if((rear+1)%elements.length == front){
            return true;
        }
        return false;
    }
}
LeetCode - 232. 用栈实现队列
解题思维

很简单, 栈 的特性是:先进后出。也就是说第一个入栈的数据,将是最后一个出栈,
我们利用两个栈来实现这题。

代码如下
class MyQueue {
    Stack<Integer> stack1;
    Stack<Integer> stack2;
    public MyQueue() {
        stack1 = new Stack<>();
        stack2 = new Stack<>();
    }
    
    public void push(int x) {
        stack1.push(x);
    }
    
    public int pop() {
        if(stack2.isEmpty()){
            while(!stack1.isEmpty()){
                stack2.push(stack1.pop());
            }
        }
        return stack2.pop();
    }
    
    public int peek() {
    // 防止 别人一开始 就调用 peek,所以 peek 也需要 写 stack1 导入 stack2 的程序
        if(stack2.isEmpty()){
            while(!stack1.isEmpty()){
                stack2.push(stack1.pop());
            }
        }
        return stack2.peek();
    }
    
    public boolean empty() {// 如果模拟的队列 将全部数据出队,那么 stack1 和 stack2 都为空
        return stack1.isEmpty() && stack2.isEmpty();
    }
}