Java-数据结构-栈与队列(StackQueue)

一、栈(Stack)

① 栈的概念

栈是一种特殊的线性表，它只允许固定一端进行"插入元素"和"删除元素"的操作，这固定的一端被称作"栈顶"，对应的另一端就被称做"栈底"。

📚 栈中的元素遵循后进先出的原则

什么是后进先出呢？在生活中也有很多类似的例子，比如叠放的书本，堆积的盘子，它们都是栈在生活中的体现~

📕 压栈：指栈插入元素的操作，一般叫做进栈/压栈/入栈(操作位置是栈顶)。

📕 出栈：指栈的删除操作(操作位置是栈顶)。

② 栈的使用

栈有以下六种方法：

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

E push(E e)方法：

E pop()方法：

E peek()方法：

int size()方法：

boolean empty()方法：

③ 栈的模拟实现

栈的方法与操作与顺序表，链表等相比并不难，让我们也试着模拟实现一下~

1. 栈的基本框架

上面提到了，栈也是一种线性表，并且栈和顺序表其实是相似的，所以我们使用数组来充当栈~

接下来需要设置的东西就都和顺序表大差不差啦：

📕 创建elem数组充当栈

📕 定义usedSize代表栈内有效元素个数

📕 定义DEFAULE_SIZE为默认初始大小

📖 代码示例：

public class MyStack {private int[] elem;private int usedSize;private static final int DEFAULT_SIZE = 10;public MyStack(){elem = new int[10];}
}

📚 给大家看一眼我们要模拟实现的方法都有哪些：

2. display 方法

就没有什么多说的啦，遍历数组就好了。

📖 代码示例：

    public void display(){System.out.print("[");for(int i = 0;i < usedSize;i++){System.out.print(elem[i]);if(i != usedSize - 1){System.out.print(", ");}}System.out.println("]");}

3. size 方法

返回栈有效元素个数即可。

📖 代码示例：

    public int size(){return usedSize;}

4. push 方法

在实现push(入栈)方法之前，我们需要先实现两个辅助方法：

📕 入栈前需要先判断栈是否已满：

    public boolean full(){if(usedSize == elem.length){return true;}return false;}

📕 如果栈已满，需要自动扩容：

    public void grow(){elem = Arrays.copyOf(elem,elem.length * 2);}

等对栈是否满，以及扩容完毕后，我们将数据直接入栈即可~

📖 代码示例：

    public void push(int num){if(full()){grow();}elem[usedSize] = num;usedSize++;}

5. pop 方法

虽然是出栈，但是pop会删除元素，所以先实现两个其他的辅助方法：

📕 删除元素前，我们需要知道栈是否为空：

    public boolean empty(){if(usedSize == 0){return true;}return false;}

📕 如果栈为空，那么应该抛出异常：

    public static class StackEmptyException extends RuntimeException{public StackEmptyException() {}public StackEmptyException(String message) {super(message);}}

📖 代码示例：

    public int pop(){if(empty()){throw new StackEmptyException("栈为空异常!");}usedSize--;return elem[usedSize];}

6. peek 方法

和pop一样，不减少usedSize就好了

📖 代码示例：

    public int peek(){if(empty()){throw new StackEmptyException("栈为空异常!");}return elem[usedSize - 1];}

完整代码：

import java.util.*;
public class MyStack {public static void main(String[] args) {}private int[] elem;private int usedSize;private static final int DEFAULT_SIZE = 10;public MyStack(){elem = new int[10];}public int size(){return usedSize;}public void push(int num){if(full()){grow();}elem[usedSize] = num;usedSize++;}public int pop(){if(empty()){throw new StackEmptyException("栈为空异常!");}usedSize--;return elem[usedSize];}public int peek(){if(empty()){throw new StackEmptyException("栈为空异常!");}return elem[usedSize - 1];}public void grow(){elem = Arrays.copyOf(elem,elem.length * 2);}public boolean full(){if(usedSize == elem.length){return true;}return false;}public boolean empty(){if(usedSize == 0){return true;}return false;}public void display(){System.out.print("[");for(int i = 0;i < usedSize;i++){System.out.print(elem[i]);if(i != usedSize - 1){System.out.print(", ");}}System.out.println("]");}public static class StackEmptyException extends RuntimeException{public StackEmptyException() {}public StackEmptyException(String message) {super(message);}}
}

④ 习题：有效的括号

学习了栈之后，正好做一道小题小试牛刀吧~这题如果在学习栈之前，单纯用字符串来解决的话，不出所料应该是相当麻烦的，因为要直接对字符串整体进行计算，就要考虑到很多种情况，比如左右括号数量，括号类型是否对应等，也没办法准确的去删除已分配好的括号，即便做出了删除的办法，但频繁的对字符串进行操作也会导致代码效率低下。

