Stack, Queue, and Deque Operations

In the world of competitive programming, knowing how to efficiently manipulate data structures is of utmost importance. One such set of data structures that are frequently used are stack, queue, and deque. These data structures have their own unique characteristics and operations that make them suitable for various problem-solving scenarios. In this article, we will delve into the operations associated with stack, queue, and deque, highlighting their differences and providing examples of their usage.

Stack

A stack is a last-in-first-out (LIFO) data structure, where elements are added and removed only from one end called the top. Therefore, the element that is added most recently, i.e., the top element, is the first one to be removed. The operations associated with a stack include:

1. Push: Adds an element to the top of the stack.
2. Pop: Removes and returns the top element from the stack.
3. Peek: Returns the top element of the stack without removing it.
4. isEmpty: Checks if the stack is empty or not.

Stacks find useful applications in problems that require tracking the state of operations or parentheses matching, among others.

Here is an example of creating and using a stack in Java:

Stack<Integer> stack = new Stack<>();
stack.push(5); // pushes 5 to the top of the stack
stack.push(10); // pushes 10 to the top of the stack

int topElement = stack.peek(); // returns 10
int poppedElement = stack.pop(); // removes and returns 10

boolean empty = stack.isEmpty(); // returns false

Queue

Unlike stacks, queues are first-in-first-out (FIFO) data structures. Elements are added to one end called the rear, and are removed from the other end called the front. Therefore, the element that is added first is the first one to be removed. The operations associated with a queue include:

1. Enqueue: Adds an element to the rear end of the queue.
2. Dequeue: Removes and returns an element from the front end of the queue.
3. Peek: Returns the front element of the queue without removing it.
4. isEmpty: Checks if the queue is empty or not.

Queues are widely used in scenarios where elements need to be processed in the order of their arrival, such as scheduling tasks or managing requests.

Here is an example of creating and using a queue in Java:

Queue<Integer> queue = new LinkedList<>();
queue.add(5); // adds 5 to the rear of the queue
queue.add(10); // adds 10 to the rear of the queue

int frontElement = queue.peek(); // returns 5
int dequeuedElement = queue.remove(); // removes and returns 5

boolean empty = queue.isEmpty(); // returns false

Deque

A deque, short for "double-ended queue," is a data structure that supports insertion and removal of elements from both ends. Therefore, it combines the characteristics of both stack and queue. The operations associated with a deque include:

1. AddFirst: Adds an element to the front of the deque.
2. AddLast: Adds an element to the rear of the deque.
3. RemoveFirst: Removes and returns an element from the front of the deque.
4. RemoveLast: Removes and returns an element from the rear of the deque.
5. PeekFirst: Returns the first element of the deque without removing it.
6. PeekLast: Returns the last element of the deque without removing it.
7. isEmpty: Checks if the deque is empty or not.

Deques are versatile data structures that can be used in various scenarios, such as implementing both stack and queue functionalities simultaneously or solving problems that require efficient access and removal from both ends.

Here is an example of creating and using a deque in Java:

Deque<Integer> deque = new LinkedList<>();
deque.addFirst(5); // adds 5 to the front of the deque
deque.addLast(10); // adds 10 to the rear of the deque

int firstElement = deque.peekFirst(); // returns 5
int lastElement = deque.peekLast(); // returns 10

int removedElement = deque.removeFirst(); // removes and returns 5

boolean empty = deque.isEmpty(); // returns false

In conclusion, understanding the operations and characteristics of stack, queue, and deque is crucial for competitive programming tasks. Each data structure has its own unique set of operations that makes it suitable for different problem-solving scenarios. By leveraging these data structures effectively, programmers can efficiently solve a wide range of problems encountered in competitive programming.