Stack Data Structure

Stack is a fundamental linear data structure that operates based on a specific order of operations. This structure adheres to either LIFO (Last In First Out) or FILO (First In Last Out) principles. In LIFO, the last element inserted is the first one to be removed, while in FILO, the first element inserted is the last one to be removed.

Understanding the Stack Data Structure

A stack represents a linear data structure that strictly follows the Last-In-First-Out (LIFO) concept. It can be likened to a stack of plates, where the most recently added plate is the first to be taken out. This characteristic distinguishes stacks from other data structures and plays a crucial role in various computing applications.d.

Basic Operations of Stack Data Structures:

• Push: This operation adds an element to the top of the stack.

• Pop: When this operation is executed, it removes the top element from the stack.

• Peek: By using this operation, you can retrieve the top element without removing it.

• IsEmpty: This operation checks whether the stack is empty or not.

• IsFull: In the case of fixed-size arrays, this operation checks if the stack is full.

Understanding the Working of Stack

The stack operates based on the Last-In-First-Out (LIFO) principle. In the illustration below, you can see a stack consisting of five memory blocks, indicating that its size is limited to 5.

Let's consider a scenario where we aim to store elements in a stack, starting with an empty stack. The stack size is set to 5, and as demonstrated below, we progressively push elements into the stack until it reaches its maximum capacity.

When we engage in the delete operation on a stack, the process involves a single entry and exit point due to the closure of the other end. This adheres to the Last In First Out (LIFO) pattern, meaning that the first value entered will be the last one removed. In the scenario mentioned earlier, where the value 5 is the initial entry, it will only be removed after all other elements have been deleted.

PUSH Operation

The PUSH operation entails the following steps:

• Before adding an element to a stack, we verify if the stack has reached its full capacity.

• If an attempt is made to insert an element into a full stack, it triggers an overflow situation.

• Upon initializing a stack, the top value is initially set to -1 to indicate an empty stack.

• When a new element is pushed into the stack, the top value is incremented by one, i.e., top = top + 1, and the element is placed at the new top position.

• Elements continue to be inserted until the stack reaches its maximum size.

POP Operation

The POP operation involves the following steps:

• Prior to removing an element from the stack, we verify if the stack is empty.

• If an attempt is made to delete an element from an empty stack, it results in an underflow condition.

• If the stack is not empty, we first access the element pointed to by the top.

• Upon completion of the pop operation, the top value is decremented by 1, i.e., top = top - 1.

Applications of Stack Data Structures:

• Recursion

• Expression Evaluation and Parsing

• Depth-First Search (DFS)

Easy Problems on Stack Data Structures:

• Infix to Postfix Conversion using Stack

• Prefix to Infix Conversion

• Prefix to Postfix Conversion

• Postfix to Prefix Conversion

• Postfix to Infix

• Convert Infix To Prefix Notation

• Check for balanced parentheses in an expression

• Arithmetic Expression Evalution

• Evaluation of Postfix Expression

• Reverse a stack using recursion

• Reverse individual words

• Reverse a string using stack

• Reversing a Queue

Medium Problems on Stack Data Structures:

• How to create mergable stack?

• The Stock Span Problem

• Next Greater Element

• Next Greater Frequency Element

• Maximum product of indexes of next greater on left and right

• Iterative Tower of Hanoi

• Sort a stack using a temporary stack

• Reverse a stack without using extra space in O(n)

• Delete middle element of a stack

• Check if a queue can be sorted into another queue using a stack

• Check if an array is stack sortable

• Iterative Postorder Traversal | Set 1 (Using Two Stacks)

• Largest Rectangular Area in a Histogram | Set 2

• Find maximum of minimum for every window size in a given array

• Find index of closing bracket for a given opening bracket in an expression

• Find maximum difference between nearest left and right smaller elements

• Delete consecutive same words in a sequence

• Check mirror in n-ary tree

• Reverse a number using stack

• Reversing the first K elements of a Queue

Hard Problems on Stack Data Structures:

• The Celebrity Problem

• Print next greater number of Q queries

• Iterative Postorder Traversal | Set 2 (Using One Stack)

• Print ancestors of a given binary tree node without recursion

• Length of the longest valid substring

• Expression contains redundant bracket or not

• Find if an expression has duplicate parenthesis or not

• Find next Smaller of next Greater in an array

• Iterative method to find ancestors of a given binary tree

• Stack Permutations (Check if an array is stack permutation of other)

• Spaghetti Stack

• Remove brackets from an algebraic string containing + and – operators

• Range Queries for Longest Correct Bracket Subsequence