Thursday, June 26, 2014

Linked List implementation of Queue Data Structure in Java

Linked List implementation of Queue Data Structure in Java
A Queue is a data structure for storing data similar to Linked List and Stack. In Queue, the order in which data arrives is important. In general, a queue is a line of people or things waiting to be served in sequential order stating at the beginning of the line.

A queue is an ordered list in which insertions are done at one end (rear) and deletion done at other end (front). The first element to be inserted is the first one to be deleted. Hence, it is called as First in First Out(FIFO) or Last in Last Out (LILO).

This is some what similar to Stack. When an element is inserted in a queue, the concept is called EnQueue and when an element is removed from the queue, the concept is called DeQueue.Trying to DeQueue an empty Queue is called as underflow and trying to EnQueue an full queue is called overflow. Generally, we treat them as exceptions.

Queue Operations
Main Operations

  • enQueue(int data) : Insert an element at the end of the queue
  • deQueue() : Removes and element an element at the front of the queue
Auxiliary Operations
  • int Front() : Returns the element at the front without removing it.
  • int QueueSize() : Returns the queue size.
  • int isEmpty() : Indicates whether element are stored.

Implementation of Queue
Linked List is one of the implementation of Queue, in which EnQueue operation is implemented by inserting element at the end of the list and DeQueue operation is implemented by deleting an element from the beginning of the list.

Source : wikipedia

Queue Exception class

For ListNode class refer Linked List



Space Complexity : O(n)
Time Complexity : enQueue and deQueue operations O(1)

Download Code : QueueException Queue QueueDemo

If you know anyone who has started learning Java, why not help them out! Just share this post with them. Thanks for studying today!...

No comments:

Post a Comment