C++第二十六弹---stack和queue的基本操作详解与模拟实现

#include <iostream>
#include <vector>
 
// 模拟stack的类定义
template<typename T>
class Stack {
private:
    std::vector<T> elements;
 
public:
    // 构造函数
    Stack() {}
 
    // 入栈操作
    void push(const T& value) {
        elements.push_back(value);
    }
 
    // 出栈操作
    void pop() {
        if (!elements.empty()) {
            elements.pop_back();
        }
    }
 
    // 获取栈顶元素
    T top() const {
        if (!elements.empty()) {
            return elements.back();
        }
        throw "empty stack";
    }
 
    // 检查栈是否为空
    bool empty() const {
        return elements.empty();
    }
};
 
// 模拟queue的类定义
template<typename T>
class Queue {
private:
    Stack<T> stack1;
    Stack<T> stack2;
 
public:
    // 构造函数
    Queue() {}
 
    // 入队操作
    void enqueue(const T& value) {
        stack1.push(value);
    }
 
    // 出队操作
    void dequeue() {
        if (stack2.empty()) {
            while (!stack1.empty()) {
                stack2.push(stack1.top());
                stack1.pop();
            }
        }
        if (!stack2.empty()) {
            stack2.pop();
        }
    }
 
    // 获取队首元素
    T front() const {
        if (stack2.empty()) {
            while (!stack1.empty()) {
                stack2.push(stack1.top());
                stack1.pop();
            }
        }
        if (!stack2.empty()) {
            return stack2.top();
        }
        throw "empty queue";
    }
 
    // 检查队列是否为空
    bool empty() const {
        return stack1.empty() && stack2.empty();
    }
};
 
int main() {
    Queue<int> q;
    q.enqueue(1);
    q.enqueue(2);
    q.enqueue(3);
    std::cout << "Front: " << q.front() << std::endl;
    q.dequeue();
    if (!q.empty()) {
        std::cout << "Front: " << q.front() << std::endl;
    }
    q.dequeue();
    if (!q.empty()) {
        std::cout << "Front: " << q.front() << std::endl;
    }
    return 0;
}

这段代码首先定义了模拟Stack和Queue的类，然后在main函数中演示了如何使用它们。这里使用了两个Stack实例来模拟Queue，其中一个用于入队操作，另一个用于出队操作时暂时存储元素。这是一个简化的模拟实现，仅用于教学目的。