#include <iostream>
#include <stack>
#include <vector>
#include <list>
#include <string>

// General print function: accepts any stack type by value (does not modify original stack)
template<typename StackType>
void printStack(StackType stk) {   // note: pass by value, uses a copy
    std::cout << "[Top -> Bottom]: ";
    while (!stk.empty()) {
        std::cout << stk.top() << " ";
        stk.pop();
    }
    std::cout << std::endl;
}

// General status function: prints stack size and emptiness, accepts any stack type
template<typename StackType>
void status(const StackType& stk, const std::string& name) {
    std::cout << name << " -> size: " << stk.size()
              << ", empty: " << (stk.empty() ? "true" : "false") << std::endl;
}

int main() {
    // ==================== 1. Construct stacks ====================
    std::stack<int> s1;                     // default underlying deque
    std::stack<int, std::vector<int>> s2;   // underlying vector
    std::stack<int, std::list<int>> s3;     // underlying list

    std::vector<int> vec = {1, 2, 3, 4, 5};
    std::stack<int, std::vector<int>> s4(vec); // copy-constructed from vector

    std::stack<int> s5(s1);                 // copy construct

    std::cout << "=== Initial state ===" << std::endl;
    status(s1, "s1");
    status(s2, "s2");
    status(s3, "s3");
    status(s4, "s4");
    std::cout << std::endl;

    // ==================== 2. Basic operations ====================
    std::cout << "=== Push 10, 20, 30 into s1 ===" << std::endl;
    s1.push(10);
    s1.push(20);
    s1.push(30);
    status(s1, "s1");
    std::cout << "Top element: " << s1.top() << std::endl;
    s1.pop();
    std::cout << "Top after one pop: " << s1.top() << std::endl;
    status(s1, "s1");
    std::cout << std::endl;

    // ==================== 3. emplace (C++11) ====================
    std::stack<std::string> strStack;
    strStack.emplace("Hello");
    strStack.emplace("World");
    std::cout << "=== emplace example ===" << std::endl;
    std::cout << "Top string: " << strStack.top() << std::endl;
    std::cout << std::endl;

    // ==================== 4. Traverse and clear ====================
    std::cout << "=== Traverse and clear s1 ===" << std::endl;
    while (!s1.empty()) {
        std::cout << s1.top() << " ";
        s1.pop();
    }
    std::cout << std::endl;
    status(s1, "s1 (after clearing)");
    std::cout << std::endl;

    // ==================== 5. Non-destructive traversal ====================
    for (int i = 1; i <= 5; ++i) s1.push(i * 10);   // 10,20,30,40,50
    std::cout << "=== Refill s1: 10 20 30 40 50 ===" << std::endl;
    std::cout << "Contents of s1: ";
    printStack(s1);      // uses a copy, original stack remains unchanged
    status(s1, "s1 (unchanged after traversal)");
    std::cout << std::endl;

    // ==================== 6. swap ====================
    std::stack<int> s6;
    for (int i = 1; i <= 3; ++i) s6.push(i * 100);
    std::cout << "=== Before swap ===" << std::endl;
    status(s1, "s1");
    status(s6, "s6");

    s1.swap(s6);
    std::cout << "=== After swap ===" << std::endl;
    status(s1, "s1");
    status(s6, "s6");
    std::cout << "s1 contents: ";
    printStack(s1);
    std::cout << "s6 contents: ";
    printStack(s6);
    std::cout << std::endl;

    // Use non-member swap
    std::swap(s1, s6);
    std::cout << "=== Swap back ===" << std::endl;
    status(s1, "s1");
    status(s6, "s6");
    std::cout << std::endl;

    // ==================== 7. Assignment operations ====================
    std::stack<int> s7;
    s7 = s1;
    std::cout << "=== Copy assignment s7 = s1 ===" << std::endl;
    status(s7, "s7");
    std::cout << "s7 contents: ";
    printStack(s7);
    std::cout << std::endl;

    // ==================== 8. Comparison operations ====================
    std::stack<int> a, b;
    a.push(1); a.push(2); a.push(3);
    b.push(1); b.push(2); b.push(3);
    std::cout << "=== Comparison operations ===" << std::endl;
    std::cout << "a == b ? " << (a == b ? "true" : "false") << std::endl;
    b.push(4);
    std::cout << "a != b ? " << (a != b ? "true" : "false") << std::endl;
    std::cout << "a < b ? " << (a < b ? "true" : "false") << std::endl;
    std::cout << std::endl;

    // ==================== 9. Stacks with different underlying containers ===
    s2.push(100);
    s2.push(200);
    std::cout << "=== s2 backed by vector ===" << std::endl;
    std::cout << "s2 top: " << s2.top() << std::endl;
    s2.pop();
    std::cout << "Top after pop: " << s2.top() << std::endl;
    status(s2, "s2");   // now works normally
    std::cout << "s2 contents: ";
    printStack(s2);

    s3.push(999);
    std::cout << "\n=== s3 backed by list ===" << std::endl;
    std::cout << "s3 top: " << s3.top() << std::endl;
    status(s3, "s3");

    return 0;
}