- Overview
- Applications
- Common Procedures
- Design & Implementation
- Implementation Examples
A Queue is a linear structure which follows a FIFO order for operations.
In a queue, the element deleted is always that one that has been in the set for the longest time: first-in, first-out, or FIFO.
There are several implementations, we will focus on a simple array to implement each.
Queue is used when things don't have to be processed immediately, but have to be processed in *FIFO order like Breadth First Search. This property of Queue makes it also useful in following other scenarios:
- A resource is shared among multiple consumers.
- CPU Scheduling
- Disk Scheduling
- Data is transferred asynxchronously (not necessarily received at same rate as sent) between two processes.
- IO Buffers
- Pipes
- File IO
- Operating Systems
- Semaphores
- FCFS (First Come First Serve) scheduling
- Spooling in printers
- Buffer for devices like keyboard
- Networks
- Queues in routers/switches
- Mail Queues
ENQUEUE(Q, x)
Q[Q.tail] = x
if Q.tail == Q.length
Q.tail = 1
else Q.tail = Q.tail + 1
DEQUEUE(Q)
x = Q[Q.head]
if Q.head == Q.length
Q.head = 1
else Q.head = Q.head + 1
return x
- Array Implementation
- Linked List Implementation
- Stack Implementation
- Time Complexity O(1) for enque & deque.
- Space Complexity O(N) for N elements to store.
- Easy to implement
- Static Data Structure -> fixed size.
- If the queue has a large number of enqueue and dequeue operations, at some point (in case of linear increment of front and rear indexes), we may not be able to insert elements in the queue even if the queue is empty.
- Time Complexity O(1) for enque & deque.
- Space Complexity O(N) for N elements to store.
- A queue can be implemented using two stacks. You need to decide whether to make enqueue or dequeue operation costly O(N) and the other one O(1).
- Space complexity O(N)
This method makes sure the oldest entered element is always at the top of stack 1, so that the dequeue operation just pops from stack1. To put the element at top of stack1, stack2 is used.
- While stack1 is not empty, push everything from stack1 to stack2.
- Push x to stack1 (assuming size of stacks is unlimited)
- Push everything back to stack1.
This method push new elements at the top of stack1. In dequeue operation, if stack2 is empty, then all the elements are moved to stack2 and finally top of stack2 is returned.
java.util
provides a Queue
interface that extends the Collection
interface, and the most common concrete classes that implement it are PriorityQueue
and LinkedList
(both implementations are not thread safe, PriorityBlockingQueue
is one alternative implementation if thread safe implementation is needed)
See more examples in my [Datastructures in Java repositroy]((https://github.com/herrera-ignacio/datastructures-in-java/tree/master/src/main/java/linear/queue).