Java数据结构栈和队列(Stack和Queue详解)

前言：

        栈和队列是数据结构中重要的存储方式，也是建立在Arrarylist和LinkedList之上的数据结构。

        本猿在C语言阶段就已经详细剖析过栈和队列，不熟悉的小伙伴可以翻看之前的博客内容！

      Java阶段一方面剖析Java中自带的Stack和Queue中的各种方法，另一方面也是重点重新再次实现栈和队列，  并发掘和C语言中的区别。

栈(Stack)：

        栈是一种"先进后出"的数据结构，如图：

Java中的栈:

        在Java的util包中有Stack类，我们可以看到Stack的源代码：

继承了Vector，那么Vector中又有哪些继承关系呢？

我们发现继承了AbstractList，并且扩展了好多接口，其中包括List接口。

综上我们可以以一张结构图概括：

栈的模拟实现：

        我们利用顺序表模拟实现栈，当然也可以用链表实现栈，Java中用的是顺序表！至于为什么要用顺序表，等自己实现一遍栈大概就清楚了！

    

public class MyStack {private int[] array;private int size;private static final int DEFFAULEVALUE = 10;public MyStack() {array = new int[DEFFAULEVALUE];}public void push(int value) {ensureCapacity();array[this.size++] = value;}public int pop(){if(empty()) {throw new RuntimeException("栈为空，无法获取栈顶元素");}size--;return array[size];}public int peek(){if(empty()){throw new RuntimeException("栈为空，无法获取栈顶元素");}return array[size-1];}public int size(){return size;}private boolean empty() {if(this.size == 0) {return true;}return false;}private void ensureCapacity() {if(this.size == array.length) {array = Arrays.copyOf(array,size*2);}}
}

注意：

        在main方法中测试的时候，需要注意打印栈当中的元素的时候需要pop打印，也就是需要用到for循环打印，但是这样写对不对呢？

        

for (int i = 0; i < myStack.size(); i++) {System.out.println(myStack.pop());
}

这样的for循环是有问题的，问题在于每次pop结束之后，size()的值在发生变化，也就是这个循环不会执行size()次。

        所以以上遍历会出现问题，应该这样遍历：

int num = myStack.size();
for (int i = 0; i < num; i++) {System.out.println(myStack.pop());
}

这样遍历才不会出现问题！！ 

关于栈的习题(典型)：

1、括号匹配问题：

        20. 有效的括号 - 力扣（LeetCode）

        具体题目请参考力扣，具体实现代码如下：

        

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

2、逆波兰表达式求值：

     150. 逆波兰表达式求值 - 力扣（LeetCode）   

class Solution {public int evalRPN(String[] tokens) {Stack<String> str = new Stack<>();for(int i = 0;i < tokens.length;i++) {if(tokens[i].equals("+")) {int num1 = Integer.valueOf(str.pop());int num2 = Integer.valueOf(str.pop());str.push(num1+num2+"");}else if(tokens[i].equals("-")) {int num1 = Integer.valueOf(str.pop());int num2 = Integer.valueOf(str.pop());str.push(num2-num1+"");}else if(tokens[i].equals("*")) {int num1 = Integer.valueOf(str.pop());int num2 = Integer.valueOf(str.pop());str.push(num1*num2+"");}else if(tokens[i].equals("/")) {int num1 = Integer.valueOf(str.pop());int num2 = Integer.valueOf(str.pop());str.push(num2/num1+"");}else {str.push(tokens[i]);}}return Integer.valueOf(str.pop());}
}

3、出栈进栈次序匹配：

栈的压入、弹出序列_牛客题霸_牛客网 (nowcoder.com)

public class Solution {/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param pushV int整型一维数组 * @param popV int整型一维数组 * @return bool布尔型*/public boolean IsPopOrder (int[] pushV, int[] popV) {// write code hereStack<Integer> st = new Stack<>();int j = 0;for(int i = 0;i<pushV.length;i++) {st.push(pushV[i]);while(!st.empty() && st.peek() == popV[j]) {st.pop();j++;}}if(st.empty()) {return true;}return false;
}
}

4、最小栈：

155. 最小栈 - 力扣（LeetCode）

class MinStack {Stack<Integer> st1;Stack<Integer> st2;int minInteger;public MinStack() {st1 = new Stack<>();st2 = new Stack<>();}public void push(int val) {if(st1.empty() && st2.empty()) {minInteger = val;st1.push(val);st2.push(val);}else {st1.push(val);if(val < minInteger) {st2.push(val);minInteger = val;}else {st2.push(minInteger);}}}public void pop() {st1.pop();st2.pop();if(!st2.empty()) {minInteger = st2.peek();}}public int top() {return st1.peek();}public int getMin() {return st2.peek();}
}

队列(Queue)：

Java中的队列：

也是一系列的继承关系。

队列的模拟实现：

public class MyQueue {// 双向链表节点public static class ListNode{ListNode next;ListNode prev;int value;ListNode(int value){this.value = value;}}ListNode first; // 队头ListNode last; // 队尾int size = 0;// 入队列---向双向链表位置插入新节点public void offer(int e){ListNode newNode = new ListNode(e);if(first == null){first = newNode;
// last = newNode;}else{last.next = newNode;newNode.prev = last;
// last = newNode;}last = newNode;size++;}// 出队列---将双向链表第一个节点删除掉public int poll(){
// 1. 队列为空
// 2. 队列中只有一个元素----链表中只有一个节点---直接删除
// 3. 队列中有多个元素---链表中有多个节点----将第一个节点删除int value = 0;if(first == null){return -1;}else if(first == last){last = null;first = null;}else{value = first.value;first = first.next;first.prev.next = null;first.prev = null;}--size;return value;}// 获取队头元素---获取链表中第一个节点的值域public int peek(){if(first == null){return 0;}return first.value;}public int size() {return size;}public boolean isEmpty(){return first == null;}
}

循环队列：