数据结构之栈和队列

一、栈

1、栈的概念

是一种线性表，具有后进先出的特点。只能在固定的一段进行数据的插入和删除，进行元素插入和删除的一端称为栈顶，另一端称为栈底。

2、栈的使用

3、栈实例

（1）逆序打印链表

eg：链表为1->2->3->4->5

逆序打印：5->4->3->2->1

递归方式：

void printList(ListNode head){
    if(null!=head){
       printList(head.next);
       System.out.print(head.val+" ");
    }
}

栈方式：

Stack<Integer> stack=new Stack<>();
while(head!=null){
   stack.push(head.val);
   head=head.next;
}
while(!stack.empty()){
    System.out.print(stack.pop()+" ");
}

（2）括号匹配

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

（3）逆波兰表达式求值

class Solution {
    public int evalRPN(String[] tokens) {
        int n=tokens.length;
        Stack<Integer> s=new Stack<>();
        for(int i=0;i<n;i++){
            String temp=tokens[i];
            if(!(temp.equals("+")||temp.equals("-")||temp.equals("*")||temp.equals("/"))){
                s.push(Integer.valueOf(temp));
            }else{
                int b=s.pop();
                int a=s.pop();
                if(temp.equals("+")){
                    s.push(a+b);
                }else if(temp.equals("-")){
                    s.push(a-b);
                }else if(temp.equals("*")){
                    s.push(a*b);
                }else{
                    s.push(a/b);
                }
            }
        }
        return s.pop();
    }
}

（4）出栈入栈次序匹配

 public boolean IsPopOrder (int[] pushV, int[] popV) {
        // write code here
        Stack<Integer> s=new Stack<>();
        int n=pushV.length;
        int j=0;
        for(int i=0;i<n;i++){
            s.push(pushV[i]);
            while(!s.empty()&&s.peek()==popV[j]){
                s.pop();
                j++;
            }
        }
        return j==n;
    }

（5）最小栈

class MinStack {
    Stack<Integer> s1;
    Stack<Integer> s2;
    public MinStack() {
        s1=new Stack<>();
        s2=new Stack<>();
    }
    
    public void push(int val) {
        s1.push(val);
        if(s2.empty()){
            s2.push(val);
        }else{
            if(s2.peek()>=val){
                s2.push(val);
            }
        }
    }
    
    public void pop() {
        int a=s1.pop();
        if(!s2.empty()&&s2.peek()==a){
            s2.pop();
        }
    }
    
    public int top() {
        return s1.peek();
    }
    
    public int getMin() {
        if(s2.empty()){
            return -1;
        }else{
            return s2.peek();
        }
    }
}

（6）栈、虚拟机栈、栈帧有什么区别？

栈：是一种线性表，具有后进先出的特点；

虚拟机栈：jvm划分的一块内存；

栈帧：调用方法的时候会在虚拟机当中给这个方法开辟一块内存。

二、队列

1、队列的概念

是一种线性表，具有先进先出的特点。只能在固定的一段进行数据的插入和删除，进行元素插入一端称为队尾，另一端称为队头。

2、队列的使用

注意：Queue是一个接口，在实例化对象时，使用LinkedList实例化对象，因为LinkedList实现了Queue接口。

3、队列实例

（1）循环队列

区分空与满

①记录长度标记

放入一个元素，长度+1；取出一个元素，长度-1；长度>队列最长长度，已满；长度<=0，已空；

该方法操作简单，就不再详细编写代码。

②保留一个位置

class MyCircularQueue {
    int[] elem;
    int front;
    int rear;
    public MyCircularQueue(int k) {
        elem=new int[k+1];
    }
    
    public boolean enQueue(int value) {
        if(isFull()){
            return false;
        }else{
            elem[rear]=value;
            rear=(rear+1)%elem.length;
            return true;
        }
    }
    
    public boolean deQueue() {
        if(isEmpty()){
            return false;
        }else{
            front=(front+1)%elem.length;
            return true;
        }
    }
    
    public int Front() {
        if(isEmpty()){
            return -1;
        }else{
            return elem[front];
        }
    }
    
    public int Rear() {
        if(isEmpty()){
            return -1;
        }else{
            int index=(rear==0)?elem.length-1:rear-1;
            return elem[index];
        }
    }
    
    public boolean isEmpty() {
        return front==rear;
    }
    
    public boolean isFull() {
        return (rear+1)%elem.length==front;
    }
}

（2）用队列实现栈

队列：先进先出；栈：先进后出

两个队列一模一样：进出队列变换。

class MyStack {
    Queue<Integer> q1;
    Queue<Integer> q2;
    public MyStack() {
        q1=new LinkedList<Integer>();
        q2=new LinkedList<Integer>();
    }
    
    public void push(int x) {
        if(q1.isEmpty()){
            q2.offer(x);
        }else{
            q1.offer(x);
        }
    }
    
    public int pop() {
        if(empty()){
            return -1;
        }
        int temp=0;
        if(q1.isEmpty()){
            while(!q2.isEmpty()){
                temp=q2.poll();
                if(!q2.isEmpty()){
                   q1.offer(temp);
                }
            }
        }else{
            while(!q1.isEmpty()){
                temp=q1.poll();
                if(!q1.isEmpty()){
                    q2.offer(temp);
                }
            }
        }
        return temp;
    }
    
    public int top() {
        if(empty()){
            return -1;
        }
        int temp=0;
         if(q1.isEmpty()){
            while(!q2.isEmpty()){
                temp=q2.poll();
                q1.offer(temp);
            }
        }else{
            while(!q1.isEmpty()){
                temp=q1.poll();           
                q2.offer(temp);                
            }
        }
        return temp;
    }
    
    public boolean empty() {
        return q1.isEmpty()&&q2.isEmpty();
    }
}

（3）用栈实现队列

两个栈不一样，一个栈固定为入队列，一个栈固定为出队列。

class MyQueue {
    Stack<Integer> s1;
    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.empty()){
            while(!s1.empty()){
                s2.push(s1.pop());
            }
        }
        return s2.pop();
    }
    
    public int peek() {
        if(empty()){
            return -1;
        }
        if(s2.empty()){
            while(!s1.empty()){
                s2.push(s1.pop());
            }
        }
        return s2.peek();
    }
    
    public boolean empty() {
        return s1.empty()&&s2.empty();
    }
}

4、双端队列（Deque）

允许两端都可以进行入队和出队操作。Deque是一个接口，实例化对象使用LinkedList实现。