Stacks & Queues

Stack and Queue are fundamental data structures in Java Collections Framework. They are used to store the same type of data and retrieve the data in a specific order. Stack and Queue both are Linear Data Structures.

• Stack follows the LIFO principle i.e. Last In First Out.
• Queue follows the FIFO principle i.e. First In First Out.

Introduction to Stack

A stack is an abstract, linear data type with a predefined capacity (or boundary). It follows a particular order for adding or removing elements.

The name “stack” is derived from a stack of plates. So, when we need a plate, we take (pop) from the top of the stack, and when we want to add a plate, we put (push) it at the top as well. We cannot add or remove a plate at the middle of the stack.

They are used in many applications. One such application is the undo mechanism in text editors. All the changes are stored in a stack. When you undo something, it pops the most recent action. When you make changes, it pushes changes onto the stack.

1. Books and Clothes
2. Floors in a Building
3. Browsers
4. Mobile Phone Call Log
5. Women’s Bangles

Source

Implementation of Stack

The Java collections framework has a Stack Class that provides the functionality of the Stack Data structure. The Stack class extends the Vector class.

• Firstly we need to import java.util.Stack package.
• General syntax to declare stack

import java.util.Stack;

//For declaring Stack object
Stack<Object> stacks;

The object can be Integer, String, Character, Float, etc.

NOTE: The stack can store only one type of data.

• Syntax to initialise the stack:

import java.util.Stack;

//For declaring Stack object
Stack<Object> stacks;

stacks = new Stack<>();

//Example stack of Integer datatype.
Stack<Integer> stack = new Stack<>();

Methods in Stack Class

1. push(e): Adds element e to the top of the stack. Syntax: <stack_name>.push(<variable_name>);
2. pop(): Removes and returns the top element from the stack. If the stack is empty, it throws an exception(EmptyStackException). Syntax: <stack_name>.pop();
3. peek():Returns the top element of the stack without removing it. If the stack is empty, it throws an exception. Syntax: <stack_name>.peek();
4. size(): Returns the number of elements in the stack. Syntax: <stack_name>.size();
5. empty(): Returns a Boolean indicating whether the stack is empty. Syntax: <stack_name>.empty();

import java.util.Stack;

Stack<Integer> stack = new Stack<>();

//To add elements to the stack:
stack.push(45);
stack.push(55);
stack.push(75);

//To remove element at the top:
stack.pop();      //This will remove 75 from the stack

stack.peek();        //It will return 55 value without deleting it.

stack.size();      //It will return 2 as 55 & 45 are present in stack.

stack.empty();    //It will return false as the stack is not empty

Introduction to Queue

• Queue is an abstract data structure, somewhat similar to Stacks. Unlike stacks, a queue is open at both its ends. One end is always used to insert data (enqueue) and the other is used to remove data (dequeue).
• It is a collection of objects that are inserted at the rear end of the list and are deleted from the front end of the list.

Source

Implementation of Queue

Queue is a datatype. queue is the variable name of our queue. This declares the queue. The object is the datatype. All the elements in the Queue have to be of the same datatype. It can be Integer, Float, String, Character, etc.

• Firstly, we will import the queue from Java Collections Framework. This will let us declare Queue. import java.util.Queue;
• General syntax to declare queue:

Queue<Object> queue;

• Syntax to initialise the queue

<variable_name> = new LinkedListQueue(); initialises queue.

Now we can use the queue to store, retrieve and manipulate the data.

queue = new LinkedListQueue<Obj>();

For example:

import java.util.Queue;

Queue<Character> queue = new LinkedListQueue<Character>();

Methods in Queue class

1. enqueue(e): Adds element e to the back of the queue. Syntax: <queue_name>.enqueue(<data>);
2. dequeue(): Removes and returns the first element from the queue. An Exception is thrown if the Queue is empty. Syntax: <queue_name>.dequeue();
3. first(): Returns the first element of the queue without removing it. An Exception is thrown if the Queue is empty. Syntax: <queue_name>.first();
4. size(): Returns the number of elements in the queue. Syntax: <queue_name>.size();
5. isEmpty(): Returns a Boolean indicating whether the queue is empty. Syntax: <queue_name>.isEmpty();
6. add() : Inserts the specified element into the queue. If the task is successful, add() returns true, if not it throws an exception. Syntax: <queue_name>.add(<data>);
7. poll(): Returns and removes the head of the queue. Returns null if the queue is empty.

import java.util.Queue;

Queue<Character> queue = new LinkedListQueue<Character>();

//To enque elements: 
queue.enqueue('g');
queue.enqueue('s');

//To dequeue elements: 
queue.dequeue();

//To retrieve the first element: 
queue.first();

//To find the number of elements: 
queue.size();

//To check if the queue is Empty: 
queue.isEmpty();

//To insert specified element: 
queue.add('a');

//To remove head of the queue: 
queue.poll();

Types of Queue

Circular Queues:

They follow the basic principle of Queues but the last element connects back to the element at First Position, hence forming a circle.

When an element is enqueued, the value of rear is incremented. But it must take into account the need to loop back to index 0, hence the below formula is used to calculate the position of the rear element.

rear = (rear+1) % queue.length;

Source

Priority Queues

A priority Queue is a collection of elements where each element is assigned a priority and the order in which elements are deleted and processed is determined from the following rules:

1. An element of higher priority is processed before any element of lower priority.
2. Two elements with the same priority are processed according to the order in which they are added to the queue.

Source

Stack is used in solving problems and works on recursion.

Queue is used in solving problems having sequential processing.

For queries regarding the content, please drop a mail to loop@cumminscollege.in Links for in-depth studying and practice problems are sent via mail to students of the college on the date of publishing of the blog by Loop Club. The content is a part of DSA Bulletins started by Team Loop, to provide thorough knowledge and facilitate the learning of new topics of DSA. We are a group of students who are passionate about CP and DSA and want to create awareness and help students in the above topics.