java 数据结构栈和队列

目录

栈(Stack)

栈的使用

栈的模拟实现

栈的应用场景

队列(Queue)

队列的使用

队列模拟实现

循环队列

双端队列

用队列实现栈

用栈实现队列

---

栈(Stack)

什么是栈？

栈 ：一种特殊的线性表，其 只允许在固定的一端进行插入和删除元素操作 。进行数据插入和删除操

作的一端称为栈 顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO （ Last In First Out ）的原则。

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

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

---

栈的使用

方法例子：

public static void main(String[] args) {
Stack<Integer> s = new Stack();s.push(1);s.push(2);s.push(3);s.push(4);
System.out.println(s.size()); // 获取栈中有效元素个数---> 4
System.out.println(s.peek()); // 获取栈顶元素---> 4s.pop(); // 4出栈，栈中剩余1 2 3，栈顶元素为3
System.out.println(s.pop()); // 3出栈，栈中剩余1 2 栈顶元素为3if(s.empty()){System.out.println("栈空");}else{System.out.println(s.size());
}
}

---

栈的模拟实现

从上图中可以看到，Stack继承了Vector，Vector和ArrayList类似，都是动态的顺序表，不同的是

Vector是线程安全的。

模拟实现代码：

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

---

栈的应用场景

1.逆波兰表达式(中缀转后缀)：

https://leetcode.cn/problems/evaluate-reverse-polish-notation/

代码：

class Solution {public int evalRPN(String[] tokens) {Stack<Integer> stack=new Stack<>();for(String x:tokens){if(!isCase(x)){stack.push(Integer.parseInt(x));}else{int nums2=stack.pop();int nums1=stack.pop();switch(x){case "+":stack.push(nums1+nums2);break;case "-":stack.push(nums1-nums2);break;case "*":stack.push(nums1*nums2);break;case "/":stack.push(nums1/nums2);break;}}  }return stack.pop();
}public boolean isCase(String s){if(s.equals("+")||s.equals("-")||s.equals("*")||s.equals("/")){return true;}return false;}}

2.括号匹配：

https://leetcode.cn/problems/valid-parentheses/description/

代码：

class Solution {public boolean isValid(String s) {Stack<Character> stack = new Stack<>();//遍历for (int i = 0; i < s.length(); i++) {char ch = s.charAt(i);//取出字符//判断是不是左括号if (ch == '(' || ch == '{' || ch == '[') {stack.push(ch);} else {//遇到右括号,判断栈是不是空if (stack.empty()) {return false;}//看看括号匹不匹配char ch2 = stack.peek();if ((ch2 == '(' && ch == ')') || (ch2 == '{' && ch == '}') || (ch2 == '[' && ch == ']')) {stack.pop();} else {return false;}}}//如果栈不空,并且遍历完了if (!stack.empty()) {return false;}return true;}
}

3.出栈入栈次序匹配：

https://www.nowcoder.com/practice/d77d11405cc7470d82554cb392585106?tpId=13&&tqId=11174&rp=1&ru=/activity/oj&qru=/ta/coding-interviews/question-ranking

代码：

