## Algorithm

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

## Code Examples

### #1 Code Example with C Programming

```Code - C Programming```

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

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

struct Queue{
int size;
struct QueueNode *front;
struct QueueNode *tail;
};

void push(struct Queue *queue, int new_val) {
if (queue == NULL) return;

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

new_node->val = new_val;
new_node->next = NULL;

if (queue->tail != NULL) {
queue->tail->next = new_node;
}

queue->tail = new_node;

if (queue->front == NULL) {
queue->front = new_node;
queue->size = 1;
}
else{
queue->size++;
}
}

void pop(struct Queue *queue) {
if (queue == NULL || queue->front == NULL) return;

struct QueueNode *tmp = queue->front;
queue->front = queue->front->next;

free(tmp);
queue->size--;

if (queue->front == NULL) {
queue->tail = NULL;
queue->size = 0;
}
}

int size(struct Queue *queue) {
if (queue == NULL) {
return 0;
}
else {
return queue->size;
}
}

bool isEmpty(struct Queue *queue) {
if (queue == NULL) {
return true;
}
else {
return (queue->size == 0) ? true : false;
}
}

typedef struct {
struct Queue queue;
} Stack;

void stackCreate(Stack *stack, int maxSize) {
if (stack == NULL) return;

stack->queue.front = stack->queue.tail = 0;
stack->queue.size = 0;
}

void stackPush(Stack *stack, int element) {
if (stack == NULL) return;

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

/* Removes the element on top of the stack */
void stackPop(Stack *stack) {
if (stack == NULL) return;

int originalSize = size(&stack->queue);
int i;
for (i = 0; i  <  originalSize - 1; i++) {
if (stack->queue.front == NULL) {
return;
}
int tmp = stack->queue.front->val;
pop(&stack->queue);
push(&stack->queue, tmp);
}

pop(&stack->queue);
}

int stackTop(Stack *stack) {
if (stack == NULL || stack->queue.tail == NULL) {
return 0;
}
else {
return stack->queue.tail->val;
}
}

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

return isEmpty(&stack->queue);
}

void stackDestroy(Stack *stack) {
if (stack == NULL) return;

while (size(&stack->queue) > 0) {
pop(&stack->queue);
}
}

int main() {

Stack s;
int maxSize = 5;
stackCreate(&s, maxSize);

printf("push 1 to stack.\n");
stackPush(&s, 1);

printf("push 2 to stack.\n");
stackPush(&s, 2);

printf("push 3 to stack.\n");
stackPush(&s, 3);

printf("current top of stack is: %d.\n", stackTop(&s));
printf("stack is empty? %d.\n", stackEmpty(&s));

printf("pop from stack.\n");
stackPop(&s);

printf("current top of stack is: %d.\n", stackTop(&s));

printf("destroy stack.\n");
stackDestroy(&s);

printf("current top of stack is: %d.\n", stackTop(&s));
printf("stack is empty? %d.\n", stackEmpty(&s));

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

Input

cmd
["MyStack", "push", "push", "top", "pop", "empty"] [[], [1], [2], [], [], []]

Output

cmd
[null, null, null, 2, 2, false]

### #2 Code Example with Java Programming

```Code - Java Programming```

``````
class MyStack {

private Queue primaryQueue;
private Queue < Integer> secondaryQueue;

public MyStack() {
this.primaryQueue = new LinkedList<>();
this.secondaryQueue = new LinkedList < >();
}

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

public int pop() {
int result = moveFromPrimaryToSecondary();
moveFromSecondaryToPrimary(true);
return result;
}

public int top() {
int result = moveFromPrimaryToSecondary();
moveFromSecondaryToPrimary(false);
return result;
}

public boolean empty() {
return this.primaryQueue.isEmpty();
}

private int moveFromPrimaryToSecondary() {
int last = this.primaryQueue.peek();
while (!this.primaryQueue.isEmpty()) {
last = this.primaryQueue.peek();
this.secondaryQueue.add(this.primaryQueue.remove());
}
return last;
}

private void moveFromSecondaryToPrimary(boolean removeLast) {
while (this.secondaryQueue.size() > 1) {
this.primaryQueue.add(this.secondaryQueue.remove());
}
if (removeLast) {
this.secondaryQueue.remove();
} else {
this.primaryQueue.add(this.secondaryQueue.remove());
}
}
}
``````
Copy The Code &

Input

cmd
["MyStack", "push", "push", "top", "pop", "empty"] [[], [1], [2], [], [], []]

Output

cmd
[null, null, null, 2, 2, false]

### #3 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const MyStack = function() {
this.stack = []
};

MyStack.prototype.push = function(x) {
this.stack.push(x)
};

MyStack.prototype.pop = function() {
return this.stack.pop()
};

MyStack.prototype.top = function() {
return this.stack.length === 0 ? null : this.stack[this.stack.length - 1]
};

MyStack.prototype.empty = function() {
return this.stack.length === 0
};
``````
Copy The Code &

Input

cmd
["MyStack", "push", "push", "top", "pop", "empty"] [[], [1], [2], [], [], []]

Output

cmd
[null, null, null, 2, 2, false]

### #4 Code Example with Python Programming

```Code - Python Programming```

``````
class MyStack:

def __init__(self):
"""
Initialize your data structure here.
"""
self.data = []

def push(self, x):
"""
Push element x onto stack.
:type x: int
:rtype: void
"""
self.data.append(x)

def pop(self):
"""
Removes the element on top of the stack and returns that element.
:rtype: int
"""
return self.data.pop()

def top(self):
"""
Get the top element.
:rtype: int
"""
return self.data[-1]

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

Input

cmd
["MyStack", "push", "push", "top", "pop", "empty"] [[], [1], [2], [], [], []]

Output

cmd
[null, null, null, 2, 2, false]

### #5 Code Example with C# Programming

```Code - C# Programming```

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

namespace LeetCode
{
public class _0225_ImplementStackUsingQueues
{
private readonly Queue < int> queue;

public _0225_ImplementStackUsingQueues()
{
queue = new Queue<int>();
}

public void Push(int x)
{
queue.Enqueue(x);
var i = queue.Count - 1;
while (i-- > 0)
queue.Enqueue(queue.Dequeue());
}

public int Pop()
{
return queue.Dequeue();
}

public int Top()
{
return queue.Peek();
}

public bool Empty()
{
return queue.Count == 0;
}
}

}
``````
Copy The Code &

Input

cmd
["MyStack", "push", "push", "top", "pop", "empty"] [[], [1], [2], [], [], []]

Output

cmd
[null, null, null, 2, 2, false]
Advertisements