数据结构初阶（栈和队列）

一、栈

1.1 什么是栈

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

1.2 栈的使用

（1）底层代码

import java.util.Arrays;public class MyStack {private int[] elem;     //stack的底层是数组private int usedSize;public MyStack() {this.elem = new int[5];}//压栈public void push(int val) {if(isFull()) {      //判断里面的空间是否为满的情况elem = Arrays.copyOf(elem,2*elem.length);}elem[usedSize] = val;usedSize++;}public boolean isFull() {return usedSize == elem.length;}//出栈public int pop() {//1、判断栈不为空if(empty()) {//抛出异常！！throw new StackEmptyException("栈为空！");}//2、开始删除return elem[--usedSize];     //elem[useSize]的数字没有被删掉，后续如果有push的话，会把值该赋给掉}//获取栈顶元素public int peek() {//1、判断栈不为空if(empty()) {//抛出异常！！throw new StackEmptyException("栈为空！");}//2、开始删除return elem[usedSize-1];}public boolean empty() {return usedSize == 0;}
}

（2）方法

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

（3）栈的应用

• 改变元素的序列
  • 进栈过程中可以出栈 和 依次入栈，然后再依次出栈 对元素出栈的顺序的改变
• 将递归转化为循环

//递归方式
public void show(ListNode head) {if(head == null) {return;}if(head.next == null) {System.out.println(head.val);return;}show3(head.next);System.out.println(head.val);
}//循环方式
public void show2() {Stack<ListNode> stack = new Stack<>();ListNode cur = head;while (cur != null) {stack.push(cur);cur = cur.next;}//依次出栈while (!stack.empty()) {ListNode tmp = stack.pop();System.out.println(tmp.val);}
}

• 逆波兰表达式求值

class Solution {public int evalRPN(String[] tokens) {Deque<Integer> stack = new LinkedList<Integer>();int n = tokens.length;for (int i = 0; i < n; i++) {String token = tokens[i];if (isNumber(token)) {stack.push(Integer.parseInt(token));} else {int num2 = stack.pop();int num1 = stack.pop();switch (token) {case "+":stack.push(num1 + num2);break;case "-":stack.push(num1 - num2);break;case "*":stack.push(num1 * num2);break;case "/":stack.push(num1 / num2);break;default:}}}return stack.pop();}public boolean isNumber(String token) {return !("+".equals(token) || "-".equals(token) || "*".equals(token) || "/".equals(token));}
}

• 有效的括号

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;}else {char tmp = stack.peek();if (ch == ')' && tmp == '(' || ch == '}' && tmp == '{' || ch == ']' && tmp == '[') {stack.pop();}else {return false;}}}}if (!stack.empty()) {return false;}return true;}
}

• 栈的压入、弹出序列

import java.util.Stack;public class Solution {public boolean IsPopOrder(int [] pushA,int [] popA) {Stack<Integer> stack = new Stack<>();int j = 0;for (int i = 0; i < pushA.length; i++) {stack.push(pushA[i]);while (!stack.empty() && j < popA.length&& stack.peek() == popA[j]) {stack.pop();j++;}}return stack.empty();}
}

• 最小栈

class MinStack {
private Stack<Integer> stack ;private 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 {if(val <= minStack.peek()) {minStack.push(val);}}}public void pop() {//栈为空 则不能进行弹出元素if(stack.empty()) {return;}int val = stack.pop();if(val == minStack.peek()) {minStack.pop();}}//获取栈顶元素 和 最小栈没有关系public int top() {if(stack.empty()) {return -1;}return stack.peek();}//获取元素 不是删除元素public int getMin() {return minStack.peek();}}

栈、虚拟机栈、栈帧有什么区别呢？

栈是数据结构
虚拟机栈是内存
栈帧是调用方法是，在虚拟机栈开辟的一个内存

二、队列

2.1 什么是队列

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

2.2 队列的使用

（1）底层代码的实现

在Java中，Queue是个接口，底层是通过链表实现的
队列可以通过数组和链表实现

• 如果是双向链表，那么入队和出队，均可以达到O(1)，不管从哪边进
• 如果是单链表，并且记录了最后一个节点的位置的情况下，我们可以采用从尾入队，从头出队的方式，都是O(1)。如果是从头进，从尾出，那么出队的复杂度为O(n)

（2）队列的使用

❤️创建
Queue是个接口，在实例化时必须实例化LinkedList的对象，因为LinkedList实现了Queue接口。

Queue<Integer> q = new LinkedList<>();

❤️方法

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

❤️队列的模拟实现

• 顺序结构
  双向链表

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 -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 -1;}return first.value;}public int size() {return size;}public boolean isEmpty(){return first == null;}
}

