Day 2 - Queues & Stacks

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.