Description

Implement a last-in-first-out (LIFO) stack using only two queues. The implemented stack should support all the functions of a normal stack (push, top, pop, and empty).

Implement the MyStack class:

void push(int x) Pushes element x to the top of the stack.
int pop() Removes the element on the top of the stack and returns it.
int top() Returns the element on the top of the stack.
boolean empty() Returns true if the stack is empty, false otherwise.
Notes:

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

Example 1:

Input
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
Output
[null, null, null, 2, 2, false]

Explanation
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // return 2
myStack.pop(); // return 2
myStack.empty(); // return False

Constraints:

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

Follow-up: Can you implement the stack using only one queue?

Answer & Explaining

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

// 定義一個Queue
typedef struct {
    int *data;
    int front;
    int rear;
    int size;
    int capacity;
} Queue;

// 創建Queue
Queue* createQueue(int capacity) {
    Queue *queue = (Queue*)malloc(sizeof(Queue));
    queue->data = (int*)malloc(capacity * sizeof(int));
    queue->front = 0;
    queue->rear = 0;
    queue->size = 0;
    queue->capacity = capacity;//設置容量
    return queue;//傳回Queue的pointer
}

// 確認Queue是否為空
bool isEmpty(Queue* queue) {
    return queue->size == 0;
}

// 添加Queue元素
void enqueue(Queue* queue, int item) {
    if (queue->size == queue->capacity) return; //滿的情況不做操作
    queue->data[queue->rear] = item;//將新物件放到尾端
    queue->rear = (queue->rear + 1) % queue->capacity;//更新rear
    queue->size++;//更新size
}

// 取出元素
int dequeue(Queue* queue) {
    if (isEmpty(queue)) return -1;//空的情況
    int item = queue->data[queue->front];//取出front
    queue->front = (queue->front + 1) % queue->capacity;//更新front
    queue->size--;//size更新
    return item;//回傳取出的元素
}

// 取得Front
int front(Queue* queue) {
    if (isEmpty(queue)) return -1;
    return queue->data[queue->front];//取得目前的front
}

// 定義整體結構，使用兩個Queue
typedef struct {
    Queue* queue1;
    Queue* queue2;
} MyStack;

// 創建Stack
MyStack* myStackCreate() {
    MyStack *stack = (MyStack*)malloc(sizeof(MyStack));
    stack->queue1 = createQueue(100);  // 最多100元素
    stack->queue2 = createQueue(100);
    return stack;
}

// Push實現
void myStackPush(MyStack* obj, int x) {
    enqueue(obj->queue1, x);//放到queue1
}

// Pop實現
int myStackPop(MyStack* obj) {
    while (obj->queue1->size > 1) {//在大小大於一時不斷執行
        //將queue1 的元素放到 queue2
        enqueue(obj->queue2, dequeue(obj->queue1));
    }
    int topElement = dequeue(obj->queue1);//Top為最後一個Queue1的取出
    Queue* temp = obj->queue1;//將兩個queue做SWAP
    obj->queue1 = obj->queue2;
    obj->queue2 = temp;
    return topElement;//回傳top
}

// 獲得Top
int myStackTop(MyStack* obj) {
    while (obj->queue1->size > 1) {//在大小大於一時不斷執行
        //將queue1 的元素放到 queue2
        enqueue(obj->queue2, dequeue(obj->queue1));
    }
    int topElement = front(obj->queue1);
    enqueue(obj->queue2, dequeue(obj->queue1));
    Queue* temp = obj->queue1;//兩Queue交換
    obj->queue1 = obj->queue2;
    obj->queue2 = temp;
    return topElement;
}

// 檢查Stack是否空
bool myStackEmpty(MyStack* obj) {
    return isEmpty(obj->queue1);
}

// 釋放空間
void myStackFree(MyStack* obj) {
    free(obj->queue1->data);
    free(obj->queue1);
    free(obj->queue2->data);
    free(obj->queue2);
    free(obj);
}

Testing

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

// 定義一個Queue
typedef struct {
    int *data;
    int front;
    int rear;
    int size;
    int capacity;
} Queue;

// 創建Queue
Queue* createQueue(int capacity) {
    Queue *queue = (Queue*)malloc(sizeof(Queue));
    queue->data = (int*)malloc(capacity * sizeof(int));
    queue->front = 0;
    queue->rear = 0;
    queue->size = 0;
    queue->capacity = capacity;//設置容量
    return queue;//傳回Queue的pointer
}

// 確認Queue是否為空
bool isEmpty(Queue* queue) {
    return queue->size == 0;
}

// 添加Queue元素
void enqueue(Queue* queue, int item) {
    if (queue->size == queue->capacity) return; //滿的情況不做操作
    queue->data[queue->rear] = item;//將新物件放到尾端
    queue->rear = (queue->rear + 1) % queue->capacity;//更新rear
    queue->size++;//更新size
}

// 取出元素
int dequeue(Queue* queue) {
    if (isEmpty(queue)) return -1;//空的情況
    int item = queue->data[queue->front];//取出front
    queue->front = (queue->front + 1) % queue->capacity;//更新front
    queue->size--;//size更新
    return item;//回傳取出的元素
}

// 取得Front
int front(Queue* queue) {
    if (isEmpty(queue)) return -1;
    return queue->data[queue->front];//取得目前的front
}

// 定義整體結構，使用兩個Queue
typedef struct {
    Queue* queue1;
    Queue* queue2;
} MyStack;

// 創建Stack
MyStack* myStackCreate() {
    MyStack *stack = (MyStack*)malloc(sizeof(MyStack));
    stack->queue1 = createQueue(100);  // 最多100元素
    stack->queue2 = createQueue(100);
    return stack;
}

// Push實現
void myStackPush(MyStack* obj, int x) {
    enqueue(obj->queue1, x);//放到queue1
}

// Pop實現
int myStackPop(MyStack* obj) {
    while (obj->queue1->size > 1) {//在大小大於一時不斷執行
        //將queue1 的元素放到 queue2
        enqueue(obj->queue2, dequeue(obj->queue1));
    }
    int topElement = dequeue(obj->queue1);//Top為最後一個Queue1的取出
    Queue* temp = obj->queue1;//將兩個queue做SWAP
    obj->queue1 = obj->queue2;
    obj->queue2 = temp;
    return topElement;//回傳top
}

// 獲得Top
int myStackTop(MyStack* obj) {
    while (obj->queue1->size > 1) {//在大小大於一時不斷執行
        //將queue1 的元素放到 queue2
        enqueue(obj->queue2, dequeue(obj->queue1));
    }
    int topElement = front(obj->queue1);
    enqueue(obj->queue2, dequeue(obj->queue1));
    Queue* temp = obj->queue1;//兩Queue交換
    obj->queue1 = obj->queue2;
    obj->queue2 = temp;
    return topElement;
}

// 檢查Stack是否空
bool myStackEmpty(MyStack* obj) {
    return isEmpty(obj->queue1);
}

// 釋放空間
void myStackFree(MyStack* obj) {
    free(obj->queue1->data);
    free(obj->queue1);
    free(obj->queue2->data);
    free(obj->queue2);
    free(obj);
}

//測試
int main() {
    MyStack* obj = myStackCreate();
    myStackPush(obj, 1);
    myStackPush(obj, 2);
    printf("Top element: %d\n", myStackTop(obj)); // 输出 2
    printf("Pop element: %d\n", myStackPop(obj)); // 输出 2
    printf("Is empty: %d\n", myStackEmpty(obj));  // 输出 0 (false)
    myStackFree(obj);
    return 0;
}