Sponsored
Sponsored
This approach involves using two queues to simulate the operations of a stack. Whenever we push an element onto the stack, we move all elements from the first queue to the second queue, enqueue the new element into the first queue, and then move all elements back from the second queue to the first one. This ensures that the newest element is always at the front of the queue, allowing us to use single dequeue operations for pop() and top(), thus mimicking a stack's LIFO behavior.
Time Complexity: push - O(n), pop, top, and empty - O(1).
Space Complexity: O(n) for two queues storing up to all stack elements at once.
1#include <stdio.h>
2#include <stdlib.h>
3#include <stdbool.h>
4
5#define MAX_SIZE 100
6
7typedef struct {
8 int data[MAX_SIZE];
9 int front;
10 int rear;
11 int size;
12} Queue;
13
14Queue* createQueue() {
15 Queue* q = (Queue*)malloc(sizeof(Queue));
16 q->front = 0;
17 q->rear = -1;
18 q->size = 0;
19 return q;
20}
21
22bool isEmpty(Queue* q) {
23 return q->size == 0;
24}
25
26void enqueue(Queue* q, int x) {
27 if (q->size < MAX_SIZE) {
28 q->rear = (q->rear + 1) % MAX_SIZE;
29 q->data[q->rear] = x;
30 q->size++;
31 }
32}
33
34int dequeue(Queue* q) {
35 int item = -1;
36 if (!isEmpty(q)) {
37 item = q->data[q->front];
38 q->front = (q->front + 1) % MAX_SIZE;
39 q->size--;
40 }
41 return item;
42}
43
44int front(Queue* q) {
45 return q->data[q->front];
46}
47
48typedef struct {
49 Queue* q1;
50 Queue* q2;
51} MyStack;
52
53MyStack* myStackCreate() {
54 MyStack* stack = (MyStack*)malloc(sizeof(MyStack));
55 stack->q1 = createQueue();
56 stack->q2 = createQueue();
57 return stack;
58}
59
60void myStackPush(MyStack* obj, int x) {
61 enqueue(obj->q2, x);
62 while (!isEmpty(obj->q1)) {
63 enqueue(obj->q2, dequeue(obj->q1));
64 }
65 Queue* temp = obj->q1;
66 obj->q1 = obj->q2;
67 obj->q2 = temp;
68}
69
70int myStackPop(MyStack* obj) {
71 return dequeue(obj->q1);
72}
73
74int myStackTop(MyStack* obj) {
75 return front(obj->q1);
76}
77
78bool myStackEmpty(MyStack* obj) {
79 return isEmpty(obj->q1);
80}
81
82void myStackFree(MyStack* obj) {
83 free(obj->q1);
84 free(obj->q2);
85 free(obj);
86}The solution involves implementing two queues using arrays with helper functions for queue operations. We use these queues to implement stack operations where push is done by rotating elements between two queues, ensuring the stack order.
This approach only uses one queue to implement the stack. When pushing an element, we enqueue the element and then rotate the queue such that the newly added element reaches the front. The queue thus behaves like a stack with respect to push, pop, top
Time Complexity: push - O(n), pop, top, and empty - O(1).
Space Complexity: O(n), as we use only one queue to hold stack data.
1
This approach takes advantage of a single queue, rotating the elements until the newly pushed element reaches the front. This ensures it behaves as the top of the stack.