但如今学习了栈就不一样了，让我们用"栈"的方式看看这题该如何解决吧：

📚 思路分析：

📕 遍历字符串，当出现的' ( '，' [ '，' { '时放入栈中。

📕 当出现' ) '，' ] '，' } '时判断：如果此时栈顶元素(上一个符号)是否为其对应的括号

📕 如果是其对应括号，则"将栈顶元素出栈，然后遍历下一个字符"(此行为代表删除这对括号)

📕 如果不是其对应括号，则直接返回false(因为如果栈顶元素不匹配，则代表此字符是多余的)

📕 最后对栈进行判断，如果栈为空，则代表所有括号匹配成功，返回true，反之则返回false

📖 代码示例：

class Solution {public boolean isValid(String s) {Stack<Character> stack = new Stack<>();char[] str = s.toCharArray();for(int i = 0;i < str.length;i++){char c = str[i];if(c == ')' || c == ']' || c == '}'){if(stack.empty()){return false;}char n = stack.peek();if((n == '(' && c != ')') || (n == '[' && c != ']') || (n == '{' && c != '}')){return false;}stack.pop();}else {stack.push(c);}}if(stack.empty()){return true;}return false;}
}

二、队列(Queue)

① 队列的概念

还记得栈的性质嘛？没错，"后进先出"，而队列恰恰与栈相反，队列的性质是"先进先出"，也就是"只允许在一段进行插入数据操作"，"在另一端进行删除数据的操作"的特殊线性表。

📕 队尾：进行插入操作的一端

📕 对头：进行删除操作的一端

在生活中也有很多队列的体现，就比如"银行排队取钱"，就像队列一样，先排队的人先取(先走)，后排队的人后取(后走)~

② 队列的使用

由图我们可以看出，Queue是一个接口，并且我们还要知道，Queue底层是使用链表实现的，所以当我们对队列进行实例化的时候，是不能使用Queue的，而是应该new一个链表~

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

boolean offer(E e) 方法

E poll() 方法

peek() 方法

int size() 方法

boolean isEmpty() 方法

③ 队列的模拟实现

大部分代码以及思路都和模拟实现双向链表是一致的，如果有需要可以前往Java-数据结构-链表(LinkedList)-双向链表-CSDN博客
进行更细致的学习，如果链表学会了那队列不在话下~

在刚刚我们知道了队列(Queue)的底层是使用链表来实现的，但是我们学习过了单向链表，也学习过双向链表，对于队列的模拟实现，我们应该使用哪种链表会更加方便呢？由于队列最主要的两种操作也就仅仅是入队和出队，那么我们便对这两点展开讨论：

📚 单向链表：

📕 如果从表头实现入队，那么就要从表尾实现出队，则入队为O(1)，出队为O(n)

📕 如果从表尾实现入队，那么就要从表头实现出队，则入队为O(n)，出队为O(1)

📚 双向链表：

📕 如果从表头实现入队，那么就要从表尾实现出队，则入队为O(1)，出队为O(1)

📕 如果从表尾实现入队，那么就要从表头实现出队，则入队为O(1)，出队为O(1)

所以我们应该使用双向链表来模拟实现队列~

1. 队列的基本框架

📕 由于是使用双向链表，所以框架基本一致~

public class MyQueue {public static class ListNode{private int val;private ListNode prev;private ListNode next;public ListNode(int val) {this.val = val;}}public ListNode front;public ListNode last;public int usedSize = 0;
}

2. offer 方法

其实本质上就是双向链表的尾插法~

📚 想要实现元素的入队并不难，我们需要注意以下几点：

📕 如果该队列为空，则需要将node变成新的head

📕 如果队列不为空，应该将node插入last的后继，并且让node的前驱变成last

📕 只要有元素入队，last就要进行更新

📖 代码示例：

    public void offer(int e){ListNode node = new ListNode(e);if(front == null){front = node;}else{last.next = node;node.prev = last;}last = node;usedSize++;}

3. poll 方法

其实本质上就类似于双向链表的"删掉第一个结点"

📚 有以下注意事项：

📕 队列为空时，直接返回null

📕 队列中只有一个元素时直接全部置null

📕 队列中有多个元素时，

📖 代码示例：

    public int poll() {int value = 0;if (front == null) {return -1;} else if (front == last) {last = null;front = null;} else {value = front.val;front = front.next;front.prev = null;--usedSize;}return value;}

4. peek 方法

获取队头元素，就是上面poll的不删除版本

📖 代码示例：

    public int peek(){if(front == null){return -1;}return front.val;}

5. size & isEmpty 方法

📖 代码示例：

    public int size(){return usedSize;}public boolean isEmpty(){return front == null;}

完整代码：

