算法隊列與棧—Java版

隊列、雙向隊列、棧 — ArrayDeque

使用雙向隊列ArrayDeque可以完成以上三種資料結構。隊列的操作包括：入隊、出隊、傳回隊首元素、傳回隊尾元素、删除隊首元素、删除隊尾元素、判斷空、傳回隊列長度。雙向隊列包括：首尾入隊、首尾出隊、傳回首尾元素、删除首尾元素、判斷空、傳回隊列長度。棧包括：入棧、出棧、傳回棧頂元素、傳回棧尾元素、判斷空，傳回棧長度。

雙向隊列：

addFirst(E e) 在此deque前面插入指定的元素。
addLast(E e) 在此deque的末尾插入指定的元素。
getFirst() 檢索，但不删除，這個deque的第一個元素。如果此deque為空，則報錯。
getLast() 檢索，但不删除，這個deque的最後一個元素。如果此deque為空，則報錯。
removeFirst() 檢索并删除此deque的第一個元素。如果此deque為空，則報錯。
removeLast() 檢索并删除此deque的最後一個元素。如果此deque為空，則報錯。
size() 傳回此deque中的元素數。
contains(Object o) 如果此deque包含指定的元素，則傳回 true 。
clear() 從這個deque中删除所有的元素。

@Test
 public void my_queue(){
        ArrayDeque<Integer> arrdeq = new ArrayDeque<>();
        arrdeq.add(3);
        arrdeq.add(9);
        arrdeq.add(0);

        arrdeq.addFirst(1);
        arrdeq.addLast(2);

        boolean con = arrdeq.contains(9);
        Integer peekf = arrdeq.peekFirst(); //傳回隊頭元素,如果此deque為空，則報錯。
        Integer peekl = arrdeq.peekLast();//傳回隊尾元素,如果此deque為空，則報錯。

        Integer pf = arrdeq.pollFirst();//隊頭元素出隊并傳回,如果此deque為空，則報錯。
        Integer pl = arrdeq.pollLast();//隊尾元素出隊并傳回,如果此deque為空，則報錯。

        boolean empty = arrdeq.isEmpty();
        arrdeq.clear();
    }

Note: 隻要掌握了上面的雙向隊列的操作，那麼棧和隊列的操作也就會了。注意，最好使用如果隊列為空報錯的操作而不使用傳回null的操作，因為，為空報錯對于算法是好的，而傳回null有時候很難發現錯誤！

堆（優先隊列）— PriorityQueue

add(E e) 将指定的元素插入到此優先級隊列中。
peek() 檢索但不删除此隊列的頭，如果此隊列為空，則傳回 null 。
poll() 檢索并删除此隊列的頭，如果此隊列為空，則傳回 null 。
remove(Object o) 從該隊列中删除指定元素的單個執行個體（如果存在）。
size() 傳回此集合中的元素數。
toArray() 傳回一個包含此隊列中所有元素的數組。
contains(Object o) 如果此隊列包含指定的元素，則傳回 true 。

@Test
public void my_priorityQueue(){
        // 預設小根堆，如果要大根堆，隻需要乘以-1即可，然後結果再恢複
        PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
        pq.add(9);
        pq.add(1);
        pq.add(4);

        Integer peek = pq.peek();
        Integer poll = pq.poll();
        boolean res = pq.remove(1);
    }

232. 用棧實作隊列

此題，使用基本棧實作隊列，需要兩個棧，一個為輸入棧，當輸入的時候按順序入棧即可；另外一個為輸出棧，需要把輸入棧裡的元素全部出棧到輸出棧中，即倒置元素到輸出棧中，如下圖所示（圖檔來源：代碼随想錄）；

算法隊列與棧—Java版

import java.util.ArrayDeque;
public class MyQueue {
    ArrayDeque<Integer> stack_in;
    ArrayDeque<Integer> stack_out;
    public MyQueue() {
        stack_in = new ArrayDeque<>();
        stack_out = new ArrayDeque<>();
    }

    public void push(int x) {
        stack_in.addLast(x);
    }
    public int pop() {
        // 如果輸出棧還有元素，先用出棧
        if(!stack_out.isEmpty()){
            Integer p = stack_out.removeLast();
            return p;
        }
        //else 否則
        while (!stack_in.isEmpty()){
            Integer last = stack_in.removeLast();
            stack_out.addLast(last);
        }
        Integer p = stack_out.removeLast();
        return p;
    }

