Java Stack，Queue，循环队列和双端队列的原理/性质 + 代码模拟实现_java双端队列

---

前言

本文介绍了十分有趣的两种结构栈和队列，有时这两种结构对解决问题有奇效，所以废话不多说，直接上干货。

---

一、栈(Stack)

1.栈的概念

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

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

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

---

栈可以理解成一个一个死胡同，只有最后进来的人，先出去，里面的人才能出来。
所以栈这一数据结构，先进的数据晚出，后进的数据先出。。

• 最先进入的人，即为栈底元素，最后出。
• 最后进入的人，即为栈顶元素，最先出。

---

2.栈的使用

---

    public static void main(String[] args) {
		Deque<Integer> stack1 = new ArrayDeque<>();
    	//Deque<Integer> stack1 = new LinkedList<>();
        stack1.push(12);//最先进入，12为栈底元素
        stack1.push(19);
        stack1.push(26);
        stack1.push(34);//最后进入，34为栈顶元素
        System.out.println(stack1.size());// 获取栈中有效元素个数---> 4
        System.out.println(stack1.peek());// 获取栈顶元素---> 34
        stack1.pop();//将栈顶元素34出栈，栈顶元素更新为26
        System.out.println(stack1.pop());//将栈顶元素26，栈顶元素更新为19
        System.out.println(stack1.empty());//栈空返回true，不空返回false
    }
1
2
3
4
5
6
7
8
9
10
11
12
13

Stack类快要过时了，所以用使用双端队列这个接口，底层有顺序表实现的双端队，也有链表实现的。该接口中提供了Stack的方法。

---

3.栈的模拟实现

栈的实现采用顺序结构比较好
用size控制可访问范围，效率高，
链式存储，如果要访问栈顶元素，或删除栈顶元素，都要遍历整个链表。

---

public class MyStack {

    int[] array;
    int size = 0;

    //初始化
    public MyStack(){
        array = new int[10];
    }

    //压栈
    public int push(int e){
        ensureCapacity();//检查是否需要扩容
        array[size++] = e;//将数据压入栈中，更新size
        return e;
    }

    //扩容
    public void ensureCapacity(){
        if(size == array.length) {
            array = Arrays.copyOf(array,array.length*2);
        }
    }

    //出栈
    public int pop() {
        examine();//检查栈中是否有元素
        return array[--size];//出栈栈顶元素，并更新size
    }

    //检查栈中是否有数据
    public void examine() {
        if(size == 0) {
            throw new RuntimeException("栈为空，无法获取栈顶元素");
        }
    }

    //查看栈顶数据
    public int peek() {
        examine();//检查栈中是否有元素
        int ret = array[--size];
        size++;
        return ret;
    }

    //返回数据个数
    public int size(){
        return 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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

---

二、队列(Queue)

1.队列的概念

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

---

队列可以理解为，在学校食堂，排队买饭，
最先进入队伍的人称为队头，最后进入队伍的人称为队尾

• 先进的人先买到饭，即队头元素先出去
• 后进的人后买到饭，即队尾元素后出去

---

2.队列的使用

在Java中，Queue是个接口，底层是通过链表实现的，在实例化时必须实例化LinkedList的对象，因为LinkedList实现了Queue接口。

---

---

    public static void main(String[] args) {

    	Deque<Integer> queue1 = new ArrayDeque<>();
    	Deque<Integer> queue2 = new LinkedList<>(); 
        queue.offer(15);//最先入队，即为队头元素
        queue.offer(36);
        queue.offer(69);
        queue.offer(23);
        queue.offer(48);
        queue.offer(95);//最后入队，即为队尾元素
        System.out.println(queue.poll());//队头元素出队，更新队头元素为36
        System.out.println(queue.peek());//获取队头元素36
        System.out.println(queue.size());//获取队列中有效元素个数
        System.out.println(queue.isEmpty());//队列为空返回true，不为空返回false
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

因为Queue只能用链表实现，所以在这里也使用双端队列这个接口，底层有顺序表实现的双端队列，也有链表实现的。该接口中提供了Queue的方法。

---

3.队列的模拟实现

队列的实现采用链式结构比较好
如果采用顺序结构，那么出队时，就要挪动数组，效率较低

public class MyQueue {
    //创建一个内部类，当作链表结点
    class Node {
        public int val;
        public Node next;

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

    }


    public Node head;//队头
    public Node last;//队尾
    public int size;//元素个数


    //入队
    public void offer(int val) {
        Node node = new Node(val);//创造结点
        if(last == null) {
            head = last = node;//如果last==null，证明队列中没有元素
        } else {
            node.next = last;//从队尾入
            last = node;//更新队尾
        }
        size++;//更新size
    }

    //出队
    public int poll() {
        if (head == null) {
            throw new RuntimeException("队列为空");//如果队列为空，则抛出异常
        } else {//从队头出，并更新队头
            int ret = head.val;
            head = head.next;
            size--;//更新size
            return ret;
        }
    }


    //获取队头元素
    public int peek() {
        if (head == null) {
            throw new RuntimeException("队列为空");//如果队列为空，则抛出异常
        } else {
            return head.val;
        }
    }

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

    //检测队列是否为空
    public boolean isEmpty() {
        return size == 0;//队列为空，返回true，不为空返回false
    }

}
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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

---

4.循环队列

实际中我们有时还会使用一种队列叫循环队列。
环形队列通常使用数组实现。

---

public class MyCircularQueue {
    private int[] array = new int[5];//底层数组,初始容量为10
    int size;//队列中数据个数
    int front;//队头下标
    int rear;//队尾下标

    public boolean offer(int val) {
        //首先要考虑数组是否已满
        if(isFull()) {
            //数组已满，添加失败，返回false
            return false;
        }
        array[rear++] = val;//将数据存入队尾位置，并更新队尾下标
        size++;//更新size
        return true;
    }

    private boolean isFull() {
        //牺牲一个空间用来标记，如果rear后面就是front，那么就证明数组满了
        return (rear + 1) % array.length == front%array.length;

        //或者也可以用size来判断
    }
    //可以参考下面的图片

    public int poll() {
        //检查队列中是否有数据
        if(isEmpty()) {

            throw new RuntimeException("队列为空");
        }
        size--;//更新size
        return array[front++];//更新front位置，通过控制数据访问，来达到删除目的
    }

    public boolean isEmpty() {
        //如果队尾与队列重合，那么队列就是空的
        return rear % array.length == front%array.length;
        //或者也可以用size来判断
    }
    //可以参考下面的图片
    public int getSize() {
        return 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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

---

上图证明循环队列为空

---

上图证明循环队列为满

---

5.双端队列

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

• Deque是一个接口，使用时必须创建LinkedList的对象。

---

还有一其他方法，与队列大致相同

    public static void main(String[] args) {
        Deque<Integer> deque = new LinkedList<>();
        deque.addFirst(1);//头插，即插入到队头
        deque.addLast(2);//尾插，即插入到队尾
        deque.add(3);//尾插，即插入到队尾
        deque.pollFirst();//将队头元素出队
        deque.pollLast();//将队尾元素出队
        deque.poll();//将队尾元素出队
    }
1
2
3
4
5
6
7
8
9

---

总结

以上就是今天要讲的内容，本文简单介绍了栈和队列的使用，并模拟实现了栈和队列，以及循环队列，如果本期内容对你有所帮助，帮作者点个赞吧声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/不正经/article/detail/78808