public class MyQueue {public static class ListNode {private int val;private ListNode prev;private ListNode next;public ListNode(int val) {this.val = val;}}public ListNode front;public ListNode last;public int usedSize = 0;public void offer(int e) {ListNode node = new ListNode(e);if (front == null) {front = node;} else {last.next = node;node.prev = last;}last = node;usedSize++;}public void display() {System.out.print("[");ListNode cur = front;while (cur != null) {System.out.print(cur.val);if (cur.next != null) {System.out.print(", ");}cur = cur.next;}System.out.print("]");}public int poll() {int value = 0;if (front == null) {return -1;} else if (front == last) {last = null;front = null;} else {value = front.val;front = front.next;front.prev = null;--usedSize;}return value;}public int peek(){if(front == null){return -1;}return front.val;}public int size(){return usedSize;}public boolean isEmpty(){return front == null;}
}

④ 习题：设计循环队列

📚 思路提示：

循环队列是个什么东西呢？其实就是将队列的头和尾连接到一起而已，没有什么特别的~我们来看看循环队列长什么样子：

这就是我们的循环队列了，其中内部的是元素的下标，外部的是用来存储元素的空间，其实看起来就像一个循环了的数组一样~

而刚刚也看到啦，就类似于环形的数组，所以对于这个环形链表，我们可以采取使用顺序表的方式来模拟实现它：

对于这个循环队列的实现，最重要的难点在于：当正常访问到队列的末尾时，如何判断它是空队列还是满队列，以及如何让它从队尾的下一位访问到队头。

对此我们有以下解法：

① 定义一个size记录存储的个数

        size == len 就是满

        size == 0 就是空

(该方法比较简单，就不过多介绍了)

② 牺牲一个空间来判满：

(我们在此使用这种方法来解决)

📕 基本框架：

class MyCircularQueue {public int left;public int right;public int[] elem;public MyCircularQueue(int k) {elem = new int[k + 1];}public boolean enQueue(int value) {return false;}public boolean deQueue() {return false;}public int Front() {return -1;}public int Rear() {return -1;}public boolean isEmpty() {return false;}public boolean isFull() {return false;}
}

📕 isFull 方法

判断循环队列是否为空的方法，由于我们刚刚说了：我们采用的是舍弃一个空间的方法，也就是队尾 + 1 正好等于该队列的大小时，也就舍弃一个空间，算它为满了。

📖 代码示例：

    public boolean isFull() {if((right + 1) % elem.length == left){return true;}return false;}

📕 enQueue 方法

向队列中插入一个元素，这就要用到我们刚刚完成的 isFull 方法了

⭐ 如果队列为满，直接返回false

还有，别忘了我们是舍弃一块空间的方法，所以不能直接是 right % 队列大小

而应该是 (right + 1) % 队列大小，才能够跳过一块空间~ 

📖 代码示例：

    public boolean enQueue(int value) {if(isFull()){return false;}elem[right] = value;right = (right + 1) % elem.length;return true;}

📕 isEmpty 方法

对于判断该循环队列是否为空的方法，我们只需要判断 left 是否等于 right 就行了，因为 left 始终都是在 right 后面的，当两者相等时，也就代表正好将链表的元素都删除了。

📖 代码示例：

    public boolean isEmpty() {return left == right;}

📕 Front 方法

从队头获取元素的方法，只需要额外判断一下链表是否为空即可~

📖 代码示例：

    public int Front() {if(isEmpty()){return -1;}return elem[left];}

📕 Rear 方法

获取队尾元素的方法，这个就没那么简单了，除了需要对队列是否为空做出判断，还需要注意这个问题：

我们一般插入元素后，right就会指向下一个位置，所以如果直接取right下标的元素是行不通的，我们需要取right的前一个元素~

或许你认为只需要对right - 1就好了呀，实则不然，别忘了我们是循环队列，所以当我们队列已满的时候，right 是在 0 位置的，这时我们需要访问的 index 就不是 right - 1了 ，而是队列大小-1。

📖 代码示例：

    public int Rear() {if(isEmpty()){return -1;}int index = (right == 0 ? elem.length - 1 : right - 1);return elem[index];}

📕 deQueue 方法

删除队列中一个元素，首先判断是否为空，如果为空队列直接返回false~

随后就还是一样的，删除一位，队尾再向后走一位，并且记得是(left + 1)而不是left

📖 代码示例：

    public boolean deQueue() {if(isEmpty()){return false;}elem[left] = 0;left = (left + 1) % elem.length;return true;}

也是顺利通过了~

那么这次关于栈与队列的知识，就为大家分享到这里啦，作者能力有限，如果有讲得不清晰或者不正确的地方，还请大家在评论区多多指出，我也会虚心学习的！那我们下次再见哦