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.
1using System.Collections.Generic;
2
3public class MyStack {
4 private Queue<int> q1 = new Queue<int>();
5 private Queue<int> q2 = new Queue<int>();
6
7 public void Push(int x) {
8 q2.Enqueue(x);
9 while (q1.Count > 0) {
10 q2.Enqueue(q1.Dequeue());
11 }
12 var temp = q1;
13 q1 = q2;
14 q2 = temp;
15 }
16
17 public int Pop() {
18 return q1.Dequeue();
19 }
20
21 public int Top() {
22 return q1.Peek();
23 }
24
25 public bool Empty() {
26 return q1.Count == 0;
27 }
28}
29For C#, the implementation uses the Queue class. Element addition involves queuing to the second queue and then swapping to keep the stack's top element aligned with the queue's front.
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
public class MyStack {
private Queue<int> q1;
public MyStack() {
q1 = new Queue<int>();
}
public void Push(int x) {
q1.Enqueue(x);
int count = q1.Count;
while (count > 1) {
q1.Enqueue(q1.Dequeue());
count--;
}
}
public int Pop() {
return q1.Dequeue();
}
public int Top() {
return q1.Peek();
}
public bool Empty() {
return q1.Count == 0;
}
}
This C# implementation successfully creates a stack-like behavior from a single queue by manipulating the order upon each element pushed, sequentially translating this item to the front for stack alignment.