yoruru的努力日記

232. Implement Queue using Stacks

Implement a first in first out (FIFO) queue using only two stacks. The implemented queue should support all the functions of a normal queue (push, peek, pop, and empty).

Implement the MyQueue class:

• void push(int x) Pushes element x to the back of the queue.
• int pop() Removes the element from the front of the queue and returns it.
• int peek() Returns the element at the front of the queue.
• boolean empty() Returns true if the queue is empty, false otherwise.

Notes:

• You must use only standard operations of a stack, which means only push to top, peek/pop from top, size, and is empty operations are valid.
• Depending on your language, the stack may not be supported natively. You may simulate a stack using a list or deque (double-ended queue) as long as you use only a stack's standard operations.

Example 1:

Input
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
Output
[null, null, null, 1, 1, false]

Explanation
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false

Constraints:

• 1 <= x <= 9
• At most 100 calls will be made to push, pop, peek, and empty.
• All the calls to pop and peek are valid.

SOL：

一開始對stack的用法不太熟悉，回去複習了一下 [LeetCode-C] 155. Min Stack

不過這一題因為題目限制在100次的呼叫以內，所以可以宣告最大的array來解決，因此題目難度只有easy。

但我覺得這一題的難點是在於，要想到用一個stack來push資料，而且因為stack只能從top一個一個取值(top是最大index的感覺)，要pop/peek資料時必須用另一個空的stack把資料以相反的順序存入，這樣從這個新的stack的top取值才會是queue FIFO的順序。

一樣使用 chatqpt 來參考答案，這次的解法大量使用了 ++i, i++, --i. i--這種用法。

要能理解的訣竅在於 i++、i--這種把變數放前面的，在當行程式碼中 i 是原值，結束這行運算後，i 才會變成 (i+1)、(i-1)。

而 ++i、--i 這種把運算符號放前面、變數放後面的，看重的東西放前面，意思是希望 i 趕快進行運算，所以在當行程式碼中 i 就直接更新成 (i+1)、(i-1)。

並且這個解法也完成了 Follow-up ：把大部分queue操作時間間複雜度控制在 O(1)內，惟除了當 top2是-1的時候，第一次把資料從stack1寫入stack2會是O(n)。

这道题的思路是用两个栈来模拟一个队列，其中一个栈（stack1）用于插入元素，另一个栈（stack2）用于删除元素。每当需要删除元素时，如果 stack2 不为空，则直接删除 stack2 的栈顶元素；如果 stack2 为空，则先将 stack1 中的元素全部弹出并压入 stack2 中，再从 stack2 中删除栈顶元素。

需要注意的是，在判断队列是否为空时，需要同时判断 stack1 和 stack2 是否为空。

同时，我们需要定义一个结构体来存储两个栈以及它们的栈顶指针，以方便后续的操作。

至於我自己的解法如下，把pop改成呼叫peek，就可以偷懶少寫一段程式碼。

#define MAX_SIZE 1000

typedef struct {
    int stack1[MAX_SIZE];
    int stack2[MAX_SIZE];
    int top1, top2;
} MyQueue;


MyQueue* myQueueCreate() {
    MyQueue* q = (MyQueue*)malloc(sizeof(MyQueue));
    q->top1 = -1;
    q->top2 = -1;
    return q;
}

void myQueuePush(MyQueue* obj, int x) {
    obj->stack1[++(obj->top1)] = x;
}

int myQueuePop(MyQueue* obj) {
    int val = myQueuePeek(obj);
    obj->top2--;
    return val;
}

int myQueuePeek(MyQueue* obj) {
    if(obj->top2 == -1){
        while(obj->top1 != -1){
            obj->stack2[++(obj->top2)]=obj->stack1[(obj->top1)--];
        }
    }
    int val = obj->stack2[(obj->top2)];
    return val;
}

bool myQueueEmpty(MyQueue* obj) {
    if(obj->top1 == -1 && obj->top2 == -1)
        return true;
    else
        return false;
}

void myQueueFree(MyQueue* obj) {
    free(obj);
}

/**
 * Your MyQueue struct will be instantiated and called as such:
 * MyQueue* obj = myQueueCreate();
 * myQueuePush(obj, x);
 
 * int param_2 = myQueuePop(obj);
 
 * int param_3 = myQueuePeek(obj);
 
 * bool param_4 = myQueueEmpty(obj);
 
 * myQueueFree(obj);
*/