## Algorithm

Problem Name: 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.

## Code Examples

### #1 Code Example with C Programming

```Code - C Programming```

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

struct StackNode {
int val;
struct StackNode *next;
};

struct Stack {
struct StackNode *top;
};

void push(struct Stack *stack, int new_val) {
if (stack == NULL) return;

struct StackNode *new_node
= (struct StackNode *)malloc(sizeof(struct StackNode));

new_node->val = new_val;
new_node->next = stack->top;

stack->top = new_node;
}

int pop(struct Stack *stack) {
if (stack == NULL || stack->top == NULL) return 0;

struct StackNode *t = stack->top;
int ans = t->val;

stack->top = stack->top->next;

free(t);

return ans;
}

bool isEmpty(struct Stack *stack) {
if (stack == NULL) return true;

return (stack->top == NULL) ? true : false;
}

typedef struct {
struct Stack in;
struct Stack out;
} Queue;

void queueCreate(Queue *queue, int maxSize) {
if (queue == NULL) return;

queue->in.top = queue->out.top = NULL;
}

void queuePush(Queue *queue, int element) {
if (queue == NULL) return;

while (!isEmpty(&queue->out)) {
int top = pop(&queue->out);
push(&queue->in, top);
}

push(&queue->in, element);
}

void queuePop(Queue *queue) {
if (queue == NULL) return;

if (isEmpty(&queue->out)) {
while (!isEmpty(&queue->in)) {
int top = pop(&queue->in);
push(&queue->out, top);
}
}

pop(&queue->out);
}

int queuePeek(Queue *queue) {
if (isEmpty(&queue->out)) {
while (!isEmpty(&queue->in)) {
int top = pop(&queue->in);
push(&queue->out, top);
}
}

if (!isEmpty(&queue->out) && queue->out.top) {
return queue->out.top->val;
}
else {
return 0;
}
}
bool queueEmpty(Queue *queue) {
if (isEmpty(&queue->in) && isEmpty(&queue->out)) {
return true;
}
else {
return false;
}
}

void queueDestroy(Queue *queue) {
while (!isEmpty(&queue->in)) {
pop(&queue->in);
}

while (!isEmpty(&queue->out)) {
pop(&queue->out);
}
}

int main() {
int maxSize = 5;
Queue q;

printf("Create a queue.\n"); queueCreate(&q, maxSize);

printf("Push 1\n"); queuePush(&q, 1);
printf("Push 2\n"); queuePush(&q, 2);
printf("Push 3\n"); queuePush(&q, 3);
printf("Push 4\n"); queuePush(&q, 4);

printf("Peek of queue: %d\n", queuePeek(&q));

printf("Pop\n"); queuePop(&q);
printf("Peek of queue: %d\n", queuePeek(&q));
printf("Push 5\n"); queuePush(&q, 5);
printf("Peek of queue: %d\n", queuePeek(&q));

printf("Pop\n"); queuePop(&q);
printf("Peek of queue: %d\n", queuePeek(&q));
printf("Pop\n"); queuePop(&q);
printf("Peek of queue: %d\n", queuePeek(&q));
printf("Pop\n"); queuePop(&q);
printf("Peek of queue: %d\n", queuePeek(&q));

printf("Destroy\n"); queueDestroy(&q);

return 0;
}
``````
Copy The Code &

Input

cmd
["MyQueue", "push", "push", "peek", "pop", "empty"] [[], [1], [2], [], [], []]

Output

cmd
[null, null, null, 1, 1, false]

### #2 Code Example with Java Programming

```Code - Java Programming```

``````
class MyQueue {

private final Stack stackOne;
private final Stack < Integer> stackTwo;

public MyQueue() {
this.stackOne = new Stack<>();
this.stackTwo = new Stack < >();
}

public void push(int x) {
this.stackOne.push(x);
}

public int pop() {
exchangeElements(stackOne, stackTwo);
int popped = stackTwo.pop();
exchangeElements(stackTwo, stackOne);
return popped;
}

public int peek() {
exchangeElements(stackOne, stackTwo);
int peeked = stackTwo.peek();
exchangeElements(stackTwo, stackOne);
return peeked;
}

public boolean empty() {
return stackOne.isEmpty();
}

private void exchangeElements(Stack < Integer> stack1, Stack stack2) {
while (!stack1.isEmpty()) {
stack2.push(stack1.pop());
}
}
}
``````
Copy The Code &

Input

cmd
["MyQueue", "push", "push", "peek", "pop", "empty"] [[], [1], [2], [], [], []]

Output

cmd
[null, null, null, 1, 1, false]

### #3 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
var MyQueue = function() {
this.input = []
this.output = []
};

MyQueue.prototype.push = function(x) {
this.input.push(x)
};

MyQueue.prototype.pop = function() {
if(this.output.length === 0) {
while(this.input.length) {
this.output.push(this.input.pop())
}
}
return this.output.pop()
};

MyQueue.prototype.peek = function() {
return this.output[this.output.length - 1] || this.input[0]
};

MyQueue.prototype.empty = function() {
return this.input.length === 0 && this.output.length === 0
};
``````
Copy The Code &

Input

cmd
["MyQueue", "push", "push", "peek", "pop", "empty"] [[], [1], [2], [], [], []]

Output

cmd
[null, null, null, 1, 1, false]

### #4 Code Example with Python Programming

```Code - Python Programming```

``````
class MyQueue:

def __init__(self):
"""
"""
self.data = []

def push(self, x):
"""
Push element x to the back of queue.
:type x: int
:rtype: void
"""
self.data.append(x)

def pop(self):
"""
Removes the element from in front of queue and returns that element.
:rtype: int
"""
front = self.data[0]
self.data = self.data[1:]
return front

def peek(self):
"""
Get the front element.
:rtype: int
"""
return self.data[0]

def empty(self):
"""
Returns whether the queue is empty.
:rtype: bool
"""
return not bool(self.data)
``````
Copy The Code &

Input

cmd
["MyQueue", "push", "push", "peek", "pop", "empty"] [[], [1], [2], [], [], []]

Output

cmd
[null, null, null, 1, 1, false]

### #5 Code Example with C# Programming

```Code - C# Programming```

``````
using System.Collections.Generic;

namespace LeetCode
{
public class _0232_ImplementQueueUsingStacks
{
private readonly Stack < int> s1;
private int s1Front;

public _0232_ImplementQueueUsingStacks()
{
s1 = new Stack < int>();
s2 = new Stack<int>();
}

public void Push(int x)
{
if (s1.Count == 0)
s1Front = x;
s1.Push(x);
}

public int Pop()
{
if (s2.Count == 0)
while (s1.Count > 0)
s2.Push(s1.Pop());

return s2.Pop();
}

public int Peek()
{
if (s2.Count > 0)
return s2.Peek();

return s1Front;
}

public bool Empty()
{
return s1.Count == 0 && s2.Count == 0;
}
}

}
``````
Copy The Code &

Input

cmd
["MyQueue", "push", "push", "peek", "pop", "empty"] [[], [1], [2], [], [], []]

Output

cmd
[null, null, null, 1, 1, false]