README
¶
Name
39 - queue using stack
Description
Problem
Implement a queue using stack with the following API, derived from std::queue:
type Queue interface {
Empty() bool
Front() (int, bool)
Pop()
Push(int)
Size() int
}
Example
Solution
DetailsUse two stacks:
-
in: keeps track of input items. It gives a way to quickly push items to the
queue.
-
out: a list of items to remove - the top item is the first one in the queue.
Performance:
-
time:
- Empty is O(1)
- Front is O(n) due to move from in to out stacks
- Pop is O(n) due to move from in to out stacks
- Push is O(1)
- Size is O(1)
-
space: O(n)
in: keeps track of input items. It gives a way to quickly push items to the queue.
out: a list of items to remove - the top item is the first one in the queue.
time:
- Empty is O(1)
- Front is O(n) due to move from in to out stacks
- Pop is O(n) due to move from in to out stacks
- Push is O(1)
- Size is O(1)
space: O(n)
Directories
Click to show internal directories.
Click to hide internal directories.