Stack

A stack is a data structure that operates on the principle of “Last-In, First-Out” (LIFO). It is an ordered collection of items where the addition of new items and the removal of existing items always take place at the same end, referred to as the “top” of the stack.

Characteristics of a Stack

• LIFO Principle: The last element added to the stack will be the first one to be removed. This is analogous to a stack of plates where only the top plate can be removed.
• Access: Only the top element can be accessed at any given time, which makes the stack a very controlled structure for managing data.

Advantages

• Simple and Easy to Use: Stack operations are straightforward and easy to implement.
• Memory Efficient: Only the top element needs to be accessed or modified, reducing memory access.

Disadvantages

• Limited Access: Only the top element is accessible, limiting direct access to other elements.
• Fixed Size (Array Implementation): The size of the stack might need to be increased or decreased dynamically, which is not possible with a static array implementation.

Basic Operations

• Push: Adds an item to the top of the stack.
• Pop: Removes and returns the item from the top of the stack.
• Peek or Top: Returns the top element of the stack without removing it.
• IsEmpty: Checks if the stack is empty.
• Size: Returns the number of elements in the stack.

Implementation

• Array-Based Implementation: Fixed size, but fast access.
• Linked List-Based Implementation: Dynamic size, but slightly more overhead.

Applications of Stacks

• Expression Evaluation: Used in algorithmic expression evaluation and syntax parsing.
• Backtracking: Essential in algorithms that involve backtracking, such as maze solving or tree traversal.
• Function Calls: Fundamental in managing function calls and recursion in programming languages.
• Undo Mechanisms: Used to implement undo mechanisms in software applications.

Stack.h

#ifndef PIE_STACK_H
#define PIE_STACK_H

#include <vector>
#include <iostream>

template <typename T>
class Stack {
public:
    Stack();
    void push(const T& data);
    void pop();
    const T& top();
    bool isEmpty();

private:
    std::vector<T> stackVector;
};

#endif //PIE_STACK_H

Stack.cpp

#include "Stack.h"

template<typename T>
Stack<T>::Stack() {
    stackVector.reserve(20);
}


template<typename T>
void Stack<T>::push(const T& data) {
    stackVector.push_back(data);
}


template<typename T>
void Stack<T>::pop() {
    if (!stackVector.empty()) {
        stackVector.pop_back();
    }
}


template<typename T>
const T& Stack<T>::top() {
    if (!stackVector.empty()) {
        return stackVector.back();
    }
    throw std::runtime_error("Stack is empty");
}



template<typename T>
bool Stack<T>::isEmpty() {
    if (stackVector.empty())
        return true;
    else
        return false;
}

main.cpp

#include "Stack.h"
#include "Stack.cpp"
#include <ctime>
#include <string>

struct card {
    std::string shape;
    int num;
};

const std::string shapes[] = {"Heart", "Diamond", "Clover", "Spade"};

card generateRandomCard() {
    card newCard;
    newCard.shape = shapes[std::rand() % 4]; // Now using std::string
    newCard.num = std::rand() % 13 + 1;
    return newCard;
}

int main() {
    std::srand(static_cast<unsigned int>(std::time(nullptr))); // Initialize random seed

    Stack<card> cardStack;
    for (int i = 0; i < 15; i++) {
        card randomCard = generateRandomCard();
        std::cout << "Push Card: " << randomCard.shape << " " << randomCard.num << std::endl;
        cardStack.push(randomCard);
    }

    std::cout << "================= " << std::endl;

    while (!cardStack.isEmpty()) {
        std::cout << "Card Pop: " << cardStack.top().shape << " " << cardStack.top().num << std::endl;
        cardStack.pop();
    }

    return 0;
}