    public boolean IsPopOrder (int[] pushV, int[] popV) {Stack<Integer> stack = new Stack<>();int j = 0;for (int i = 0; i < pushV.length; i++) {stack.push(pushV[i]);//每进栈一个数字,peek一下判断一不一样,并且判断越没越界while (!stack.empty() && j < popV.length && stack.peek() == popV[j]) {stack.pop();j++;}}//循环走完了,判断是不是空,是的话就匹配了,不是的话就不匹配return stack.empty();
}

4.最小栈：

https://leetcode.cn/problems/min-stack/

代码：

class MinStack {public Stack<Integer> stack;public Stack<Integer> minStack;public MinStack() {stack = new Stack<>();minStack = new Stack<>();}public void push(int val) {stack.push(val);if (minStack.empty()) {minStack.push(val);} else {int minVal = minStack.peek();//判断最小栈的栈顶是不是小于等于要存入的值if (val <= minVal) {minStack.push(val);}}}public void pop() {if (stack.peek().equals(minStack.peek())) {// 弹出的元素是全栈最小的minStack.pop();}stack.pop();}public int top() {return stack.peek();}public int getMin() {if (!minStack.empty()) {return minStack.peek();}return -1;
}
}

---

队列(Queue)

队列 ：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进

先出 FIFO(First In First Out) 入队列：进行插入操作的一端称为 队尾（ Tail/Rear ） 出队列：进行删

除操作的一端称为 队头 （ Head/Front ）

---

队列的使用

在 Java 中， Queue 是个接口，底层是通过链表实现 的。

注意：Queue是个接口，在实例化时必须实例化LinkedList的对象，因为LinkedList实现了

Queue接口。

用法例子：

public static void main(String[] args) {
Queue<Integer> q = new LinkedList<>();q.offer(1);q.offer(2);q.offer(3);q.offer(4);q.offer(5); // 从队尾入队列
System.out.println(q.size());
System.out.println(q.peek()); // 获取队头元素q.poll();
System.out.println(q.poll()); // 从队头出队列，并将删除的元素返回if(q.isEmpty()){System.out.println("队列空");}else{System.out.println(q.size());
}
}

---

队列模拟实现

队列中既然可以存储元素，那底层肯定要有能够保存元素的空间，通过前面线性表的学习了解到常

见的空间类型有 两种：顺序结构 和 链式结构 。同学们思考下： 队列的实现使用顺序结构还是链式

结构好？

模拟实现代码：

public class Queue {// 双向链表节点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 null;} 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 null;}return first.value;}public int size() {return size;}public boolean isEmpty() {return first == null;}
}

---

循环队列

实际中我们有时还会使用一种队列叫循环队列。如操作系统课程讲解生产者消费者模型时可以就会

使用循环队列。 环形队列通常使用数组实现。

https://leetcode.cn/problems/design-circular-queue/description/

代码：

public class MyCircularQueue {public int[] elem;public int front; // 队头public int rear; // 队尾public int usedSize; // 记录队列中元素数量public MyCircularQueue(int k) {elem = new int[k];usedSize = 0; // 初始化为 0}// 入队public boolean enQueue(int value) {if (isFull()) {return false;}elem[rear] = value;rear = (rear + 1) % elem.length;usedSize++; // 每次入队增加 usedSizereturn true;}// 出队public boolean deQueue() {if (isEmpty()) {return false;}front = (front + 1) % elem.length;usedSize--; // 每次出队减少 usedSizereturn true;}// 得到队头元素public int Front() {if (isEmpty()) {return -1;}return elem[front];}// 得到队尾元素public int Rear() {if (isEmpty()) {return -1;}//如果是0下标就返回数组长度-1不是就rear-1int index = (rear == 0) ? elem.length - 1 : rear - 1;return elem[index];}public boolean isEmpty() {return usedSize == 0; // 使用 usedSize 判断是否为空}public boolean isFull() {return usedSize == elem.length; // 使用 usedSize 判断是否为满}
}

---

双端队列

双端队列（deque）是指允许两端都可以进行入队和出队操作的队列，deque 是 “double ended

queue” 的简称。 那就说明元素可以从队头出队和入队，也可以从队尾出队和入队。

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

在实际工程中，使用Deque接口是比较多的，栈和队列均可以使用该接口。

Deque<Integer> stack = new ArrayDeque<>();//双端队列的线性实现
Deque<Integer> queue = new LinkedList<>();//双端队列的链式实现

---

用队列实现栈

https://leetcode.cn/problems/implement-stack-using-queues/

代码：

class MyStack {// 用队列实现栈//用两个队列实现public Deque<Integer> qu1;public Deque<Integer> qu2;public MyStack() {qu1 = new LinkedList<>();qu2 = new LinkedList<>();}public void push(int x) {if (!qu1.isEmpty()) {qu1.offer(x);} else if (!qu2.isEmpty()) {qu2.offer(x);} else {//都空的,指定存qu1.offer(x);}}public int pop() {if (empty()) {return -1;}if (!qu1.isEmpty()) {//这样记录不会因为poll改变int size = qu1.size();for (int i = 0; i < size - 1; i++) {//取到长度减1个就是要的了int x = qu1.poll();qu2.offer(x);}return qu1.poll();} else {int size = qu2.size();for (int i = 0; i < size - 1; i++) {//取到长度减1个就是要的了int x = qu2.poll();qu1.offer(x);}return qu2.poll();}}public int top() {if (empty()) {return -1;}if (!qu1.isEmpty()) {//这样记录不会因为poll改变int size = qu1.size();int x = 0;//用来记录拿出来的值,循环结束后就拿到最后一个for (int i = 0; i < size; i++) {x = qu1.poll();qu2.offer(x);}return x;} else {int size = qu2.size();int x = 0;//用来记录拿出来的值,循环结束后就拿到最后一个for (int i = 0; i < size ; i++) {x = qu2.poll();qu1.offer(x);}return x;}}public boolean empty() {//判断两个队列是不是都空的return qu1.isEmpty() && qu2.isEmpty();}
}

用栈实现队列

https://leetcode.cn/problems/implement-queue-using-stacks/description/

代码：

public class MyQueue {public Stack<Integer> s1;public Stack<Integer> s2;public MyQueue() {s1 = new Stack<>();s2 = new Stack<>();}public void push(int x) {s1.push(x);}public int pop() {if (empty()) {return -1;}if (s2.isEmpty()) {while (!s1.isEmpty()) {s2.push(s1.pop());}}return s2.pop();}public int peek() {if (empty()) {return -1;}if (s2.isEmpty()) {int size = s1.size();for (int i = 0; i < size; i++) {int x = s1.pop();s2.push(x);}}return s2.peek();}public boolean empty() {return s1.isEmpty() && s2.isEmpty();}
}