用两个队列实现栈.md

通过两个队列实现栈

问题描述

通过两个队列实现栈，包括push, pop, empty, size, top等函数

解决方案

算法代码如下：

class QueueStack {
private:
    queue<int> q1, q2;
public:
    void push(int data) {
        if (q1.empty()) {
            q2.push(data);
        } else {
            q1.push(data);
        }
    }

    void pop() {
        if (q2.empty() && !q1.empty()) {
            while (q1.size() > 1) {
                q2.push(q1.front());
                q1.pop();
            }
            q1.pop();
        } else if (q1.empty() && !q2.empty()) {
            while (q2.size() > 1) {
                q1.push(q2.front());
                q2.pop();
            }
            q2.pop();
        }
    }

    bool empty() const {
        return (q2.empty() && q1.empty());
    }

    int size() const {
        return (q1.size() + q2.size());
    }

    int& top() {
        if (q2.empty() && !q1.empty()) {
            while (q1.size() > 1) {
                q2.push(q1.front());
                q1.pop();
            }
            int &data = q1.front();
            q2.push(data);
            q1.pop();
            return data;
        } else if (q1.empty() && !q2.empty()) {
            while (q2.size() > 1) {
                q1.push(q2.front());
                q2.pop();
            }
            int &data = q2.front();
            q1.push(data);
            q2.pop();
            return data;
        } else {
            throw "No data";
        }
    }
};

测试用例如下：

TEST(StackFifo, Class_Stack) {
    QueueStack s;
    s.push(1);
    s.push(2);
    s.push(3);
    s.push(4);
    EXPECT_EQ(4, s.top());
    EXPECT_EQ(4, s.size());
    EXPECT_FALSE(s.empty());

    s.pop();
    EXPECT_EQ(3, s.top());
    EXPECT_EQ(3, s.size());
    EXPECT_FALSE(s.empty());
    s.pop();
    s.pop();
    s.pop();
    s.pop();
    EXPECT_TRUE(s.empty());
    EXPECT_EQ(0, s.size());
    ASSERT_ANY_THROW(s.top());

    s.push(1);
    s.push(2);
    EXPECT_EQ(2, s.top());
    EXPECT_EQ(2, s.size());
    EXPECT_FALSE(s.empty());
}