数据结构栈与队列-EW帮帮网

本节目标：

知道栈的概念及如何使用

知道队列的概念及如何使用

1.栈（Stack）

1.1 概念

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

压栈：栈的插入操作叫做进栈/压栈/入栈。入数据在栈顶。

出栈：栈的删除操作叫做出栈。出数据在栈顶。

如下图所示：

栈在实现生活中也是存在例子的，比如说羽毛球筒，当我们把羽毛球放到羽毛球筒里时，在不把它们都倒出来的情况下，我们只能放和取最后一个羽毛球。

1.2 栈的使用

Java为我们提供了Stack类，它是一个栈，它包含了栈的所有方法，并且它继承和实现了一些类和接口，如下图所示：

从上图中可以看到，Stack继承了Vector，Vector和ArrayList类似，都是动态的顺序表，不同的是Vector是线程安全的。

它的一些常用方法如下：

方法	功能
Stack()	构造一个空的栈
E push(E e)	将e入栈，并返回e
E pop()	将栈顶元素出栈并返回
E peek()	获取栈顶元素
int size()	获取栈中有效元素个数
boolean empty()	检测栈是否为空

使用演示：

import java.util.Stack;

public class Test {
    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();
        stack.push(1);
        stack.push(2);
        stack.push(3);
        System.out.println(stack.peek());
        System.out.println(stack.pop());
        System.out.println(stack.size());
        System.out.println(stack.empty());
    }
}

//运行结果：
3
3
2
false

值得一提的是，LinkedList中也有栈的方法，因此它也能够当做栈来使用！

1.3 手动实现栈

之前我们已经学习了顺序表和链表了，对于栈来说，既可以使用顺序表来实现，也可以使用链表来实现。不过用链表来实现的话，建议使用双链表，因为单链表不能直接获得尾节点和尾节点前一个节点，因此若使用尾插法入栈和尾插法出栈，时间复杂度是O(n)，但如果使用头插法入栈和头插法出栈，时间复杂度是O(1)。

这里我们使用顺序表来实现栈，也就是基于数组。

构造方法

public class MyStack {
    private int[] arr;
    private int size = 0;

    public MyStack() {
        this.arr = new int[10]; 
        //栈的初始容量为10
    }
}

入栈（压栈）

要求：将新的数据放到栈顶

思路：直接用尾插法插入数组，size++即可，不过在入栈之前需要判断栈是否满了，如果满了就需要扩容。

//入栈
    public int push(int data) {
        if (isFull()) {
            //进行扩容
            this.arr = Arrays.copyOf(this.arr,2*this.arr.length);
        }
        this.arr[this.size] = data;
        this.size++;
        return data;
    } 
    //判满
    private boolean isFull() {
        return this.size == this.arr.length;
    }

出栈

要求：将栈顶元素出栈并返回。

思路：入栈我们使用的是尾插法，此时栈顶元素在数组尾端，那么直接尾删元素即可，同时size--，不仅如此，在出栈前，需要判断栈是否为空，为空就抛出异常。

自定义异常类：

public class EmptyStackException extends RuntimeException{
    public EmptyStackException() {
    }

    public EmptyStackException(String message) {
        super(message);
    }
}

出栈方法：

//出栈
    public int pop() {
        if (empty()) {
            throw new EmptyStackException("栈为空！");
        }
        int val = this.arr[this.size - 1];
        this.size--;
        return val;
    }
    //检测栈是否为空
    public boolean empty() {
        return this.size == 0;
    }

获取栈顶元素

要求：获取栈顶的元素。

思路：直接返回数组尾端的值即可，不要忘记判断栈是否为空。

//获取栈顶元素
    public int peek() {
        if (empty()) {
            throw new EmptyStackException("栈为空！");
        }
        return this.arr[this.size - 1];
    }

获取栈中有效元素个数

//获取栈中有效元素个数
    public int size() {
        return this.size;
    }

检测栈是否为空

//检测栈是否为空
    public boolean empty() {
        return this.size == 0;
    }

到此，我们就手动实现了栈，在数据结构中，栈是属于比较简单的那一档。完整代码：

import java.util.Arrays;

public class MyStack {
    private int[] arr;
    private int size = 0;

    public MyStack() {
        this.arr = new int[10];
        //栈的初始容量为10
    }

    //入栈
    public int push(int data) {
        if (isFull()) {
            //进行扩容
            this.arr = Arrays.copyOf(this.arr,2*this.arr.length);
        }
        this.arr[this.size] = data;
        this.size++;
        return data;
    }
    //判满
    private boolean isFull() {
        return this.size == this.arr.length;
    }

    //出栈
    public int pop() {
        if (empty()) {
            throw new EmptyStackException("栈为空！");
        }
        int val = this.arr[this.size - 1];
        this.size--;
        return val;
    }
    //检测栈是否为空
    public boolean empty() {
        return this.size == 0;
    }

