【数据结构基础】之栈与队列介绍，生动形象，通俗易懂，算法入门必看

前言

本文为 数据结构基础【栈与队列】 相关知识，下边将对栈的概念与实现，队列的概念与实现，循环队列的概念与实现，双端队列的概念与实现，Java中栈和队列等进行详尽介绍~

📌博主主页：´Code_Wang的主页
👉Java全栈学习路线可参考：【Java全栈学习路线】最全的Java学习路线及知识清单，Java自学方向指引，内含最全Java全栈学习技术清单~
👉算法刷题路线可参考：算法刷题路线总结与相关资料分享，内含最详尽的算法刷题路线指南及相关资料分享~

---

目录

一、栈

1.栈的概念

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

2.栈的实现

• （1）利用顺序表实现，即使用尾插 + 尾删的方式实现
• （2）利用链表实现，则头尾皆可

相对来说，顺序表的实现上要更为简单一些，所以我们优先用顺序表实现栈。

// 基于数组实现链表
public class Stack<E> {
    private E[] elementData; // 栈中的元素
    private int size; // 当前栈中元素个数
 
    public Stack() {
        elementData = (E[]) new Object[10]; // 默认长度为10
    }
 
    public Stack(int initCap) {
        elementData = (E[]) new Object[initCap]; // 初始长度
    }
 
    // 入栈
    public void push(E value) {
        // 扩容
        if(size == elementData.length) {
            int oldLength = elementData.length;
            int newLength = oldLength << 1;
            elementData = Arrays.copyOf(elementData, newLength);
        }
        // 在数组尾部添加元素
        elementData[size++] = value;
    }
 
    // 出栈,返回原来的栈顶元素
    public E pop () {
        if(getSize() == 0) {
            throw new NoSuchElementException("栈中没有元素！");
        }
        // 得到原来的栈顶元素位置
        E oldVaule = elementData[size - 1];
        size--;
        elementData[size] = null;
        return oldVaule;
    }
 
    // 查看栈顶元素
    public E peek() {
        if(getSize() == 0) {
            throw new NoSuchElementException("栈中没有元素！");
        }
        return elementData[size - 1];
    }
 
    // 获取当前栈的长度
    public int getSize() {
        return size;
    }
 
    @Override
    public String toString() {
        StringBuilder stringBuilder = new StringBuilder();
        stringBuilder.append("[");
        for (int i = 0; i < size; i++) {
            stringBuilder.append(elementData[i]);
            if(i != size - 1) {
                stringBuilder.append(",");
            }
        }
        stringBuilder.append("]");
        return stringBuilder.toString();
    }
}
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
64

二、队列

1.队列的概念

• 队列是一种仅支持在表尾进行插入操作、在表头进行删除操作的线性表，插入端称为队尾，删除端称为队首，因整体类似排队的队伍而得名。
• 队列满足先进先出的性质（FIFO)，元素入队即将新元素加在队列的尾，元素出队即将队首元素取出，它后一个作为新的队首。
  

2.队列的实现

队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低。

/**
 * 基于链表的队列实现
 */
public class LinkedQueue{
    private Node head;
    private Node tail;
    private int size;
    private class Node {
        private int data;
        private Node next;
 
        public Node(int data) {
            this.data = data;
        }
    }
 
    // 入队
    public void offer(int value) {
        Node node = new Node(value);
        if(head == null) {
            head = tail = node;
        } else {
            tail.next = node;
            tail = node;
        }
        size++;
    }
 
    // 出队(队首元素出队）
    public int poll() {
        if(size == 0) {
            throw new NoSuchElementException("对列为空！");
        } else {
            int oldValue = head.data;
            Node tempHead = head;
            head = head.next;
            tempHead.next = null;
            size--;
            return oldValue;
        }
    }
 
    // 查看队首元素
    public int peek() {
        if(size == 0) {
            throw new NoSuchElementException("对列为空！");
        }
        return head.data;
    }
 
