---
tags: 提升程式設計師的面試力
---
# Stack and Queue

### Queue

概念：先進先出，先加入的元素會先被移除

方法：

add(item) : 加入元素

remove() : 移除對列的第一個元素

peek() : 取得對列的第一個元素(並不移除)

isEmpty() : 只有對列為空時為真

結構：

實作與Stack類似，不過移除的方向與Stack相反。

public class MyQueue<T>
{
    // 建立 LinkedList 結構
    private class QueueNode<T>
    {
        public T data;
        public QueueNode<T> next;

        public QueueNode(T data)
        {
            this.data = data;
        }
    }

    // 對列第一個項目
    private QueueNode<T> first;
    // 對列最後項目
    private QueueNode<T> last;

    // Add
    public void Add(T data)
    {
        var t = new QueueNode<T>(data);
        if (last != null)
        {
            last.next = t;
        }
        last = t;
        if (first == null)
        {
            first = last;
        }
    }

    public T Remove()
    {
        if (first == null) throw new NoSuchElementException();

        T data = first.data;
        first = first.next;
        if (first == null)
        {
            last = null;
        }
        return data;
    }

    public T Peek()
    {
        if (first == null) throw new NoSuchElementException();
        return first.data;
    }

    public bool IsEmpty()
    {
        return first == null;
    }

}

### 題目

**用Stack做出Queue**：利用兩個Stack做出一個Queue

提示1：如何移除Stack內最舊的元素？

提示2：如果要呼叫Queue.pop()，可以如何優化？

解法：

public class StackQueue<T>
{
    Stack<T> stackNewest, stackOldest;

    public StackQueue()
    {
        stackNewest = new Stack<T>();
        stackOldest = new Stack<T>();
    }

    public bool IsEmpty()
    {
        return Size() == 0;
    }

    public int Size()
    {
        return stackNewest.Count + stackOldest.Count;
    }

    public void Add(T value)
    {
        stackNewest.Push(value);
    }

    private void ShiftStacks()
    {
        if (stackOldest.Count == 0)
        {
            while (stackNewest.Count != 0)
            {
                stackOldest.Push(stackNewest.Pop());
            }
        }
    }

    public T Peek()
    {
        ShiftStacks();
        return stackOldest.Peek();
    }

    public T Remove()
    {
        ShiftStacks();
        return stackOldest.Pop();
    }
}

---

**排列Stack內元素**：寫一段程式，讓Stack內最上方的元素是最小的。
限制： 只能使用一個暫存Stack來完成

提示1：有一種排序方法是，遍歷所有元素，取出最大並存入新Stack

提示2：假設第二個Stack已經排序好了，要如何把新元素存入第二個Stack？如何設計一個暫存的空間？

提示3：讓第二個Stack保持排序狀態(最上面最大)，把第一個Stack作為暫存Stack。

解法：

public class SortStack : Stack<int>
{
    public void Sort()
    {
        // 亂序Stack
        var s = this;
        // 排序Stack
        Stack<int> r = new();

        while (s.Count != 0)
        {
            int temp = s.Pop();
            while (r.Count != 0 && r.Peek() > temp)
            {
                s.Push(r.Pop());
            }
            r.Push(temp);
        }

        while (r.Count != 0)
        {
            s.Push(r.Pop());
        }
    }
}

---

**動物收容所：** 動物收容所內有貓與狗，先進來的動物會優先被領養，提供實作以下方法：enqueue, dequeueAny, dequeueDog, dequeueCat。

提示1：可以用一個串列紀錄所有貓狗，由遍歷的方式取出符合條件的動物，此做法有何利弊？

提示2：如果用兩個串列分別記錄貓狗，要怎麼取得最早的動物？

提示3：在現實生活中，要怎麼依據時序紀錄收入的動物？要怎麼找到最早的動物？要怎麼維護這些資料？

解法

public class AnimalQueue
{
    Queue<Dog> dogs = new();
    Queue<Cat> cats = new();
    private int order = 0; // 紀錄收容順序

    public void Enqueue(Animal a)
    {
        a.SetOrder(order);
        order++;

        if (a is Dog) dogs.Enqueue((Dog)a);
        else if (a is Cat) cats.Enqueue((Cat)a);
    }

    public Animal DequeueAny()
    {
        if (dogs.Count == 0) return DequeueCat();
        else if (cats.Count == 0) return DequeueDog();

        var dog = dogs.Peek();
        var cat = cats.Peek();

        if (dog.IsOlderThan(cat))
        {
            return DequeueDog();
        }
        else
        {
            return DequeueCat();
        }
    }

    public Dog DequeueDog() => dogs.Dequeue();

    public Cat DequeueCat() => cats.Dequeue();

}