    public int peek() {
        // 如果輸出棧還有元素，先用出棧
        if(!stack_out.isEmpty()){
            Integer p = stack_out.getLast();
            return p;
        }
        //else 否則
        while (!stack_in.isEmpty()){
            Integer last = stack_in.removeLast();
            stack_out.addLast(last);
        }
        Integer p = stack_out.getLast();
        return p;
    }
    public boolean empty() {
        if(stack_out.isEmpty() && stack_in.isEmpty()){
            return true;
        }
        return false;
    }
}

225. 用隊列實作棧

思路，使用兩個隊列，當入隊時，向非空的一個隊列中入隊，另外一個隊列作為輔助隊列用于存儲擋在前面的元素。兩個隊列循環作為輔助隊列使用，即空的那個即為輔助隊列。注明：圖檔來源代碼随想錄！

算法隊列與棧—Java版

import java.util.ArrayDeque;
public class MyStack {
    ArrayDeque deque1;
    ArrayDeque deque2;
    public MyStack() {
        deque1 = new ArrayDeque<Integer>();
        deque2 = new ArrayDeque<Integer>();
    }

    public void push(int x) {
        if(!deque1.isEmpty()){
            deque1.addLast(x);
        }else if(!deque2.isEmpty()){
            deque2.addLast(x);
        }else {
            deque1.addLast(x);
        }
    }

    public int pop() {
        ArrayDeque<Integer> deque = null;
        ArrayDeque<Integer> helpdeq = null;
        if(!deque1.isEmpty()){
            deque = deque1;
            helpdeq = deque2;
        }
        if(!deque2.isEmpty()){
            deque = deque2;
            helpdeq = deque1;
        }
        while (deque.size()>1){
            Integer value = deque.removeFirst();
            helpdeq.addLast(value);
        }
        // 當deque.size()==1
        Integer p = deque.removeFirst();
        return p;
    }

    public int top() {
        int pop = pop();
        push(pop);
        return pop;
    }

    public boolean empty() {
        if(deque2.isEmpty() && deque1.isEmpty()){
            return true;
        }else {
            return false;
        }
    }
}

LeetCode練習

20. 有效的括号
1047. 删除字元串中的所有相鄰重複項
以上兩題非常簡單，直接套用棧就行。

150. 逆波蘭表達式求值

思路：此題需要一個棧儲存數字，當讀取一個符号發現數值棧中大于兩個數字則兩個數字出棧進行運算後結果再入棧。

import java.util.ArrayDeque;
public class lc150 {
    public boolean isNumber(String s){
        if(s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/")){
            return false;
        }else {
            return true;
        }
    }

    public int evalRPN(String[] tokens) {
        ArrayDeque<Integer> stack = new ArrayDeque<>();
        for (int i = 0; i < tokens.length; i++) {
            String s = tokens[i];
            if(isNumber(s)){
                int value = Integer.parseInt(s);
                stack.addLast(value);
            }else {
                if(stack.size()>=2){
                    int v2 = stack.removeLast();
                    int v1 = stack.removeLast();
                    switch (s){
                        case "+":{
                            stack.addLast(v1+v2);
                            break;
                        }
                        case "-":{
                            stack.addLast(v1-v2);
                            break;
                        }
                        case "*":{
                            stack.addLast(v1*v2);
                            break;
                        }
                        case "/":{
                            stack.addLast(v1/v2);
                            break;
                        }
                    }
                }
            }
        }
        return stack.getLast();
    }
}

347. 前 K 個高頻元素

思路：先統計，再使用優先隊列。

public int[] topKFrequent(int[] nums, int k) {
        TreeMap<Integer, Integer> map = new TreeMap<>();
        PriorityQueue<Map.Entry<Integer, Integer>> pq = new PriorityQueue<>(new Comparator<Map.Entry<Integer, Integer>>() {
            @Override
            public int compare(Map.Entry<Integer, Integer> o1, Map.Entry<Integer, Integer> o2) {
                return o2.getValue()-o1.getValue();
            }
        });
        for(int a: nums){
            //  map.put(num,map.getOrDefault(num,0)+1);
            if(map.containsKey(a)){
                map.replace(a,map.get(a)+1);
            }else {
                map.put(a,1);
            }
        }
        Set<Map.Entry<Integer, Integer>> entries = map.entrySet(); //轉為集合
        ArrayList<Map.Entry<Integer, Integer>> arr = new ArrayList<>(entries); //轉為數組

        for (int i = 0; i < arr.size(); i++) {
            pq.add(arr.get(i));
        }
//        Collections.sort(arr, new Comparator<Map.Entry<Integer, Integer>>() {
//            @Override
//            public int compare(Map.Entry<Integer, Integer> o1, Map.Entry<Integer, Integer> o2) {
//                return o1.getValue()-o2.getValue();
//            }
//        });
        int[] res = new int[k];
        for (int i = 0; i < k; i++) {
            Map.Entry<Integer, Integer> poll = pq.poll();
            res[i] = poll.getKey();
        }
        return res;
    }