    public String toString() {
        StringBuilder stringBuilder = new StringBuilder();
        stringBuilder.append("front[");
        Node node = head;
        while (node != null) {
            stringBuilder.append(node.data);
            if(node.next != null) {
                stringBuilder.append(",");
            }
            node = node.next;
        }
        stringBuilder.append("]tail");
        return stringBuilder.toString();
    }
}
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
64
65

3.循环队列的概念

• 实际中我们有时还会使用一种队列叫循环队列。如操作系统课程讲解生产者消费者模型时可以就会使用循环队列。环形队列通常使用数组实现。
• 在顺序队列中，当下标走到队尾后，不能再往后走插入元素，但其实数组中还有位置，这叫做“假溢出”，为了解决这个问题提高数组利用率，就出现了循环队列。
• 实现循环对列，最重要的是如何判断队列为空还是为满。
  

4.循环队列的实现

如何区分循环队列的空与满：

• 通过 size 属性记录当前队列中的元素个数
• 保留一个位置，这个位置不能存储元素。这样当队满为 front == （rear+ 1）% length，队空为 front ==rear
• front：指向循环队列的第一个元素下标，rear：指向循环队列的最后一个元素的下一个下标

/**
 * 循环队列
 */
public class LoopQueue implements IQueue {
    // 指向循环队列的最后一个元素的下一个位置
    private int tail;
    // 队首元素，指向队列中的第一个元素索引
    private int front;
    // 有效元素个数
    private int size;
    private int[] data;
 
    public LoopQueue(int k) {
        data = new int[k + 1];
    }
 
    // 判断队列是否已满
    public boolean isFull() {
        if ((tail + 1) % data.length == front) {
            return true;
        }
        return false;
    }
 
    // 判断队列是否为空
    public boolean isEmpty() {
//        if (front == tail) {
//            return true;
//        }
//        return false;
        return tail == front;
    }
 
    // 入队
    public void offer(int value) {
        if (isFull()) {
            System.err.println("队列已满！");
            return;
        } else {
            data[tail] = value;
            tail = (tail + 1) % data.length;
            size++;
        }
    }
 
    // 出队
    public int poll() {
        if (isEmpty()) {
            System.err.println("队列为空！");
            return -1;
        } else {
            int value = data[front];
            front = (front + 1) % data.length;
            size--;
            return value;
        }
    }
 
    // 查看队首元素
    public int peek() {
        if (isEmpty()) {
            System.err.println("队列为空！");
            return -1;
        }
        return data[front];
    }
 
    // 查看队尾元素
    public int getTail() {
        if (isEmpty()) {
            System.err.println("队列为空！");
            return -1;
        }
        // 最后一个元素的下标
        int index = tail == 0 ? data.length - 1 : tail - 1;
        return data[index];
    }
 
    // 判断有效个数
    public int getSize() {
        return size;
    }
 
    public String toString() {
        StringBuilder stringBuilder = new StringBuilder();
        stringBuilder.append("[");
        // 最后一个元素的位置
        int lastIndex = tail == 0 ? data.length - 1 : tail - 1;
        for (int i = front; i != tail; ) {
            stringBuilder.append(data[i]);
            if (i != lastIndex) {
                stringBuilder.append(",");
            }
            i = (i + 1) % data.length;
        }
        stringBuilder.append("]");
        return stringBuilder.toString();
    }
}
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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99

5.双端队列的概念

双端队列(Deque:double ended queue)就是一个两端都是结尾的队列。队列的每一端都可以插入数据项和移除数据项。相对于普通队列，双端队列的入队和出队操作在两端都可进行。

6.双端队列的实现

我们使用最常用的顺序结构来存储双端队列，为了节省空间，把它首尾相连，构成循环队列。并且规定left指向左端的第一个元素，right指向右端的下一个位置。那么队空的判断则是left== right ，队满是(left-1+MAX)%MAX== right或者(right-left+MAX)%MAX==MAX。

