Introduction to Stack Data Structure with Practical Examples

A stack data structure operates similarly to adding or removing plates from a stack of plates. It follows the Last In, First Out (LIFO) principle. Adding a plate to the top and removing from the top ensure that the last plate added is the first one taken. It only lets you add or remove plates from the top and doesn’t allow any changes in other parts of the stack.

¶Stack Data Structure

A stack is a fundamental data structure in computer science that operates on the Last-In-First-Out ( LIFO ) principle. The last element added is the first to be removed, creating a sequential order where the most recent addition is the priority for removal.

Stack is a versatile data structure and find applications across various domains in computer science. They are essential for tasks such as tracking function calls in programs, managing memory efficiently, and undo mechanisms in software applications.

¶Operations in Stack

¶Push Operation

The push operation involves adding an element to the top of the stack. The newly added element becomes the top of the stack. It’s like placing a plate on top of a pile of plates. When we push a new plate onto the stack, we’re placing it directly on the top. As a result, the plate we just added becomes the new top of the stack.
Time Complexity: O(1) - Constant time complexity, as the push operation does not depend on the size of the stack.

¶Pop Operation

The pop operation removes the element from the top of the stack. After this operation, the element below the removed one becomes the new top. it’s like removing the top plate from a pile of plates. The plate just below the one we removed becomes the new top.
Time Complexity: O(1) - Constant time complexity, as the pop operation’s duration is independent of the stack’s size.

¶Peek (or Top) Operation

Peek retrieves the element at the top of the stack without removing it. It allows you to inspect the top element without altering the stack.
Time Complexity: O(1) - Constant time complexity, as it involves accessing the top element directly.

¶isEmpty Operation

The isEmpty operation checks if the stack is empty, i.e., it has no elements. It returns a boolean indicating whether the stack is devoid of elements.
Time Complexity: O(1) - Constant time complexity, as checking if the stack is empty doesn’t depend on its size.

¶Implementation of Stack Using Array and Struct in C

#include #include #define MAX_SIZE 100 // Define the stack structure struct Stack < int arr[MAX_SIZE]; int top; >; // Function to initialize the stack void initialize(struct Stack *stack) < stack->top = -1; // Initialize top to -1 to indicate an empty stack > // Function to check if the stack is empty int isEmpty(struct Stack *stack) < return stack->top == -1; > // Function to check if the stack is full int isFull(struct Stack *stack) < return stack->top == MAX_SIZE - 1; > // Function to push an element onto the stack void push(struct Stack *stack, int element) < if (isFull(stack)) < printf("Stack Overflow: Cannot push element %d, stack is full.\n", element); return; >stack->arr[++stack->top] = element; printf("Pushed %d onto the stack.\n", element); > // Function to pop an element from the stack int pop(struct Stack *stack) < if (isEmpty(stack)) < printf("Stack is empty. Cannot pop from an empty stack.\n"); return -1; // Return a special value to indicate underflow >int poppedElement = stack->arr[stack->top--]; printf("Popped %d from the stack.\n", poppedElement); return poppedElement; > // Function to get the top element without removing it int peek(struct Stack *stack) < if (isEmpty(stack)) < printf("Stack is empty. No element to peek.\n"); return -1; // Return a special value to indicate underflow >return stack->arr[stack->top]; > int main() < // Declare and initialize a stack struct Stack myStack; initialize(&myStack); // Push elements onto the stack push(&myStack, 10); push(&myStack, 20); push(&myStack, 30); // Peek at the top element printf("Top element: %d\n", peek(&myStack)); // Pop elements from the stack pop(&myStack); pop(&myStack); pop(&myStack); // Try popping from an empty stack pop(&myStack); return 0; >

Output:
Pushed 10 onto the stack.
Pushed 20 onto the stack.
Pushed 30 onto the stack.
Top element: 30
Popped 30 from the stack.
Popped 20 from the stack.
Popped 10 from the stack.
Stack is empty. Cannot pop from an empty stack.

¶Stack Overflow and Stack Underflow

Stack overflow occurs when an attempt is made to push an element onto a stack that is already at its maximum capacity, leading to a situation where there is no more space for additional elements. Stack underflow occurs when an attempt is made to pop an element from an empty stack, where there are no elements to remove.

#include #define MAX_SIZE 3 int stack[MAX_SIZE]; int top = -1; // Function to push an element onto the stack void push(int element) < if (top == MAX_SIZE - 1) < printf("Stack Overflow: Cannot push %d, stack is full.\n", element); return; >stack[++top] = element; printf("Pushed %d onto the stack.\n", element); > // Function to pop an element from the stack int pop() < if (top == -1) < printf("Stack Underflow: Cannot pop from an empty stack.\n"); return -1; // Return a special value to indicate underflow >printf("Popped %d from the stack.\n", stack[top]); return stack[top--]; > int main() < // Attempting to push more elements than the stack can hold push(1); push(2); push(3); push(4); // This will cause a stack overflow pop(); pop(); pop(); // Attempting to pop from an empty stack pop(); // This will cause a stack underflow return 0; >