单向链表

public class MyQueue {static class ListNode {public int val;public ListNode next;public ListNode(int val) {this.val = val;}}public ListNode head;public ListNode last;private int usedSize;public void offer(int val) {ListNode node = new ListNode(val);if(head == null) {head = node;last = node;}else {last.next = node;last = last.next;}usedSize++;}public int getUsedSize() {return usedSize;}public int poll() {if(head == null) {return -1;}int val = -1;if(head.next == null) {val = head.val;head = null;last = null;return val;}val = head.val;head = head.next;usedSize--;return val;}public int peek() {if(head == null) {return -1;}return head.val;}}

• 循环结构

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

class MyCircularQueue {private int[] elem;private int front;//队头下标private int rear;//队尾下标public MyCircularQueue(int k) {this.elem = new int[k+1];}//入队public boolean enQueue(int value) {if(isFull()) {return false;}elem[rear] = value;rear = (rear+1) % elem.length;return true;}//出队public boolean deQueue() {if(isEmpty()) {return false;}front = (front+1) % elem.length;return true;}//得到队头元素public int Front() {if(isEmpty()) {return -1;}return elem[front];}//得到队尾元素public int Rear() {if(isEmpty()) {return -1;}int index = (rear == 0) ? elem.length-1 : rear-1;return elem[index];}public boolean isEmpty() {return rear == front;}public boolean isFull() {return (rear+1) % elem.length == front;}
}

解析

• 数组下标循环：
  下标最后再往后：(rear + 1) % elem.length;
  下标最前再往前：(front + 1) % elem.length;
• 如何区分空和满：
  满： 通过添加 useSize 属性记录,当useSIze == len 的时候为满
  保留一个位置，用这个位置来表示满
  使用标记
  空： front == rear 时为空

2.3 双端队列

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

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

Deque<Integer> stack = new ArrayDeque<>();  双端队列的线性实现，底层是数组
Deque<Integer> queue = new LinkedList<>();  双端队列的链式实现，底层是链表

2.4 练习

一、用队列实现栈

import java.util.LinkedList;
import java.util.Queue;class MyStack {private Queue<Integer> qu1;private Queue<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()) {int currentSize = qu1.size();for (int i = 0; i < currentSize-1; i++) {int x = qu1.poll();qu2.offer(x);}return qu1.poll();//最后一个数据返回}if(!qu2.isEmpty()) {int currentSize = qu2.size();for (int i = 0; i < currentSize-1; i++) {int x = qu2.poll();qu1.offer(x);}return qu2.poll();//最后一个数据返回}return -1;}//peek方法public int top() {if(empty()) {return -1;}if(!qu1.isEmpty()) {int currentSize = qu1.size();int x = -1;for (int i = 0; i < currentSize; i++) {x = qu1.poll();qu2.offer(x);}return x;//最后一个数据返回}if(!qu2.isEmpty()) {int currentSize = qu2.size();int x = -1;for (int i = 0; i < currentSize; i++) {x = qu2.poll();qu1.offer(x);}return x;//最后一个数据返回}return -1;}public boolean empty() {return qu1.isEmpty() && qu2.isEmpty();}
}

二、用栈实现队列

class MyQueue {private Stack<Integer> s1;private Stack<Integer> s2;public MyQueue() {s1 = new Stack<>();s2 = new Stack<>();}public void push(int x) {s1.push(x);}public int pop() {if(!s2.empty()) {return s2.pop();}else {while(!s1.empty()) {int val = s1.pop();s2.push(val);}return s2.pop();}}public int peek() {if(!s2.empty()) {return s2.peek();}else {while(!s1.empty()) {int val = s1.pop();s2.push(val);}return s2.peek();}}public boolean empty() {return s1.empty() && s2.empty();}
}