leetcode栈与队列（上）之理论篇（java实现）

前言

学习数据结构，需要先搞清楚自己语言是怎么实现的。

栈与队列是每个学数据结构最早接触的数据结构，相信很多人对这两种数据结构的特性清楚地了解，但是也仅限于此。

所以本文以leetcode习题为例，深入探索这两种数据结构，以及如何灵活运用这两种数据结构的思想，为下篇leetcode栈与队列实战篇（链接）铺垫。

如果理论知识已经烂熟于心，可以直接看实战篇： leetcode栈与队列（下）之实战篇（java实现）

队列

先进先出

1.介绍

2.API分析

在Java中，有写好的Queue接口，他是继承自Collection接口

在我们具体实现时，一般采用LinkedList实现类作为队列的实现，LinkedList类实现了Deque接口，Deque接口继承自Queue接口

（1）Queue

成员方法：

注意，‘/’分开的两种方法的区别为，给出源代码中的解释：

主要区别，拿入队为例，add(e)如果添加失败会抛出异常，而offer(e)添加失败会返回false

主要原因是，在它的继承接口会继承类中，可能会限定队列的最大容量。如果队列达到了他的最大容量，再入队就会失败。

（2）Deque

双端队列Deque的方法比较如下：

Queue 和Deque方法的比较（很多方法相同）

另外，Deque还可以作为栈使用，并且官方表示此接口优先于堆栈类使用。（见下面栈的实现）

（3）队列使用示例

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