Output:
Pushed 1 onto the stack.
Pushed 2 onto the stack.
Pushed 3 onto the stack.
Stack Overflow: Cannot push 4, stack is full.
Popped 3 from the stack.
Popped 2 from the stack.
Popped 1 from the stack.
Stack Underflow: Cannot pop from an empty stack.

Here, we first attempt to push more elements than the stack’s capacity, causing a stack overflow. Subsequently, we attempt to pop elements from an empty stack, resulting in a stack underflow. These scenarios highlight the importance of checking the stack’s status before performing push and pop operations to prevent overflow and underflow.

¶Stack in C++ STL

The C++ STL stack provides a convenient way to implement and use stacks, offering various methods for common stack operations. To use the stack in C++ STL , we need to include the header.

¶Functions in C++ STL Stack

• empty() Checks if the stack is empty. Returns true if the stack has no elements; otherwise, returns false.
  
• size() Returns the number of elements in the stack.
  
• push() Adds an element to the top of the stack.
  
• pop() Removes the top element from the stack.
• top() Provides access to the top element without removing it. Retrieves a reference to the top element.
  

Here’s a simple example that demonstrates how to declare a stack, push elements onto it, pop elements from it, and perform other common operations:

#include #include int main() < // Declare a stack of integers std::stackmyStack; // Push elements onto the stack myStack.push(10); myStack.push(20); myStack.push(30); // Display the size of the stack std::cout else < std::cout return 0; > 

¶Applications of Stack

• Function Call Management: Stacks are used to manage function calls in programming languages. When a function is called, its context is pushed onto the stack, and when the function completes, its context is popped off.
• Expression Evaluation: Stacks help in evaluating expressions, especially arithmetic expressions. They are used to convert infix expressions to postfix or prefix form, making them easier to evaluate.
• Undo Mechanisms in Software: Stacks are employed to implement undo functionalities in software applications. Each action performed is pushed onto the stack, allowing easy reversal of operations.
• Memory Management: Stacks are used in memory management to keep track of allocated memory. Local variables and function call information are stored on the stack during program execution.
• Backtracking Algorithms: Stacks are instrumental in backtracking algorithms. They store the state of the system at different decision points, allowing the algorithm to backtrack when needed.
• Browser History Implementation: Stacks can be used to implement the back and forward buttons in web browsers. Each visited page is pushed onto the stack, allowing easy navigation.
• Parentheses Matching: Stacks are employed to check the correctness of parentheses in expressions. Each opening parenthesis is pushed onto the stack, and when a closing parenthesis is encountered, it is matched with the top element.

¶Infix to Postfix Expression Conversion Using Stack

Infix to postfix conversion involves converting an infix expression to a postfix expression using a stack. Here’s a basic algorithm and explanation of how to perform infix to postfix conversion using a stack:

Let’s convert the infix expression "3 + 5 * ( 2 - 8 )" to postfix:

• Scan from left to right:

1. Operand 3 , add to postfix.
2. Operator + , push onto stack.
3. Operand 5 , add to postfix.
4. Operator *' push onto stack.
5. Open parenthesis ( , push onto stack.
6. Operand 2 , add to postfix.
7. Operator ‘-’, push onto stack.
8. Operand 8, add to postfix.
9. Close parenthesis ‘)’, pop operators and add to postfix until ( is encountered.
10. Pop * , add to postfix.
11. Pop + add to postfix.
12. Postfix expression: "3 5 2 8 - * +"

This postfix expression is equivalent to the original infix expression “3 + 5 * ( 2 - 8 )”.

#include #include #include bool isOperator(char ch) < return (ch == '+' || ch == '-' || ch == '*' || ch == '/'); >int getPrecedence(char op) < if (op == '+' || op == '-') < return 1; >else if (op == '*' || op == '/') < return 2; >return 0; // For '(' > std::string infixToPostfix(const std::string& infix) < std::stackoperatorStack; std::string postfix; for (char ch : infix) < if (std::isalnum(ch)) < postfix += ch; // Operand, add to postfix >else if (isOperator(ch)) < while (!operatorStack.empty() && getPrecedence(operatorStack.top()) >= getPrecedence(ch)) < postfix += operatorStack.top(); operatorStack.pop(); >operatorStack.push(ch); > else if (ch == '(') < operatorStack.push(ch); >else if (ch == ')') < while (!operatorStack.empty() && operatorStack.top() != '(') < postfix += operatorStack.top(); operatorStack.pop(); >operatorStack.pop(); // Discard '(' > > // Pop remaining operators from the stack while (!operatorStack.empty()) < postfix += operatorStack.top(); operatorStack.pop(); >return postfix; > int main()

¶Run C Programming Online Compiler

To make your learning more effective, exercise the coding examples in the text editor below.