Stacks

Concept of Stacks

A stack is a linear data structure that follows the Last In First Out (LIFO) principle. This means that the last element added to the stack will be the first one to be removed. Think of a stack as a pile of plates - you can only take the top plate, and you can only add a new plate to the top.

Stacks are used in various applications in computer science, including expression evaluation, syntax parsing, backtracking algorithms, and function call management in programming languages.

    ┌───┐
    │ D │ ← Top (Last In)
    ├───┤
    │ C │
    ├───┤
    │ B │
    ├───┤
    │ A │ ← Bottom (First In)
    └───┘
                        

Key Characteristics of Stacks

• LIFO (Last In First Out): The last element inserted is the first one to be removed.
• Dynamic Size: The size of the stack can grow and shrink as elements are pushed and popped.
• Single Point of Access: Elements can only be accessed from the top of the stack.
• Restricted Operations: Only a limited set of operations are allowed on a stack.

Primitive Operations

A stack supports the following basic operations:

1. Push

The push operation adds an element to the top of the stack. If the stack is full, this operation may result in a stack overflow.

Before Push(E):       After Push(E):
    ┌───┐                ┌───┐
    │ D │ ← Top          │ E │ ← Top
    ├───┤                ├───┤
    │ C │                │ D │
    ├───┤                ├───┤
    │ B │                │ C │
    ├───┤                ├───┤
    │ A │                │ B │
    └───┘                ├───┤
                         │ A │
                         └───┘
                        

2. Pop

The pop operation removes the top element from the stack and returns it. If the stack is empty, this operation may result in a stack underflow.

Before Pop():         After Pop():
    ┌───┐                ┌───┐
    │ D │ ← Top          │ C │ ← Top
    ├───┤                ├───┤
    │ C │                │ B │
    ├───┤                ├───┤
    │ B │                │ A │
    ├───┤                └───┘
    │ A │                
    └───┘                
                        

3. Peek (or Top)

The peek operation returns the top element of the stack without removing it. If the stack is empty, this operation may return an error or a special value.

Stack:                Peek() returns D
    ┌───┐             (Stack remains unchanged)
    │ D │ ← Top
    ├───┤
    │ C │
    ├───┤
    │ B │
    ├───┤
    │ A │
    └───┘
                        

4. isEmpty

The isEmpty operation checks if the stack is empty. It returns true if the stack has no elements, and false otherwise.

5. isFull

The isFull operation checks if the stack is full. It returns true if the stack cannot accommodate any more elements, and false otherwise. This operation is relevant only for stacks with a fixed size.

6. Size

The size operation returns the number of elements currently in the stack.

Abstract Data Type

A stack is an abstract data type (ADT) that specifies a collection of elements with specific operations but does not specify how these operations are implemented. The ADT defines what operations are allowed on the data structure, but not how these operations are implemented.

Stack ADT Specification

The Stack ADT can be defined as follows:

ADT Stack {
    // Data
    A collection of elements with LIFO access
    
    // Operations
    void push(element)     // Add element to the top of the stack
    element pop()          // Remove and return the top element
    element peek()         // Return the top element without removing it
    boolean isEmpty()      // Check if the stack is empty
    boolean isFull()       // Check if the stack is full
    int size()             // Return the number of elements in the stack
}
                    

This ADT specification defines what a stack is and what operations it supports, but it does not specify how these operations are implemented. The implementation can vary depending on the underlying data structure used (e.g., array, linked list).

Representation of Stacks Using Arrays

One of the most common ways to implement a stack is using an array. In this implementation, we use an array to store the elements and a variable to keep track of the top of the stack.

Array Implementation of Stack

Here's a C++ implementation of a stack using an array:

#include <iostream>
using namespace std;

class Stack {
private:
    int* arr;       // Array to store stack elements
    int capacity;   // Maximum capacity of the stack
    int top;        // Index of the top element
    
public:
    // Constructor
    Stack(int size) {
        arr = new int[size];
        capacity = size;
        top = -1;   // Initialize top as -1 (empty stack)
    }
    
    // Destructor
    ~Stack() {
        delete[] arr;
    }
    
    // Push operation
    void push(int x) {
        if (isFull()) {
            cout << "Stack Overflow" << endl;
            return;
        }
        
        arr[++top] = x;
        cout << x << " pushed to stack" << endl;
    }
    
    // Pop operation
    int pop() {
        if (isEmpty()) {
            cout << "Stack Underflow" << endl;
            return -1;
        }
        
        return arr[top--];
    }
    
    // Peek operation
    int peek() {
        if (isEmpty()) {
            cout << "Stack is empty" << endl;
            return -1;
        }
        
        return arr[top];
    }
    
    // Check if stack is empty
    bool isEmpty() {
        return top == -1;
    }
    
    // Check if stack is full
    bool isFull() {
        return top == capacity - 1;
    }
    
    // Get size of stack
    int size() {
        return top + 1;
    }
    