/*
Queue 是一个接口，继承自Collection接口，需要继承类来实现，
 LinkedList实现了Deque接口，Deque继承自Queue

入队： add(),offer()
出队：remove(),poll()
获取队首元素：element(),peek()
*/
public class QueueDemo {
    public static void main(String[] args) {
        // 创建一个队列对象
        Queue<String> que = new LinkedList<>();
        
        // 入队操作
        que.offer("apple");
        que.offer("banana");
        que.offer("grape");
        que.offer("peach");
        que.offer("pear");

        System.out.println("队首元素是: " + que.peek());

        // 出队
        while (que.size() > 0) {
            // 出队的同时并获取出队元素
            String element = que.poll();
            System.out.println(element);
        }
        // 判断队列是否为空
        System.out.println(que.isEmpty());
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

栈

1.介绍

先进后出(FILO)。允许插入和删除的一端，称为栈顶，固定的一端称为栈底。所以最先插入的元素在栈底，最后插入的元素在栈顶。

如前面所介绍的，栈的实现一般由Stack和Deque 来实现（而Java中更推荐Deque）

2.Stack

Java中有给我们封装好Stack类,首先是类的结构层次

主要成员方法：

栈的使用示例

public class StackDemo {
    public static void main(String[] args) {
        // 1. Initialize a stack.
        Stack<Integer> s = new Stack<>();

        // 2. Push new element.
        s.push(5);
        s.push(13);
        s.push(8);
        s.push(6);

        // 3. Check if stack is empty.
        if (s.empty()) {
            System.out.println("Stack is empty!");
            return;
        }

        // 4. Pop an element.
        s.pop();

        // 5. Get the top element.
        System.out.println("The top element is: " + s.peek());

        // 6. Get the size of the stack.
        System.out.println("The size is: " + s.size());
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

3.Deque

如上面说的，Java推荐Deque作为栈的实现。当deque用作堆栈时，从deque的开头推送和弹出元素。堆栈方法等同于下表所示的Deque方法：

具体示例如下：

LinkedList

如上面所说，Deque既可以当作栈，也可以当作队列，而LinkedList作为Deque的一个实现类，已经被普遍使用

上面已经给了两个示例（分别实现了栈和队列），现在总结一下LinkedList的中的常用方法：

1.添加元素

即，入栈，入队列等

boolean add(E e)：在链表后添加一个元素，如果成功，返回true，否则返回false；
void addFirst(E e)：在链表头部插入一个元素；
void addLast(E e)：在链表尾部添加一个元素；
void add(int index, E element)：在指定位置插入一个元素。

boolean offer(E e)：在链表尾部插入一个元素；
boolean offerFirst(E e)：与addFirst一样，实际上它就是addFirst；
boolean offerLast(E e)：与addLast一样，实际上它就是addLast；

2.删除元素

即出栈，出队列等

remove()；移除链表中第一个元素；
boolean remove(Object o)：移除链表中指定的元素；
remove(int index)：移除链表中指定位置的元素；
removeFirst()：移除链表中第一个元素，与remove类似；
removeLast()：移除链表中最后一个元素；
boolean removeFirstOccurrence(Object o)：移除链表中第一次出现所在位置的元素；
boolean removeLastOccurrence(Object o)：移除链表中最后一次出现所在位置的元素；

3.获取元素

即获取栈顶，队首（队尾）元素

get(int index)：按照下标获取元素；
getFirst()：获取第一个元素；
getLast()：获取最后一个元素；

peek()：获取第一个元素，但是不移除；
peekFirst()：获取第一个元素，但是不移除；
peekLast()：获取最后一个元素，但是不移除；

优先队列

优先队列其实就是个二叉堆，因为优先队列对外接口只是从队头取元素，从队尾添加元素，再无其他取元素的方式。顾名思义，出队顺序是按照优先级来的。

堆是一棵完全二叉树，树中每个结点的值都不小于（或不大于）其左右孩子的值。

分为大顶堆和小顶堆

• 大顶堆 Max Heap」，任意结点的值 大于 其子结点的值；
• 小顶堆 Min Heap」，任意结点的值 小于 其子结点的值

Java中实现了PriorityQueue，默认是最小堆，如果要把最小堆变成最大堆需要传入自己的比较器

代码示例：

public static void main(String[] args) {
        /* 初始化堆 */
        // 初始化小顶堆
        Queue<Integer> minHeap = new PriorityQueue<>();
        // 初始化大顶堆（使用 lambda 表达式修改 Comparator 即可）
        Queue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);

        /* 元素入堆 */
        maxHeap.offer(1);
        maxHeap.offer(3);
        maxHeap.offer(2);
        maxHeap.offer(5);
        maxHeap.offer(4);

        int peek = maxHeap.peek(); // 5
        int size = maxHeap.size();

        /* 堆顶元素出堆 */
        // 出堆元素会形成一个从大到小的序列
        while(!maxHeap.isEmpty())
        {
            System.out.print(maxHeap.poll()+" ");

        }

        System.out.println();

        /*--------------------------*/

        /* 输入列表并建堆 */
        minHeap = new PriorityQueue<>(Arrays.asList(1, 3, 2, 5, 4,8,6));
        while(!minHeap.isEmpty())
        {
            System.out.print(minHeap.poll()+" ");
        }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

输出：

5 4 3 2 1
1 2 3 4 5 6 8

如果是其他类型的也可以入队列，并按照自己设定的排序

// 新建一个顾客类，属性是名字和级别，排序根据level来定
public class Customer implements Comparable<Customer> {
    private String name;
    private int level;

    public Customer(String name, int level) {
        this.name = name;
        this.level = level;
    }
    // 注意这里重写compareTo方法
    public int compareTo(Customer c)
   {
       return c.level-this.level;
   }

    @Override
    public String toString() {
        return "Customer{" +
                "name='" + name + '\'' +
                ", level=" + level +
                '}';
    }
}
public class Main {
    public static void main(String[] args) {
        Queue<Customer> ps = new PriorityQueue<>();
        ps.offer(new Customer("小红",3));
        ps.offer(new Customer("小李",5));
        ps.offer(new Customer("小王",2));
        ps.offer(new Customer("小张",6));

        while(!ps.isEmpty())
        {
            System.out.println(ps.poll());
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

输出：

Customer{name=‘小张’, level=6}
Customer{name=‘小李’, level=5}
Customer{name=‘小红’, level=3}
Customer{name=‘小王’, level=2}

参考链接：
https://leetcode.cn/leetbook/detail/queue-stack/
https://blog.csdn.net/u013970897/article/details/106877472