735. 行星碰撞

public int[] asteroidCollision(int[] asteroids) {
        ArrayDeque<Integer> stack = new ArrayDeque<>();
        for(int a : asteroids){
            if(stack.isEmpty() || (stack.getLast()<0 && a>0) || stack.getLast()*a>0){
                // 如果棧為空，或者<-- -->這樣的方向，或者同向，直接加進來，因為這些都噴不到
                stack.addLast(a);
            }else {
                while(!stack.isEmpty() && (stack.getLast()>0 && a<0) && Math.abs(stack.getLast())<Math.abs(a)){
                    stack.pollLast();
                }
                //因為空結束，同向結束
                if(stack.isEmpty()||stack.getLast()*a>0){
                    stack.addLast(a);
                }
                //因為品質相等結束，條件要求會碰才能消除
                else if(Math.abs(stack.getLast())==Math.abs(a) && (stack.getLast()>0 && a<0)){
                    stack.pollLast();
                }
            }
        }
        int[] res = new int[stack.size()];
        int i=0;
        while (!stack.isEmpty()){
            res[i] = stack.pollFirst();
            i++;
        }
        return res;
    }

739. 每日溫度

public int[] dailyTemperatures(int[] temperatures) {
        // 單調棧，維護一個遞減棧
        ArrayDeque<int[]> stack = new ArrayDeque<>();
        int[] res = new int[temperatures.length];
        int[][] temp = new int[temperatures.length][2];
        for (int i = 0; i < temperatures.length; i++) {
            temp[i][0] = i; //第一個記錄下标
            temp[i][1] = temperatures[i]; //第二個記錄下标對應的溫度
        }

        stack.addLast(temp[0]);
        for (int i = 1; i < temp.length; i++) {
            int[] ct = temp[i]; //現在的溫度
            while (!stack.isEmpty()){
                if(ct[1]>stack.getLast()[1]){
                    int[] last = stack.pollLast();
                    res[last[0]] = i-last[0];   //出棧：第一個比它大的下标-他自己的下标 就是第幾天溫度比他高
                }else {
                    stack.addLast(ct);
                    break;
                }
            }
            // 否則棧空就進棧
            stack.addLast(ct);
        }
        return res;
    }

算法隊列與棧—Java版

隊列、雙向隊列、棧 — ArrayDeque

堆（優先隊列）— PriorityQueue

232. 用棧實作隊列

225. 用隊列實作棧

LeetCode練習

20. 有效的括号

1047. 删除字元串中的所有相鄰重複項

150. 逆波蘭表達式求值

347. 前 K 個高頻元素

735. 行星碰撞

739. 每日溫度

繼續閱讀

Codeforces 1417 D. Make Them Equal(思維+構造)

查找算法之二分查找查找算法之二分查找

查找算法學習之二分查找（Python版本）——BinarySearch

CQ V1.0分詞bates(基于雙數組tire樹)—應該是目前最快的中文分詞算法

Command Network(POJ 3164)---定根最小樹形圖模闆題題目描述輸入格式輸出格式輸入樣例輸出樣例分析源程式

開源低帶寬語音編解碼器

241 Different Ways to Add Parentheses（C代碼版）

【趨高機器視覺】機器視覺技術原了解析及解決方案

CSMA/CD1． CSMA/CD的概述2． CSMA 的工作原理3． CSMA/CD控制規程及特點4． CSMA/CD協定5． CSMA/CD的優點6．結束語

極大似然法(ML)與最大期望法(EM)

C++ 第十五周報告1--《冒泡法排序》

筆試面試題目：滑動視窗(二)

資料結構與算法（27）——排序（二）

Dijkstra--簡易版（最短路徑）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

hdu7108哈希