一、栈

先进后出

1.常用方法

方法	作用	含义
push(E item)	入栈	把元素压进栈里
pop()	出栈	取出栈顶元素，并且删掉
peek()	取栈顶	只看栈顶元素，不删除
empty()	判断栈是否为空	空返回 true，不为空 false
size()	获取栈中元素个数	看现在栈里有几个数
search(Object o)	查找元素位置	从栈顶开始数位置，找不到返回 -1

2.模拟实现

public class MyStack {

    public int[]elem;
    public int usedSize;

    public MyStack(){
        this.elem=new int[10];
    }

    public void push(int val){
        if(isFull()){
            //扩容
            elem= Arrays.copyOf(elem,2*elem.length);
        }
        elem[usedSize++]=val;
    }

    public boolean isFull(){
        return usedSize ==elem.length;
    }

    public int pop(){
        if(empty()){
            return -1;
        }
        return elem[--usedSize];
    }

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

    public int peek(){
        return elem[usedSize-1];
    }

    public static void main(String[] args) {

        MyStack stack=new MyStack();

        stack.push(1);
        stack.push(1);
        stack.push(2);
        stack.push(3);
        stack.push(3);
        System.out.println(stack);

        System.out.println(stack.pop());

        stack.push(5);
        System.out.println(stack);

        System.out.println(stack.peek());
        System.out.println(stack.peek());

    }
}

3.应用场景

牵扯到顺序的问题可以尝试使用栈

（1）逆波兰式求值

package MyStack;

import java.util.Stack;

//逆波兰表达式求值
//先弹出的是 右操作数，后弹出的是 左操作数
public class test1 {
    class Solution {
        public int evalRPN(String[] tokens) {
            Stack<Integer>stack=new Stack<>();
            for (String tmp : tokens) {
                if (!isOperation(tmp)) {
                    Integer val = Integer.valueOf(tmp);
                    stack.push(val);
                } else {
                    Integer val1 = stack.pop();
                    Integer val2 = stack.pop();
                    switch (tmp) {
                        case "+":
                            stack.push(val2 + val1);
                            break;
                        case "-":
                            stack.push(val2 - val1);
                            break;
                        case "*":
                            stack.push(val2 * val1);
                            break;
                        case "/":
                            stack.push(val2 / val1);
                            break;
                    }
                }
            }
            return stack.pop();
        }
        public boolean isOperation(String s){
            if(s.equals("+")||s.equals("-")||s.equals("*")||s.equals("/")){
                return true;
            }
            return false;
        }
    }
}

（2）括号匹配

package MyStack;

import java.util.Stack;

//括号匹配
public class test2 {

    class Solution {
        public boolean isValid(String s) {
            Stack<Character>stack=new Stack<>();
            for(int i=0;i<s.length();i++){
                char c=s.charAt(i);
                //左括号入栈
                if(c=='('||c=='['||c=='{'){
                    stack.push(c);
                }else{
                    //右括号
                    if(stack.empty()){
                        //栈空)(((
                        return false;
                    }else{
                        char cl=stack.peek();
                        //当前这对括号匹配
                        if(cl=='('&&c==')'||cl=='['&&c==']'||cl=='{'&&c=='}'){
                            stack.pop();
                        }else{
                            return false;
                        }
                    }
                }
            }
            return stack.empty();
        }
    }

}

（3）栈的压入、弹出顺序

package MyStack;

import java.util.Stack;

public class test3 {
    public class Solution {
        /**
         * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
         *
         *
         * @param pushV int整型一维数组
         * @param popV int整型一维数组
         * @return bool布尔型
         */
        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]);
                while(j<popV.length&&!stack.empty()&&stack.peek()==popV[j]){
                    stack.pop();
                    j++;
                }
            }
            return stack.empty();
        }
    }
}

（4）最小栈

集合里存 Integer 包装类，绝对不要直接用 == 比较值！

正确做法：①用 int 变量接收（自动拆箱），再比较②用 equals() 比较

package MyStack;

import java.util.Stack;

//最小栈
public class test4 {
    class MinStack {

        Stack<Integer>stack;
        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;
            }
//集合里存 Integer 包装类，绝对不要直接用 == 比较值！
            int popVal= stack.pop();
            if(popVal==minStack.peek()){
                minStack.pop();
            }
        }

        public int top() {
            if(stack.empty()){
                return -1;
            }
            return stack.peek();
        }

        public int getMin() {
            if(minStack.empty()){
                return -1;
            }
            return minStack.peek();
        }
    }

}

4.LinkedList实现栈

package MyStack;

import java.util.LinkedList;
import java.util.Stack;

public class test {

    public static void main(String[] args) {
        //双向链表实现栈
        LinkedList<Integer>stack=new LinkedList<>();
        stack.push(1);//addfirst入栈
        stack.push(2);
        stack.push(3);
        stack.push(4);
        System.out.println(stack);
        stack.pop();//头删出栈
        System.out.println(stack);
    }

}

二、队列

先进先出

1.常用方法

方法	作用	含义
offer(e)	入队	往队尾加元素
poll()	出队	删掉队首并返回，队空返回 null
peek()	取队首	只看队首不删除，队空返回 null

package MyQueue;

import java.util.LinkedList;
import java.util.Queue;

