Stacks

Introduction

A stack is a linear data structure that follows the Last In First Out (LIFO) principle, meaning the last element added to the stack is the first one to be removed. Stacks can be implemented using arrays or linked lists.

Basic Operations

The main operations associated with a stack are:

• Push: Adding an element to the top of the stack.
• Pop: Removing the top element from the stack.
• Top: Accessing the top element of the stack without removing it.
• IsEmpty: Checking if the stack is empty.

C++ Example

Here's an example of a simple stack implementation in C++ using a linked list:

#include <iostream>

class Node {
public:
    int data;
    Node* next;
};

class Stack {
public:
    Stack() : top(nullptr) {}

    void push(int data) {
        Node* newNode = new Node();
        newNode->data = data;
        newNode->next = top;
        top = newNode;
    }

    void pop() {
        if (!isEmpty()) {
            Node* temp = top;
            top = top->next;
            delete temp;
        }
    }

    int getTop() {
        if (!isEmpty()) {
            return top->data;
        }
        return -1;
    }

    bool isEmpty() {
        return top == nullptr;
    }

private:
    Node* top;
};

int main() {
    Stack stack;

    stack.push(1);
    stack.push(2);
    stack.push(3);

    std::cout << "Top element is: " << stack.getTop() << std::endl;

    stack.pop();
    std::cout << "Top element after pop is: " << stack.getTop() << std::endl;

    return 0;
}

In this example, the Node class represents a single node in the stack, and the Stack class implements the stack operations using a linked list. The push() function adds a new node to the top of the stack, the pop() function removes the top node from the stack, the getTop() function retrieves the top element, and the isEmpty() function checks if the stack is empty.

Applications

Stacks are used in various applications such as:

• Evaluating arithmetic expressions.
• Implementing function calls and recursion in programming languages.
• Reversing a sequence of elements.
• Balancing symbols, like parentheses, in programming languages.

See Also

• Queues
• Linked Lists
• Arrays