Created Tuesday 17 December 2013
The queue is a FIFO data structure---first in/first out. Items are put in the end of the queue and are removed from the head of the queue. Think of a line at a bank.
Java has a Queue<E> interface as well as some concrete classes (not limited to):
- ArrayBlockingQueue
- Linked List
How to Implement a Queue using a Stack
- A queue is FIFO
- A stack is LIFO
- Therefore, you'll need at least two stacks.
- Implement add() in the usual way. Ex: add elements 1,2,3,4 in that order
Stack A: head -> | 1 | 2 | 3 | 4 | 5 | <-tail
- To remove() an element, pop the items in Stack A and put them into Stack B:
Stack B: head -> | 5 | 4 | 3 | 2 | 1 | <- tail
The items are now in reverse order so you can pop them from Stack B.
- The full add() method pops the items from Stack B onto Stack A before adding the element to Stack A.
#
No backlinks to this page. comments powered by Disqus