public class test {
    public static void main(String[] args) {
        Queue<Integer> queue=new LinkedList<>();
        queue.offer(1);//尾插
        queue.offer(2);
        queue.offer(3);
        System.out.println(queue);

        System.out.println(queue.poll());//头删
        System.out.println(queue);
        System.out.println(queue.peek());
        System.out.println(queue.peek());
    }
}

2.模拟实现

package MyQueue;

import java.util.LinkedList;
import java.util.Queue;

public class MyQueue {
    static class ListNode{
        public int val;
        public ListNode prev;
        public ListNode next;

        public ListNode(int val){
            this.val=val;
        }
    }
    public ListNode head;
    public ListNode last;

    //尾插
    public void offer(int val){
        ListNode node=new ListNode(val);
        if(head==null){
            head=last=node;
        }else{
            last.next=node;
            node.prev=last;
            last=last.next;
        }
    }

    //头删
    public int poll(){
        //空
        if(head==null){
            return -1;
        }

        //一个节点
        int ret= head.val;
        if(head.next==null){
            head=last=null;
        }else{
            //多个节点
            head=head.next;
            head.prev=null;
        }
        return ret;
    }

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

    public boolean isEmpty(){
        return head==null;
    }

    public static void main(String[] args) {
        MyQueue queue=new MyQueue();
        queue.offer(1);//尾插
        queue.offer(2);
        queue.offer(3);

        System.out.println(queue.poll());//头删
        System.out.println(queue.peek());
        System.out.println(queue.peek());
    }

}

3.双端队列Deque

Deque 是 Queue（普通队列）的子接口，常用实现类是LinkedList（底层是双向链表）、ArrayDeque（底层是循环数组）

（1）实现循环队列

package MyQueue;

public class MyCircleQueue {

    //浪费一个空间
    class MyCircularQueue {
        public int[]elem;
        public int first;
        public int last;

        public MyCircularQueue(int k) {
            elem=new int[k+1];
        }

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

        //删除
        public boolean deQueue() {
            if(isEmpty()){
                return false;
            }
            first=(first+1)%elem.length;
            return true;
        }

        //获取头元素
        public int Front() {
            if(isEmpty()){
                return -1;
            }
            return elem[first];
        }

        //获取尾元素
        public int Rear() {
            if(isEmpty()){
                return -1;
            }
            int index=(last==0)?elem.length-1:last-1;
            return elem[index];
        }

        public boolean isEmpty() {
            return first==last;
        }

        public boolean isFull() {
            return (last+1)%elem.length==first;
        }
    }

}

（2）双端队列

两边都能进出

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

4.面试题

（1）队列实现栈

入栈：若两个队列都为空，把数据放到第一个队列中；谁非空就把元素放到哪个队列里

出栈：把第一个队列的n-1个元素放到第二个队列中，最后剩下的一个元素就是要出栈的元素

package MyQueue;

import java.util.LinkedList;
import java.util.Queue;

//队列实现栈
class MyStack {
    public Queue<Integer>queue1;
    public Queue<Integer> queue2;

    public MyStack() {
        queue1=new LinkedList<>();
        queue2=new LinkedList<>();
    }
    
    public void push(int x) {
        if(empty()){
            queue1.offer(x);
            return;
        }
        if(!queue1.isEmpty()){
            queue1.offer(x);
        }else{
            queue2.offer(x);
        }
    }
    
    public int pop() {
        if(empty()){
            return -1;
        }
        if(!queue1.isEmpty()){
            int size=queue1.size();
            for(int i=0;i<size-1;i++){
                queue2.offer(queue1.poll());
            }
            return queue1.poll();
        }else{
            int size=queue2.size();
            for(int i=0;i<size-1;i++){
                queue1.offer(queue2.poll());
            }
            return queue2.poll();
        }
    }

    //获取栈顶元素
    public int top() {
        if(empty()){
            return -1;
        }
        if(!queue1.isEmpty()){
            int size=queue1.size();
            int ret=-1;
            for(int i=0;i<size;i++){
                ret=queue1.poll();
                queue2.offer(ret);
            }
            return ret;
        }else{
            int size=queue2.size();
            int ret=-1;
            for(int i=0;i<size;i++){
                ret=queue2.poll();
                queue1.offer(ret);
            }
            return ret;
        }
    }
    
    public boolean empty() {
        return queue1.isEmpty()&&queue2.isEmpty();
    }
}

（2）栈实现队列

入列：全部放到栈1

出列：把栈1中的元素全部放到栈2，出栈2中的元素；若栈2为空，重复入列出列的操作

package MyQueue;

import java.util.Stack;

public class StackToQueue {
    class MyQueue {
        Stack<Integer> stack1;
        Stack<Integer>stack2;
        public MyQueue() {
            stack1=new Stack<>();
            stack2=new Stack<>();
        }

        public void push(int x) {
            stack1.push(x);
        }

        public int pop() {
            if(empty()){
                return -1;
            }

            if(stack2.isEmpty()){
                int size=stack1.size();
                for(int i=0;i<size;i++){
                    stack2.push(stack1.pop());
                }
            }

            return stack2.pop();
        }

        public int peek() {
            if(empty()){
                return -1;
            }

            if(stack2.isEmpty()){
                int size=stack1.size();
                for(int i=0;i<size;i++){
                    stack2.push(stack1.pop());
                }
            }

            return stack2.peek();
        }

        public boolean empty() {
            return stack1.isEmpty()&& stack2.empty();
        }
    }

}