class ListNode {
    //数据域
    public int val;
    //指针
    public ListNode next;
    //初始化值
    public ListNode(int val) {
        this.val = val;
    }
}
 
public class Deque {
    public ListNode head;//头结点
    public ListNode last;//尾节点
 
    //在双端队列头那边添加节点变成新的头结点
    //在第一个节点处添加一个节点
    public void addFirst(int val) {
        //创建对象初始化值建立新节点
        ListNode node = new ListNode(val);
        //判断尾节点是否为空
        if (this.last == null) {
            //若为空就是头结点尾节点都是这个新创建的节点
            this.head = node;
            this.last = node;
        }
        //node成为新的头节点
        node.next = this.head;
        this.head = node;
    }
 
    //在双端队列尾那边添加节点变成新的尾节点
    //在节点的最后添加一个节点
    public void addLast(int val) {
        //创建对象初始化值建立新节点
        ListNode node = new ListNode(val);
        //判断尾节点是否为空
        if (this.last == null) {
            //若为空就是头结点尾节点都是这个新创建的节点
            this.head = node;
            this.last = node;
        }
        //node成为新的尾节点
        this.last.next = node;
        this.last = node;
    }
 
    //从头结点那边拿出Deque的一个节点
    public int offerFirst() {
        //判断头节点是否为空，如果是就输出！
        if (this.head == null) {
            System.out.println("!");
            return -1;
        }
        //如果不为空，把头结点指向的值拿出来
        int oldValue = this.head.val;
        //判断头结点尾节点是否重合，如果重合就表明双端队列为空
        if (this.head == this.last) {
            this.head = null;
            this.last = null;
        } else {
            //没有重合就接着找下一个节点变成新的头结点
            this.head = this.head.next;
        }
        return oldValue;
    }
 
    //从尾结点那边拿出Deque的一个节点
    public int offerLast() {
        //判断尾节点是否为空，如果就输出！
        if (this.last == null) {
            System.out.println("!");
            return -1;
        }
        // //如果不为空，把尾结点指向的值拿出来
        int oldValue = this.last.val;
        //判断头结点尾节点是否重合，如果重合就表明双端队列为空
        if (this.head == this.last) {
            this.last = null;
            this.head = null;
        } else {
            //遍历找到新的尾节点
            ListNode cur = this.head;
            while (cur.next != last) {
                cur = cur.next;
            }
            //把找到的最后一个节点做为尾节点
            this.last = cur;
            //尾节点.next=null
            this.last.next = null;
        }
        return oldValue;
    }
 
    //获取Deque处第一个节点的值
    public int peekFirst() {
        //判断头结点是否为空，是就输出！
        if (this.head == null) {
            System.out.println("!");
            return -1;
        }
        //返回头结点值
        return this.head.val;
    }
 
    //获取Deque上最后一个节点的值
    public int peekLast() {
        //判断尾结点是否为空，是就输出！
        if (this.last == null) {
            System.out.println("!");
            return -1;
        }
        //返回尾结点值
        return this.last.val;
    }
 
    //Check whether the Deque is empty
    public boolean empty() {
        return this.head == null;
    }
 
    public void display(){
        ListNode cur =head;
        while (cur!=last) {
            System.out.println(cur.val);
            cur = cur.next;
        }
        System.out.println(cur.val);
    }
}
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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130

三、java 中的栈和队列

1.Java集合框架

Java集合框架图：

2.Java中的Stack（栈）

Stack的方法及说明（Stack继承了Vecter,自己独有的方法只有以下5个）：

3.Java中的Queue（队列）

Queue的方法及说明：

4.Java中的Deque（双端队列）

Deque的方法及说明：

---

后记

👉Java全栈学习路线可参考：【Java全栈学习路线】最全的Java学习路线及知识清单，Java自学方向指引，内含最全Java全栈学习技术清单~
👉算法刷题路线可参考：算法刷题路线总结与相关资料分享，内含最详尽的算法刷题路线指南及相关资料分享~