LeetCode //C - 225. Implement Stack using Queues

225. Implement Stack using Queues

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.

From: LeetCode
Link: 225. Implement Stack using Queues

Solution:

Ideas:

1. Queue Operations:

• createQueue: Initializes a queue with a given capacity.
• isQueueEmpty: Checks if the queue is empty.
• isQueueFull: Checks if the queue is full.
• enqueue: Adds an element to the rear of the queue.
• dequeue: Removes an element from the front of the queue.
• queueFront: Gets the front element of the queue without removing it.

2. Stack Operations:

• myStackCreate: Initializes the stack using two queues.
• myStackPush: Pushes an element to the stack by enqueueing it to q2 and then moving all elements from q1 to q2. Finally, swaps q1 and q2.
• myStackPop: Pops the top element from the stack by dequeuing from q1.
• myStackTop: Returns the top element of the stack by peeking the front of q1.
• myStackEmpty: Checks if the stack is empty by checking if q1 is empty.
• myStackFree: Frees the memory allocated for the stack.

Code:

typedef struct {     int *data;     int front;     int rear;     int size;     int capacity; } Queue;  Queue* createQueue(int capacity) {     Queue* queue = (Queue*)malloc(sizeof(Queue));     queue->capacity = capacity;     queue->front = 0;     queue->size = 0;     queue->rear = capacity - 1;     queue->data = (int*)malloc(capacity * sizeof(int));     return queue; }  bool isQueueEmpty(Queue* queue) {     return (queue->size == 0); }  bool isQueueFull(Queue* queue) {     return (queue->size == queue->capacity); }  void enqueue(Queue* queue, int item) {     if (isQueueFull(queue)) return;     queue->rear = (queue->rear + 1) % queue->capacity;     queue->data[queue->rear] = item;     queue->size = queue->size + 1; }  int dequeue(Queue* queue) {     if (isQueueEmpty(queue)) return -1;     int item = queue->data[queue->front];     queue->front = (queue->front + 1) % queue->capacity;     queue->size = queue->size - 1;     return item; }  int queueFront(Queue* queue) {     if (isQueueEmpty(queue)) return -1;     return queue->data[queue->front]; }  typedef struct {     Queue* q1;     Queue* q2; } MyStack;  MyStack* myStackCreate() {     MyStack* stack = (MyStack*)malloc(sizeof(MyStack));     stack->q1 = createQueue(100);     stack->q2 = createQueue(100);     return stack; }  void myStackPush(MyStack* obj, int x) {     enqueue(obj->q2, x);     while (!isQueueEmpty(obj->q1)) {         enqueue(obj->q2, dequeue(obj->q1));     }     Queue* temp = obj->q1;     obj->q1 = obj->q2;     obj->q2 = temp; }  int myStackPop(MyStack* obj) {     return dequeue(obj->q1); }  int myStackTop(MyStack* obj) {     return queueFront(obj->q1); }  bool myStackEmpty(MyStack* obj) {     return isQueueEmpty(obj->q1); }  void myStackFree(MyStack* obj) {     free(obj->q1->data);     free(obj->q1);     free(obj->q2->data);     free(obj->q2);     free(obj); }  /**  * Your MyStack struct will be instantiated and called as such:  * MyStack* obj = myStackCreate();  * myStackPush(obj, x);  * int param_2 = myStackPop(obj);  * int param_3 = myStackTop(obj);  * bool param_4 = myStackEmpty(obj);  * myStackFree(obj);  */