Queues 簡介

在Java中，Queue（佇列）是一種常用的資料結構，它遵循先進先出（FIFO）的原則。Java提供了多種實現Queue的類，例如LinkedList和ArrayDeque。

使用Queue可以實現許多實用的功能，例如處理排隊系統、廣度優先搜索等。透過add或offer方法，我們可以將元素添加到Queue的尾部；透過remove或poll方法，我們可以從Queue的頭部刪除並返回元素；透過peek方法，我們可以查看Queue的頭部元素而不刪除它。

使用Queue可以方便地管理和操作元素，並且適用於各種場景。如果你需要處理排隊、廣度優先搜索或其他類似的問題，Queue將是一個非常有用的工具。

題目：225. Implement Stack using Queues

連結：https://leetcode.com/problems/implement-stack-using-queues/description/

• 等級：Easy

解題思路

1. 利用Queuesg實作

class MyStack {
    Deque<Integer> q;
    public MyStack() {
        this.q = new ArrayDeque<>();
    }
    
    public void push(int x) {
        this.q.addLast(x);
    }
    
    public int pop() {
        int size = this.q.size();
        for (int i = 0;i < size-1;i++)
            this.push(this.q.pollFirst());
        return this.q.pollFirst();
    }
    
    public int top() {
        int size = this.q.size();
        for (int i = 0;i < size-1;i++)
            this.push(this.q.pollFirst());
        int res = this.q.peekFirst();
        this.push(this.q.pollFirst());
        return res;
    }
    
    public boolean empty() {
        return this.q.size() == 0;
    }
}

題目：353. Design Snake Game

連結：https://leetcode.com/problems/design-snake-game/description/

• 等級：Medium

解題思路

1. 依步驟推算與紀錄物件行走路徑

class SnakeGame {
    Set<Integer> set; 
    Deque<Integer> body;
    int score;
    int[][] food;
    int foodIndex;
    int width;
    int height;
    public SnakeGame(int width, int height, int[][] food) {
        this.width = width;
        this.height = height;
        this.food = food;
        set = new HashSet<>();
        set.add(0); 
        body = new LinkedList<>();//記錄蛇移動的位置
        body.offerLast(0);
    }
    
    public int move(String direction) {
        //遊戲結束停止
        if (score == -1)
            return -1;
        //計算蛇的起始移動位置
        int rowHead = body.peekFirst() / width;
        int colHead = body.peekFirst() % width;
        switch (direction) {
            case "U" : rowHead--;
                        break;
            case "D" : rowHead++;
                       break;
            case "L" : colHead--;
                       break;
            default :  colHead++;//R
        }
        int head = rowHead * width + colHead;

        //判斷是否超過邊界或撞到自己
        set.remove(body.peekLast());//新頭在舊尾位置是ＯＫ的不納入判斷
        if (rowHead < 0 || rowHead == height || colHead < 0 || colHead == width || set.contains(head)) {
            return score = -1;
        }
        //移動位置
        set.add(head);
        body.offerFirst(head);

        //判斷是否吃到食物
        if (foodIndex < food.length && rowHead == food[foodIndex][0] && colHead == food[foodIndex][1])
        {
            set.add(body.peekLast());
            foodIndex++;
            return ++score;
        }
        //一般移動移除尾巴增加頭
        body.pollLast();
        return score;
    }
}