    // Display stack elements
    void display() {
        if (isEmpty()) {
            cout << "Stack is empty" << endl;
            return;
        }
        
        cout << "Stack elements: ";
        for (int i = 0; i <= top; i++) {
            cout << arr[i] << " ";
        }
        cout << endl;
    }
};

int main() {
    Stack s(5);
    
    s.push(10);
    s.push(20);
    s.push(30);
    
    s.display();
    
    cout << "Top element: " << s.peek() << endl;
    cout << "Stack size: " << s.size() << endl;
    
    cout << s.pop() << " popped from stack" << endl;
    
    s.display();
    
    return 0;
}
                    

Advantages of Array Implementation

• Simple and Easy to Implement: Array implementation of a stack is straightforward.
• Memory Efficient: No extra memory is required for pointers as in linked list implementation.
• Cache Friendly: Arrays have good locality of reference, which can lead to better cache performance.

Disadvantages of Array Implementation

• Fixed Size: The size of the stack is fixed and cannot be changed during runtime.
• Stack Overflow: If the stack is full, pushing more elements will result in a stack overflow.
• Memory Wastage: If the stack is not fully utilized, memory is wasted.

Prefix, Infix, Postfix Notations for Arithmetic Expression

Arithmetic expressions can be written in three different notations: infix, prefix, and postfix. Each notation has its own advantages and use cases.

1. Infix Notation

Infix notation is the conventional way of writing arithmetic expressions, where the operator is placed between the operands. For example, A + B.

Infix notation is easy for humans to read and write, but it requires parentheses to specify the order of operations and is more complex for computers to evaluate directly.

2. Prefix Notation (Polish Notation)

In prefix notation, the operator is placed before the operands. For example, + A B is the prefix notation for A + B.

Prefix notation was introduced by the Polish mathematician Jan Łukasiewicz, hence it is also known as Polish notation. It eliminates the need for parentheses and is easier for computers to parse.

3. Postfix Notation (Reverse Polish Notation)

In postfix notation, the operator is placed after the operands. For example, A B + is the postfix notation for A + B.

Postfix notation, also known as Reverse Polish Notation (RPN), is widely used in computer science because it is easy to evaluate using a stack and does not require parentheses to specify the order of operations.

Comparison of Notations

Let's compare the three notations with some examples:

Applications of Stacks

Stacks have numerous applications in computer science and programming. Let's explore some of the most common ones:

1. Converting Infix Expression to Postfix Expression

One of the most common applications of stacks is converting infix expressions to postfix expressions. This conversion is useful because postfix expressions are easier to evaluate using a computer.

Algorithm for Infix to Postfix Conversion

C++ Implementation

#include <iostream>
#include <stack>
#include <string>
using namespace std;

// Function to check if a character is an operand
bool isOperand(char c) {
    return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') || (c >= '0' && c <= '9');
}

// Function to get the precedence of an operator
int precedence(char op) {
    if (op == '+' || op == '-')
        return 1;
    if (op == '*' || op == '/')
        return 2;
    if (op == '^')
        return 3;
    return -1;
}

// Function to convert infix expression to postfix
string infixToPostfix(string infix) {
    stack s;
    string postfix = "";
    
    for (int i = 0; i < infix.length(); i++) {
        char c = infix[i];
        
        // If the scanned character is an operand, add it to the output string
        if (isOperand(c)) {
            postfix += c;
        }
        // If the scanned character is an opening parenthesis, push it onto the stack
        else if (c == '(') {
            s.push(c);
        }
        // If the scanned character is a closing parenthesis, pop and add to output string until an opening parenthesis is encountered
        else if (c == ')') {
            while (!s.empty() && s.top() != '(') {
                postfix += s.top();
                s.pop();
            }
            if (!s.empty() && s.top() == '(') {
                s.pop();  // Remove the opening parenthesis
            }
        }
        // If the scanned character is an operator
        else {
            while (!s.empty() && precedence(c) <= precedence(s.top())) {
                postfix += s.top();
                s.pop();
            }
            s.push(c);
        }
    }
    
    // Pop any remaining operators from the stack and add to the output string
    while (!s.empty()) {
        postfix += s.top();
        s.pop();
    }
    
    return postfix;
}

int main() {
    string infix = "a+b*(c^d-e)^(f+g*h)-i";
    string postfix = infixToPostfix(infix);
    
    cout << "Infix expression: " << infix << endl;
    cout << "Postfix expression: " << postfix << endl;
    
    return 0;
}
                    

2. Evaluating Postfix Expression

Another common application of stacks is evaluating postfix expressions. Postfix expressions are easier to evaluate using a stack because they don't require parentheses or operator precedence rules.

Algorithm for Evaluating Postfix Expression

C++ Implementation

#include <iostream>
#include <stack>
#include <string>
#include <cmath>
using namespace std;

// Function to check if a character is an operand
bool isOperand(char c) {
    return (c >= '0' && c <= '9');
}

// Function to perform an operation
int performOperation(int a, int b, char op) {
    switch (op) {
        case '+': return a + b;
        case '-': return a - b;
        case '*': return a * b;
        case '/': return a / b;
        case '^': return pow(a, b);
        default: return 0;
    }
}

