Stack and Queue Fundamentals

A stack follows Last-In-First-Out (LIFO), whereas a queue operates on First-In-First-Out (FIFO).

In C++, both structures exist within the Standard Template Library (STL), though implementations may vary across different versions:

1. HP STL: The foundational implementation that influenced many others, including being open-source.
2. P.J.Plauger STL: Used by Microsoft's Visual C++ compiler, this version is proprietary.
3. SGI STL: Adopted by GCC compilers on Linux systems, known for its readable source code.

Both stacks and queues in SGI STL act as adapters over underlying containers:

Stack Implementation

A stack exposes push and pop operations and enforces LIFO behavior, thus not supporting traversal or iterators. Internally it uses an adaptable container, commnoly deque. To specify vector as the underlying container:

std::stack<int, std::vector<int>> custom_stack;

Queue Implementation

Similarly, queues default to using deque but can also utilize list:

std::queue<int, std::list<int>> custom_queue;

Queue Simulation Using Two Stacks

To simulate FIFO behavior with two LIFO structures:

class QueueSimulator {
private:
    std::stack<int> input_stack;
    std::stack<int> output_stack;
    
    void move_elements() {
        if (output_stack.empty()) {
            while (!input_stack.empty()) {
                output_stack.push(input_stack.top());
                input_stack.pop();
            }
        }
    }
    
public:
    void enqueue(int value) {
        input_stack.push(value);
    }
    
    int dequeue() {
        move_elements();
        int result = output_stack.top();
        output_stack.pop();
        return result;
    }
    
    int front_element() {
        move_elements();
        return output_stack.top();
    }
    
    bool is_empty() {
        move_elements();
        return output_stack.empty();
    }
};

Stack Construction with Queues

Using dual queues to build a LIFO structure:

class StackBuilder {
private:
    std::queue<int> primary;
    std::queue<int> auxiliary;
    
public:
    void push_value(int val) {
        primary.push(val);
    }
    
    int pop_value() {
        while (primary.size() > 1) {
            auxiliary.push(primary.front());
            primary.pop();
        }
        int result = primary.front();
        primary.pop();
        
        primary.swap(auxiliary);
        return result;
    }
    
    int top_value() {
        while (primary.size() > 1) {
            auxiliary.push(primary.front());
            primary.pop();
        }
        int result = primary.front();
        auxiliary.push(result);
        primary.pop();
        
        primary.swap(auxiliary);
        return result;
    }
    
    bool check_empty() {
        return primary.empty();
    }
};

Optimized single-queue approach:

class OptimizedStack {
private:
    std::queue<int> data_queue;
    
public:
    void add_element(int element) {
        data_queue.push(element);
    }
    
    int remove_element() {
        int iterations = data_queue.size() - 1;
        while (iterations--) {
            data_queue.push(data_queue.front());
            data_queue.pop();
        }
        int result = data_queue.front();
        data_queue.pop();
        return result;
    }
    
    int get_top() {
        int iterations = data_queue.size();
        int result;
        while (iterations--) {
            result = data_queue.front();
            data_queue.push(result);
            data_queue.pop();
        }
        return result;
    }
    
    bool is_stack_empty() {
        return data_queue.empty();
    }
};

Validating Bracket Sequences

Bracket validation requires ensuring proper nesting and matching:

class BracketValidator {
public:
    bool validate(const std::string& sequence) {
        std::unordered_map<char, char> pairs = {{')', '('}, {']', '['}, {'}', '{'}};
        std::stack<char> validator;
        
        for (char ch : sequence) {
            if (pairs.count(ch)) {
                if (validator.empty() || validator.top() != pairs[ch]) {
                    return false;
                }
                validator.pop();
            } else {
                validator.push(ch);
            }
        }
        
        return validator.empty();
    }
};

Eliminating Adjacent Duplicates

Removing adjacent duplicate characters efficiently:

class DuplicateRemover {
public:
    std::string process_string(const std::string& input) {
        std::string result;
        
        for (char current : input) {
            if (!result.empty() && result.back() == current) {
                result.pop_back();
            } else {
                result.push_back(current);
            }
        }
        
        return result;
    }
};