堆疊和佇列

堆疊

堆疊的概念

堆疊：一種特殊的線性表，其只允許在固定的一端進行插入和洗掉元素操作，進行資料插入和洗掉操作的一端稱為堆疊頂，另一端稱為堆疊底，堆疊中的資料元素遵守后進先出LIFO（Last In First Out）的原則，
壓堆疊：堆疊的插入操作叫做進堆疊/壓堆疊/入堆疊，入資料在堆疊頂，
出堆疊：堆疊的洗掉操作叫做出堆疊，出資料在堆疊頂
如圖：
入堆疊時：


出堆疊時：

堆疊的實作

實作堆疊一般有兩種方法一個為利用順序表實作另一個為鏈表實作，在實際情況下，我們使用順序表實作堆疊

public class MyStack {
    public int[] elem;
    public int usedSize;
    public MyStack(){
        this.elem=new int[10];
    }
    //判斷堆疊是否為空
    public boolean isFull() {
        if(usedSize==this.elem.length){
            return true;
        }
        return false;
    }
    //將元素插入堆疊當中
    public void push(int item) {
        if(isFull()){
        //如果堆疊已經填滿，則將堆疊進行2倍擴容
            this.elem= Arrays.copyOf(this.elem,2*this.elem.length);
        }
        this.elem[this.usedSize]=item;
        this.usedSize++;
    }
    public boolean empty() {
    //判斷堆疊是否為空，是則回傳true,不是則回傳false
        return this.usedSize==0;
    }
    public int pop() throws RuntimeException{
        if (empty()){
        //如果堆疊為空則拋出例外
            throw new RuntimeException("堆疊空了");
        }
        //回傳堆疊頂元素并從堆疊中洗掉堆疊頂元素
        return this.elem[--this.usedSize];
    }
    public int peek() {
        if (empty()){
        //如果堆疊為空則拋出例外
            throw new RuntimeException("堆疊空了");
        }
        //回傳堆疊頂元素但不從堆疊中洗掉堆疊頂元素
        return this.elem[this.usedSize-1];
    }
}

注意：在java程式中，可以直接使用堆疊
格式：
Stack 變數名=new Stack<>()

堆疊的面試題

括號匹配

題解：
該題考查對堆疊掌握程度，為了匹配有效括號，我們可以使用使用一個堆疊，將遇到的左括號都放入堆疊中，遇到右括號就取出堆疊頂元素進行比較，如果匹配則洗掉堆疊頂，如果不匹配則回傳false;回圈結束后再判斷堆疊是否為空如果為空則回傳true，相反則回傳false;

class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack=new Stack<>();
        char[] ch=s.toCharArray();
        for(char ch1:ch){
            switch(ch1){
                case '(':
                case '{':
                case '[':
                stack.push(ch1);
                break;
                case ')':
                if(!stack.isEmpty()&&stack.peek()=='('){
                    stack.pop();
                }
                else{
                    return false;
                }
                break;
                case ']':
                if(!stack.isEmpty()&&stack.peek()=='['){
                    stack.pop();
                }
                else{
                    return false;
                }
                break;
                case '}':
                if(!stack.isEmpty()&&stack.peek()=='{'){
                    stack.pop();
                }
                else{
                    return false;
                }
                break;
            }
        }
        if(stack.isEmpty()){
            return true;
        }
        return false;
    }
}

逆波蘭運算式求值

該題考查我們對前綴演算法和中綴演算法的熟悉程度，使用一個堆疊，將數字放入其中當遇到‘+’，‘-’，‘*’，‘/’,則取出堆疊頂的兩個元素，與相應的運算子進行操作
再將新獲得的數放入堆疊中，

class Solution {
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();
        int n = tokens.length;
        for (String token:tokens) {
            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:
                    break;
                }
            }
        }
        return stack.pop();
    }
    public boolean isNumber(String token) {
        return !("+".equals(token) || "-".equals(token) || "*".equals(token) || "/".equals(token));
    }
}

