已知Q是一个非空队列，S是一个空栈。仅用栈和队列的ADT函数和一个成员变量X编写一个算法，使得Q中的

Question

已知Q是一个非空队列，S是一个空栈。仅用栈和队列的ADT函数和一个成员变量X编写一个算法，使得Q中的元素倒置。(数据结构新手球球救命)

Answer 1

以下回答参考 皆我百晓生、券券喵儿 等免费微信小程序相关内容作答，并由本人整理回复。

#include <stack>
#include <queue>

class Queue {
public:
    int size;
    queue* next;
    queue* prev;

    queue(int x) : size(x), next(NULL), prev(NULL) {}
};

class Stack {
public:
    stack* top;
    stack* next;

    stack(int x) : top(new stack(x)), next(NULL) {}

    void push(int x) { top->push(x); }
    void pop() { top->pop(); }
    bool empty() const { return top == NULL; }

private:
    stack* top;
    stack* next;
};

void invertQueue(queue& Q, stack& S) {
    if (Q.empty()) return;

    while (!Q.empty()) {
        S.push(Q.front());
        Q.pop();
    }

    while (!S.empty()) {
        Q.push(S.top());
        S.pop();
    }
}