Queues
Queues are data structures that follow the pattern of FIFO(first-in, first-out). It is similar to people standing in a queue. The first person gets serviced first.
The third person gets serviced after the first and second persons.
Similarly, in a queue, to get to the third element, first and second element need to be retrieved.
A simple implementation of a queue.
import java.util.LinkedList;
// Queue operate in FIFO. So, the first element added, gets out first.So, if we have to get the third element,
//we need to remove the first two elements to get to the third element
//Operations of a queue
// Check if queue is empty
// Get size of queue
// Enqueue - Add element to a queue
// Dequeue - Remove element from a queue. Usually the first element gets removed.
// Peek - Get the first element from a queue
public class
Queue {
private LinkedList queue;
public Queue(){
queue = new LinkedList();
}
public boolean isEmpty(){
return queue.isEmpty();
}
public int size(){
return queue.size();
}
public void enqueue(int data){
queue.add(data);
}
public int dequeue(){
return (int)queue.remove(0);// When you remove the first element from a linked list, the second element becomes the head.
}
public int peek(){
return (int)queue.get(0);
}
public static void main(String[] args) {
Queue queue = new Queue();
queue.enqueue(5);
queue.enqueue(6);
queue.enqueue(7);
System.out.println("Size of queue:"+queue.size());
System.out.println("First element:"+queue.dequeue());
System.out.println("First element:"+queue.peek());
System.out.println("Second element:"+queue.dequeue());
System.out.println("Third element:"+queue.dequeue());
System.out.println("Is the queue emepty:"+queue.isEmpty());
System.out.println("Size of queue after dequeuing:"+queue.size());
}
}
Output:
Size of queue:3
First element:5
First element:6
Second element:6
Third element:7
Is the queue emepty:true
Size of queue after dequeuing:0
Java does have a Queue Interface where the above operations as well as some other useful methods are available, which can be implemented using LinkedList.
The only way to traverse a stack or a queue is to pop/dequeue - which means we remove all the elements in the queue to get to the desired element/index. So, unless we store the dequeued /popped elements in another variable, they will be lost.
Stacks
Stack is a data structure which behaves in the LIFO (last-in, first-out) fashion.
Taking the example of people standing a queue, the last person who came in, gets serviced first. And the first person gets serviced last. (Sounds weird, isn't it?)
Java already has a built in feature class called stack.
Stack has the following features:
Push: Push/Inset an element.
Pop: Pop/Remove element
Peek: Returns the first element.
Taking an example:
import java.util.Stack;
public class StackEx {
public static void main(String[] args) {
Stack strStack = new Stack();
strStack.push("Hi ");
strStack.push("There ");
System.out.println("First element/Peek:"+strStack.peek());
System.out.print(strStack.pop());
System.out.println(strStack.pop()+"!");
}
}
Output:
First element/Peek:There
There Hi !
The first element pushed into the stack was 'Hi'. But the first element popped out was 'There'.
Another point is if we do a peek() operation after all the pop operations, it will give an IndexOutOfBoundsException. . Because, just like queues, when all elements are popped, the stack becomes empty.
Comparing it with Queue.
public static void main(String[] args) {
Queue queue = new Queue();
queue.enqueue("Hi ");
queue.enqueue("There ");
System.out.print(queue.dequeue());
System.out.println(queue.dequeue()+"!");
}
Output:
Hi There !
The queue pops out in whatever way the elements are inserted into the queue.