// Function to evaluate a postfix expression
int evaluatePostfix(string postfix) {
    stack s;
    
    for (int i = 0; i < postfix.length(); i++) {
        char c = postfix[i];
        
        // If the scanned character is an operand, push it onto the stack
        if (isOperand(c)) {
            s.push(c - '0');  // Convert char to int
        }
        // If the scanned character is an operator
        else {
            int val1 = s.top();
            s.pop();
            int val2 = s.top();
            s.pop();
            
            // Perform the operation and push the result back onto the stack
            s.push(performOperation(val2, val1, c));
        }
    }
    
    // The result will be at the top of the stack
    return s.top();
}

int main() {
    string postfix = "23*5+";
    int result = evaluatePostfix(postfix);
    
    cout << "Postfix expression: " << postfix << endl;
    cout << "Result: " << result << endl;
    
    return 0;
}
                    

3. Checking Well-formed (Nested) Parenthesis

Stacks are also used to check if an expression has well-formed (properly nested) parentheses. This is a common problem in compilers and text editors.

Algorithm for Checking Well-formed Parenthesis

C++ Implementation

#include <iostream>
#include <stack>
#include <string>
using namespace std;

// Function to check if brackets are balanced
bool areBracketsBalanced(string expr) {
    stack s;
    
    for (int i = 0; i < expr.length(); i++) {
        char c = expr[i];
        
        // If the current character is an opening bracket, push it onto the stack
        if (c == '(' || c == '{' || c == '[') {
            s.push(c);
        }
        // If the current character is a closing bracket
        else if (c == ')' || c == '}' || c == ']') {
            // If the stack is empty, return false
            if (s.empty()) {
                return false;
            }
            
            // Check if the closing bracket matches the corresponding opening bracket
            char top = s.top();
            if ((c == ')' && top == '(') || (c == '}' && top == '{') || (c == ']' && top == '[')) {
                s.pop();
            } else {
                return false;
            }
        }
    }
    
    // If the stack is empty, all brackets are balanced
    return s.empty();
}

int main() {
    string expr = "{[()]}";
    
    if (areBracketsBalanced(expr)) {
        cout << "Brackets are balanced" << endl;
    } else {
        cout << "Brackets are not balanced" << endl;
    }
    
    return 0;
}
                    

4. Processing of Function Calls

Stacks are used by compilers to manage function calls. When a function is called, its return address and parameters are pushed onto the stack. When the function returns, these values are popped from the stack.

This is known as the call stack, and it allows for nested function calls and recursion. Each function call creates a new stack frame that contains the function's local variables and parameters.

Function Call: main() -> func1() -> func2()

Call Stack:
    ┌───────────┐
    │  func2    │ ← Top
    │  frame    │
    ├───────────┤
    │  func1    │
    │  frame    │
    ├───────────┤
    │  main     │
    │  frame    │
    └───────────┘
                        

5. Reversing a String

Stacks can be used to reverse a string. By pushing each character of the string onto a stack and then popping them, we get the characters in reverse order.

Algorithm for Reversing a String

C++ Implementation

#include <iostream>
#include <stack>
#include <string>
using namespace std;

// Function to reverse a string using a stack
string reverseString(string str) {
    stack s;
    
    // Push each character onto the stack
    for (int i = 0; i < str.length(); i++) {
        s.push(str[i]);
    }
    
    // Pop each character from the stack and append to the result
    string result = "";
    while (!s.empty()) {
        result += s.top();
        s.pop();
    }
    
    return result;
}

int main() {
    string str = "Hello, World!";
    string reversed = reverseString(str);
    
    cout << "Original string: " << str << endl;
    cout << "Reversed string: " << reversed << endl;
    
    return 0;
}
                    

Other Applications of Stacks

• Undo Mechanism: Stacks are used to implement the undo feature in text editors and other applications.
• Browser History: The back button in web browsers uses a stack to keep track of the previously visited pages.
• Depth-First Search: Stacks are used in the implementation of depth-first search algorithm for traversing or searching tree or graph data structures.
• Expression Evaluation: Stacks are used to evaluate expressions in programming languages.
• Backtracking Algorithms: Stacks are used in backtracking algorithms to keep track of the state of the search.

Summary

In this section, we covered stacks, a fundamental data structure in computer science:

• Concept of stacks and their LIFO (Last In First Out) property
• Primitive operations on stacks: push, pop, peek, isEmpty, isFull, size
• Stack as an Abstract Data Type (ADT)
• Implementation of stacks using arrays
• Prefix, infix, and postfix notations for arithmetic expressions
• Applications of stacks:
  • Converting infix expressions to postfix expressions
  • Evaluating postfix expressions
  • Checking well-formed (nested) parentheses
  • Processing function calls
  • Reversing a string

Stacks are versatile data structures with numerous applications in computer science and programming. Understanding stacks is essential for solving many algorithmic problems and implementing various features in software applications.