    //获取栈顶元素
    public int peek() {
        if (empty()) {
            throw new EmptyStackException("栈为空！");
        }
        return this.arr[this.size - 1];
    }

    //获取栈中有效元素个数
    public int size() {
        return this.size;
    }


}

1.4 概念区分

栈、虚拟机栈、栈帧有什么区别？

栈（Stack）：通用数据结构，栈是一种基于 LIFO（后进先出）原则的基础数据结构，仅允许在 “栈顶” 进行元素的插入（入栈）和删除（出栈）操作。

虚拟机栈（JVM Stack）：Java 虚拟机的内存区域，虚拟机栈是 Java 虚拟机（JVM）规范定义的一块线程私有内存区域，用于存储线程执行过程中的栈帧。

栈帧（Stack Frame）：方法调用的状态容器，栈帧是虚拟机栈中的基本元素，每个栈帧对应一个 Java 方法的调用，用于存储该方法执行时的局部变量、操作数栈、方法返回地址等信息。

2.队列（Queue）

2.1 概念

队列：：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾（Tail/Rear）出队列：进行删除操作的一端称为队头（Head/Front）。

2.2 队列的使用

在Java中，Queue是一个接口，它的底层是通过链表实现的，它实现了队列的方法，具体如下：

方法	功能
boolean offer(E e)	入队列
E poll()	出队列
peek()	获取队头元素
int size()	获取队列中有效元素个数
boolean isEmpty()	检测队列是否为空

注意：Queue是接口，在实例化时必须实例化LinkedList的对象，因为LinkedList实现了Queue接口。

使用演示：

import java.util.LinkedList;
import java.util.Queue;

public class Test {
    public static void main(String[] args) {
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(1);
        queue.offer(2);
        queue.offer(3);
        System.out.println("队列的元素个数：");
        System.out.println(queue.size());
        System.out.println("=============");
        System.out.println(queue.peek());
        System.out.println(queue.poll());
        System.out.println("队列的元素个数：");
        System.out.println(queue.size());
        System.out.println("=============");
        System.out.println(queue.isEmpty());
    }
}

//运行结果
队列的元素个数：
3
=============
1
1
队列的元素个数：
2
=============
false

2.3 手动实现队列

前面我们实现栈的时候说过，栈可以通过顺序结构和链式结构实现，那么队列呢？队列也是如此，既可以通过顺序结构实现，也可以通过链式结构实现。如果通过顺序结构实现，建议使用循环队列的方式，因此使用普通的数组去实现，入队列和出队列这两个操作总有一个时间复杂度是O(n)。如果通过链式结构实现，建议使用双链表，因为双链表的节点可以很轻松的找到某个节点的前驱和后驱，而使用单链表实现的话，需要加上一个标记尾节点的引用，并且出队列只能使用头删的方式，入队列采用尾插的方式，不能从头节点入队，因为这样的话出队列么办法直接找到最后一个节点的前驱。

这里我们使用双链表去实现队列。

创建双链表的节点

关于创建节点，这里采用静态内部类的方式：

public class MyQueue {
    static class ListNode{
        int val;
        ListNode prev; //前驱
        ListNode next; //后驱

        public ListNode(int val) {
            this.val = val;
        }
    }

    private ListNode head;//头节点
    private ListNode last;//尾节点
    private int size = 0; 

}

入队列

要求：实现队列的入队列操作，在一端插入新数据。

思路：采用尾插法，将新节点插入链表尾端，不过这里需要分两种情况：1.一开始链表就为空；2.一开始链表不为空。

//入队列
    public void offer(int data) {
        ListNode cur = new ListNode(data);
        if (this.head == null) {
            this.head = this.last = cur;
        }else {
            this.last.next = cur;
            cur.prev = this.last;
            this.last = cur;
        }
        this.size++;
    }

出队列

要求：实现队列的出队列操作，在另一端删除数据。

思路：在入队列操作中我们采取尾插的方式，那么出队列的话，应该要采取头删的操作。不过这里也分两种情况：1.链表中仅有一个节点；2.链表中有多个节点，但是在进行头删操作前，应当先对链表进行判断为不为空。

如果链表为空，就抛出异常，自定义异常类：

public class EmptyQueueException extends RuntimeException{
    public EmptyQueueException() {
    }

    public EmptyQueueException(String message) {
        super(message);
    }
}

出队列方法：

//出队列
    public int poll() {
        if (isEmpty()) {
            throw new EmptyQueueException("队列为空！");
        }
        int val = this.head.val;
        this.head = this.head.next;
        if (this.head == null) {
            this.last = null;
        }else {
            this.head.prev = null;
        }
        this.size--;
        return val;
    }
    //检测队列是否为空
    public boolean isEmpty() {
        return this.head == null;
    }

获取队头元素

//获取队头元素
    public int peek() {
        if (isEmpty()) {
            throw new EmptyQueueException("队列为空！");
        }
        return this.head.val;
    }

获取队列中有效元素个数

//获取队列中有效元素个数
    public int size() {
        return this.size;
    }

