栈和队列 
文章图片
文章图片
栈是先进后出（在栈顶进行删除和插入），所以你可以用在一些特殊的地方，比如逆序打印链表等等。
比如判断栈出数据的顺序，中缀表达式 转 后缀表达式 （后缀表达式也叫作逆波兰表达式）
文章图片
现将转换成后缀表达式，通过这个表达式去计算。那么如何去转换成后缀表达式 需要用到栈
栈中的一些方法，可以查看api，比较常用的：peek,pop,push,isEmpty，search
【笔记|栈和队列常见oj题】
文章图片
public static void main(String[] args) {
MyStack stack = new MyStack();
stack.push(1);
stack.push(2);
stack.push(3);
stack.push(4);
stack.push(5);
stack.push(6);
System.out.println(stack.pop());
//弹出栈顶元素，并且删除 6
System.out.println(stack.pop());
//弹出栈顶元素，并且删除 5
System.out.println(stack.pop());
//弹出栈顶元素，并且删除 4
System.out.println(stack.pop());
//弹出栈顶元素，并且删除 3
System.out.println(stack.pop());
//弹出栈顶元素，并且删除 2
System.out.println(stack.pop());
//弹出栈顶元素，并且删除 1
System.out.println(stack.peek());
//获取栈顶元素，但是不删除 5
System.out.println(stack.peek());
//获取栈顶元素，但是不删除 5
System.out.println(stack.isEmpty());
//false
System.out.println(stack.size());
}
栈的弹入、压出 栈的压入、弹出
import java.util.ArrayList;
import java.util.Stack;
public class Solution {
public boolean IsPopOrder(int [] pushA,int [] popA) {
Stack stack = new Stack<>();
intj = 0;
for(int i = 0;
i 逆波兰式求值 逆波兰式求值
class Solution {
public int evalRPN(String[] tokens) {
String val= " ";
Stack stack = new Stack<>();
for(int i = 0;
i 以上是两道用栈来解决的问题
创建栈的对象，默认的构造方法实际上给栈提供的大小是10个空间
实现栈的一些基本功能
public class MyStack {
public int[] elem;
public int usedSize;
public MyStack() {
this.elem = new int[5];
}public void push(int val) {
if(isFull()) {
//扩容
this.elem = Arrays.copyOf(this.elem,2*this.elem.length);
}
this.elem[this.usedSize] = val;
this.usedSize++;
}public boolean isFull() {
return this.usedSize == this.elem.length;
}public int pop() {
if(isEmpty()) {
throw new RuntimeException("栈为空！");
}
int oldVal = this.elem[usedSize-1];
this.usedSize--;
return oldVal;
}public int peek() {
if(isEmpty()) {
throw new RuntimeException("栈为空！");
}
return this.elem[usedSize-1];
}public boolean isEmpty() {
return this.usedSize == 0;
}
}
文章图片
括号匹配问题 括号匹配问题
class Solution {
public boolean isValid(String s) {
Stack stack = new Stack<>();
int k = 0;
for(int i = 0;
i.length();
i++){
String s1 = s.charAt(i)+"";
if(s1.equals("(") ||s1.equals("{") ||s1.equals("[")){
stack.push(s1);
k++;
}else{
switch(s1){
case ")":
if(!stack.isEmpty() && "(".equals(stack.peek())){
stack.pop();
}else{
return false;
}
break;
case "}":
if(!stack.isEmpty() && "{".equals(stack.peek())){
stack.pop();
}else{
return false;
}
break;
case "]":
if(!stack.isEmpty() && "[".equals(stack.peek())){
stack.pop();
}else{
return false;
}
break;
}
}
}
if(k != 0){
return stack.isEmpty();
}else{
return false;
}}
}
实现最小栈 实现一个最小栈
//博哥讲解在栈的那一节的最后一部分
class MinStack {private Stack stack;
private Stack minStack;
public MinStack() {
stack = new Stack<>();
minStack = new Stack<>();
}public void push(int val) {
stack.push(val);
if(!minStack.isEmpty()){
int cur = minStack.peek();
if(val <= cur){
minStack.push(val);
}
}else{
minStack.push(val);
}
}public void pop() {
int popVal = stack.pop();
if(!minStack.isEmpty()){
int top = minStack.peek();
if(top == popVal){
minStack.pop();
}
}
}public int top() {
return stack.peek();
}public int getMin() {
return minStack.peek();
}
}
文章图片
LinkedList 底层是个双向链表
文章图片
public static void main1(String[] args) {
//LinkedList实现了Queue和Deque，父类引用指向子类对象，实现了向上转型，但是方法
Queue queue = new LinkedList<>();
//普通队列 ：对头进，队尾处
Deque queue2 = new LinkedList<>();
//双端队列 ：队头队尾都可以进出LinkedList list = new LinkedList<>();
这里再次说明向上转型：前两种引用使用的方法必须包含在父类的方法中，所以方法比较少，而第三种不采用向上转型，方法更多。但我们一般用向上转型的话，并不需要那么的方法，足够我们用，且能明确指出我们就是想用Queue这个类。
队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上
出数据，效率会比较低
文章图片
文章图片
文章图片
public static void main(String[] args) {
MyQueue queue = new MyQueue();
queue.offer(1);
queue.offer(2);
queue.offer(3);
System.out.println(queue.peek());
//1
System.out.println(queue.poll());
//1
System.out.println(queue.poll());
//2
System.out.println(queue.poll());
//3
System.out.println(queue.poll());
//
}public static void main2(String[] args) {
Queue queue = new LinkedList<>();
queue.offer(2);
System.out.println(queue.peek());
//1
System.out.println(queue.poll());
//1
}public static void main3(String[] args) {
Deque queue2 = new LinkedList<>();
queue2.offerLast(1);
//默认队尾入队的
queue2.offerFirst(2);
//2 1
System.out.println(queue2.peekFirst());
//2
System.out.println(queue2.peekLast());
//1
}
文章图片
上面的图说的是：双向链表可以实现普通队列、双端队列、双向链表。
接下来用单链表来实现队列（双向链表也可以）
但是单链表你进行入队的话 时间复杂度是O(1) 但是出队时间复杂度是O(N) 所以你加一个尾指针
文章图片
class Node{
public int val;
public Node next;
public Node(int val) {
this.val = val;
}
}
public class MyQueue {
public Node head;
public Node last;
public void offer(int val){
Node node = new Node(val);
if(head == null){
head = node;
last = node;
}else{
last.next = node;
last = last.next;
}}
/**
* 出队
*/
public int poll(){
if(isEmpty()){
throw new RuntimeException("队列为空，无法出队列");
}
int oldVal = this.head.val;
this.head = head.next;
return oldVal;
}
public boolean isEmpty(){
return head == null;
}
public int peek(){
if(isEmpty()) {
throw new RuntimeException("队列为空，无法出队列");
}
return head.val;
}
}
循环队列
文章图片
文章图片
文章图片
文章图片
设计循环队列 设计循环队列
class MyCircularQueue {
public int front;
public int rear;
public int[] elem;
public MyCircularQueue(int k) {
this.elem = new int[k+1];
//这里采取的是第三种，浪费一个空间，但是你又得多创建一个空间，否则不满足oj
}/**
* 入队
* @param value
* @return
*/
public boolean enQueue(int value) {
if(isFull()){
return false;
}
elem[rear] = value;
rear = (rear+1) % elem.length;
//每次入队后，rear都要++，但是当你是length-1s时，你再加就得变成下标0了，此时
//利用这个公式
return true;
}/**
* 出队
* @param
* @return
*/
public boolean deQueue() {
if(isEmpty()){
return false;
}
//每次出队也是一样，当你front出到length-1的时候，你再出本应该++，此时你需要出到下标0，但是此时front++变成length
//所以还是得用这个公式
front = (front+1) % elem.length;
return true;
}/**
* 得到队头元素
* @return
*/
public int Front() {
if(isEmpty()){
return -1;
}
return elem[front];
}public int Rear() {
if(isEmpty()){
return -1;
}
int index = -1;
//返回队尾的元素（浪费一个空间的方式），你最后一个元素应该是rear-1的位置，但是当你是rear = 0，此时你应该是length-1下标的值，也是去判断一下
if(rear== 0 ){
index = elem.length-1;
}else{
index = rear-1;
}
return elem[index];
}public boolean isEmpty() {
return rear == front;
}public boolean isFull() {
//rear的下一个是不是front ，本来就浪费了一个空间，那么必有一个空间是空着，而且front和rear是夹在中间才是慢的，建议参考上面第三种的图去理解
if((rear+1) %elem.length == front){
return true;
}else{
return false;
}
}
}
用两个队列去实现一个栈 用两个队列去实现一个栈
class MyStack {
//该题也是利用两个队列，现将数据放到不为空的队列中（如果都为空的话，先指定一个）在出元素的时候，将不为空的栈中出元素放到空栈中，但是只出size-1个，最后一个使我们要从栈中出来的，所以我们不放到第二个栈中，而是直接出出来即可。那么就实现了栈的出元素，peek的话，同样的道理，也可以都放到第二个栈中，然后返回最后一次放入的数据即可
//用两个队列去实现栈
private Queue qu1;
private Queue 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 size = qu1.size();
int val = -1;
for(int i = 0;
i-1;
i++){
val = qu1.poll();
qu2.offer(val);
}
return qu1.poll();
}
if(!qu2.isEmpty()){
int size = qu2.size();
int val = -1;
for(int i = 0;
i-1;
i++){
val = qu2.poll();
qu1.offer(val);
}
return qu2.poll();
}
return -1;
}public int top() {
if(empty()){
return -1;
}if(!qu1.isEmpty()){
int size = qu1.size();
int val = -1;
for(int i = 0;
i;
i++){
val = qu1.poll();
qu2.offer(val);
}
return val;
}
if(!qu2.isEmpty()){
int size = qu2.size();
int val = -1;
for(int i = 0;
i;
i++){
val = qu2.poll();
qu1.offer(val);
}
return val;
}
return -1;
}public boolean empty() {
return qu1.isEmpty() && qu2.isEmpty();
}
}
用栈实现队列 用栈实现队列
class MyQueue {
//基本思路就是将数据都放到栈1，先去判断栈2空不空，为空的话就不放，其实最开始我没搞懂为啥要判断栈2空不空，后来一调试发现，如果你没有这个条件的话，栈2本来就是出元素的，如果你不为空还继续放进去的话，你栈顶的元素就是后面的元素，前面的元素还没出出去，所以你得保证你前面的元素出完了你才能继续放后面的元素
Stack stack1 ;
Stack stack2 ;
public MyQueue() {
stack1 = new Stack<>();
stack2 = new Stack<>();
}public void push(int x) {
stack1.push(x);
}public int pop() {
if(empty()){
return -1;
}
while(!stack1.isEmpty()){
int val = stack1.pop();
stack2.push(val);
}
return stack2.pop();
}public int peek() {
if(empty()){
return -1;
}
if(stack2.isEmpty()){
while(!stack1.isEmpty()){
int val = stack1.pop();
stack2.push(val);
}
}
return stack2.peek();
}public boolean empty() {
return stack1.isEmpty() && stack2.isEmpty();
}
}
栈的出入元素用的是push、pop
而队列的出入元素是offer、poll 上面的截图有的
双端队列 双端队列（deque）是指允许两端都可以进行入队和出队操作的队列，deque 是 “double ended queue” 的简称。
那就说明元素可以从队头出队和入队，也可以从队尾出队和入队
}
return stack2.pop();
}
public int peek() {
if(empty()){
return -1;
}
if(stack2.isEmpty()){
while(!stack1.isEmpty()){
int val = stack1.pop();
stack2.push(val);
}
}
return stack2.peek();
}public boolean empty() {
return stack1.isEmpty() && stack2.isEmpty();
}
}
------==栈的出入元素用的是push、pop====而队列的出入元素是offer、poll上面的截图有的==## 双端队列双端队列（deque）是指允许两端都可以进行入队和出队操作的队列，deque 是 “double ended queue” 的简称。
那就说明元素可以从队头出队和入队，也可以从队尾出队和入队推荐阅读
- 数据结构|第一章.概论
- Java中取余(%)运算规则
- 计算机视觉算法工程师|算法工程师0——算法工程师学习进阶路线
- 编程语言|我的阿里巴巴盒马上岸总结
- java|程序员2009精华本(china-pub首发)--百期后的新起点
- 笔记|UA到底是什么
- java|六面天猫，已拿 offer，我的面经复盘总结，大厂真的有那么难进吗（）
- 程序人生|开年无情被裁，还好我未雨绸缪，3天拿下新offer，薪资可观
- php|php学习笔记——PHP 概述