佇列

佇列的概念

佇列：只允許在一端進行插入資料操作，在另一端進行洗掉資料操作的特殊線性表，佇列具有先進先出FIFO(First In First Out) 入佇列：進行插入操作的一端稱為隊尾（Tail/Rear） 出佇列：進行洗掉操作的一端稱為隊頭（Head/Front）
如圖：

為了實作佇列，可以采用陣列和鏈表的結構實作，使用鏈表的結構實作更優一些，因為如果使用陣列的結構，出佇列在陣列頭上出資料，效率會比較低，

class Node {
    public int data;
    public Node next;
    public Node(int data) {
        this.data = data;
    }
}
public class MyQueueLinked {
    private Node front;
    private Node rear;
    private int usedSize;
    //插入元素進入佇列中
    public void offer(int val) {
        Node node=new Node(val);
        if (front==null){
            this.front=node;
            this.rear=node;
        }
        else {
            this.rear.next=node;
            this.rear=node;
        }
        this.usedSize++;
    }
    public int size() {
        return this.usedSize;
    }
    public boolean isEmpty() {
        return this.usedSize == 0;
    }
    //回傳堆疊頭元素，并從佇列中洗掉
    public int poll() {
        if (isEmpty()) {
            throw new RuntimeException("佇列為空！");
        }
        int val=this.front.data;
        if(this.front.next == null) {
            this.front = null;
            this.rear = null;
        }
        else {
            this.front=this.front.next;
        }
        this.usedSize--;
        return val;
    }
    //回傳堆疊頭元素，但不從佇列中洗掉
    public int peek(){
        if (isEmpty()) {
            throw new RuntimeException("佇列為空！");
        }
        return this.front.data;
    }
}

回圈佇列

實際中我們有時還會使用一種佇列叫回圈佇列，如作業系統課程講解生產者消費者模型時可以就會使用回圈佇列，環形佇列通常使用陣列實作，

回圈佇列和普通佇列一樣：隊尾加元素，隊頭輸出元素

如何區分回圈佇列的空與滿

回圈佇列一般會保留一個位置以便于判斷是否滿了
如圖：

當Q.front==Q.rear時，此時回圈佇列為空，

當(Q.rear+1)%陣列的長度=Q.front時則回圈佇列為滿

佇列的面試題

分條件出堆疊

由題我們可以創建兩個佇列a,b,一個佇列a用于先放元素，第二個佇列b用于存盤從a中洗掉的元素最后回傳佇列b.

import java.util.*;

public class CatDogAsylum {
    public ArrayList<Integer> asylum(int[][] ope) {
        // write code here
        ArrayList<Integer> one=new ArrayList<>();
        ArrayList<Integer> two=new ArrayList<>();
        for (int i = 0; i < ope.length; i++) {
            if (ope[i][0]==1){
                one.add(ope[i][0]*ope[i][1]);
            }
            else {
                if (ope[i][1]==1){
                    int size= one.size();
                    for(int j=0;j<size;j++){
                        if(one.get(j)>0){
                            two.add(one.remove(j));
                            break;
                        }
                    }
                }
                else if(ope[i][1]==0){
                    two.add(one.remove(0));
                }
                else {
                    int size= one.size();
                    for(int j=0;j<size;j++){
                        if(one.get(j)<0){
                            two.add(one.remove(j));
                            break;
                        }
                    }
                }
            }
        }
        return two;
    }
}

最近的請求次數

這題考的是我們對題的理解，大概意思就是把t放入佇列中，再判斷佇列中的值是不是在區間[t-3000,t];如果有值不在這個范圍則將他從佇列中洗掉，最后回傳佇列中還有多少個元素，

class RecentCounter {
    Queue<Integer> q;
    public RecentCounter() {
        this.q=new LinkedList<>();
    }
    
    public int ping(int t) {
        q.add(t);
        while(q.peek()<t-3000){
            q.poll();
        }
        return q.size();
    }
}