xisto Community

# Data Structure -- Queue -- Implement Using Stack

## Recommended Posts

Implement a Queue using a stack.

No restriction on space complexity.

One possible Solutions

a costly procedure...

1. Use a temp stack

2. Insertion into queue

- Push the element into the original stack

3. Deletion from queue

- Pop all the elements from stack into a temp stack

- pop out the first element from the temp stack

- pop all the remaining elements back to the original stack

What is a queue?

A queue is a particular kind of collection in which the entities in the collection are kept in order and the principal (or only) operations on the collection are the addition of entities to the rear terminal position and removal of entities from the front terminal position. This makes the queue a First-In-First-Out (FIFO) data structure. In a FIFO data structure, the first element added to the queue will be the first one to be removed. This is equivalent to the requirement that whenever an element is added, all elements that were added before have to be removed before the new element can be invoked. A queue is an example of a linear data structure.

http://forums.xisto.com/no_longer_exists/

##### Share on other sites

reverse the string using two queues

Data Structure -- Queue -- Implement Using Stack

Reverse the string using two queues

##### Share on other sites

well, as u rightly said, it is a costly procedure.

let me tell you how to do it without increasing the computational cost:

use two stacks s1, and s2

start off with s1 empty and s2 full

for enque: push onto stack s1

for deque: pop from stack s2

when s2 gets empty pop all elements from s1 into s2

Implement a Queue using a stack.

No restriction on space complexity.

One possible Solutions

a costly procedure...

1. Use a temp stack

2. Insertion into queue

- Push the element into the original stack

3. Deletion from queue

- Pop all the elements from stack into a temp stack

- pop out the first element from the temp stack

- pop all the remaining elements back to the original stack

What is a queue?

http://forums.xisto.com/no_longer_exists/

##### Share on other sites

all the steps are same as above except that there is no need to push back the items to the original stack or as we say inbox stack

## Create an account

Register a new account