检测队列是否为空

//检测队列是否为空
    public boolean isEmpty() {
        return this.head == null;
    }

到此，我们就成功的手动实现了一个队列。完整代码如下：

public class MyQueue {
    static class ListNode{
        int val;
        ListNode prev; //前驱
        ListNode next; //后驱

        public ListNode(int val) {
            this.val = val;
        }
    }

    private ListNode head;//头节点
    private ListNode last;//尾节点
    private int size = 0;

    //入队列
    public void offer(int data) {
        ListNode cur = new ListNode(data);
        if (this.head == null) {
            this.head = this.last = cur;
        }else {
            this.last.next = cur;
            cur.prev = this.last;
            this.last = cur;
        }
        this.size++;
    }

    //出队列
    public int poll() {
        if (isEmpty()) {
            throw new EmptyQueueException("队列为空！");
        }
        int val = this.head.val;
        this.head = this.head.next;
        if (this.head == null) {
            this.last = null;
        }else {
            this.head.prev = null;
        }
        this.size--;
        return val;
    }
    //检测队列是否为空
    public boolean isEmpty() {
        return this.head == null;
    }

    //获取队头元素
    public int peek() {
        if (isEmpty()) {
            throw new EmptyQueueException("队列为空！");
        }
        return this.head.val;
    }

    //获取队列中有效元素个数
    public int size() {
        return this.size;
    }
}

2.4 循环队列

我们刚才说过队列也可以用顺序结构实现，并且建议使用循环队列，循环队列通常使用数组实现，可以把它现象成一个环形的数组，如下图所示：

一开始队列头和队列尾在同一位置，当入队列操作时，队列尾移动到下一个位置，队列头不动，当出队列操作时，队列尾不动，队列头移动到下一个位置。

不过问题是：我们怎么知道队列空和满呢？

对于空的情况：主要队列头和队列尾相遇，就是空的。

对于满的情况：我们有三种做法：1.定义一个size用于储存队列元素的个数；2.添加标记，定义一个boolean类型变量，当队列头和队列尾相遇并且这个标记发生改变了，就说明满了；3.浪费一个空间，当队列尾的下一个位置如果是队列头，那么就说明满了。

如何使用这三种方法实现循环队列请前往这篇文章：

数据结构实现循环队列的三种方法-CSDN博客

数组下标循环的小技巧

1.下标往后移动（正向循环）

公式：index = (index + offset) % array.length

说明：从当前下标向后移动 offset 步，超出数组长度时自动从头部开始。

举例：

2.下标往前移动（反向循环）

公式：index = (index + array.length - offset) % array.length

解释：从当前下标向前移动 offset 步，超出数组头部时自动从尾部开始。

举例：

2.5 双端队列（Deque）

双端队列（Deque）是指允许两端都可以进行入队和出对操作的队列，deque 是 “double ended queue” 的简称。简单来说就是元素可以从队头出队和入队，也可以从队尾出队和入队。

使用演示：

import java.util.Deque;
import java.util.LinkedList;

public class Test {
    public static void main(String[] args) {
        Deque<Integer> deque = new LinkedList<>();
        //队头入队和出队
        deque.offerFirst(1);
        deque.offerFirst(2);
        System.out.println(deque.pollFirst());
        System.out.println("===============");
        //队尾入队和出队
        deque.offerLast(1);
        deque.offerLast(2);
        System.out.println(deque.pollLast());
    }
}

//运行结果
2
===============
2

在实际工程中，使用Deque接口是比较多的，栈和队列均可以使用该接口。

Deque stack = new ArrayDeque<>(); //双端队列的线性实现

Deque queue = new LinkedList<>();//双端队列的链式实现

到此，栈和队列的内容完结！感谢各位的阅读，如有错误，还请指出，谢谢！

数据结构栈与队列

1.栈（Stack）

1.1 概念

1.2 栈的使用

1.3 手动实现栈

构造方法

入栈（压栈）

出栈

获取栈顶元素

获取栈中有效元素个数

检测栈是否为空

1.4 概念区分

2.队列（Queue）

2.1 概念

2.2 队列的使用

2.3 手动实现队列

创建双链表的节点

入队列

出队列

获取队头元素

获取队列中有效元素个数

检测队列是否为空

2.4 循环队列

2.5 双端队列（Deque）

网站公告

今日签到

热门文章

最新发布

数据结构 栈与队列

1.栈（Stack）

1.1 概念

1.2 栈的使用

1.3 手动实现栈

构造方法

入栈（压栈）

出栈

获取栈顶元素

获取栈中有效元素个数

检测栈是否为空

1.4 概念区分

2.队列（Queue）

2.1 概念

2.2 队列的使用

2.3 手动实现队列

创建双链表的节点

入队列

出队列

获取队头元素

获取队列中有效元素个数

检测队列是否为空

2.4 循环队列

2.5 双端队列（Deque）

网站公告

今日签到

热门文章

最新发布

数据结构栈与队列