第一题

题目简述

实现一个循环队列，能充分利用空间内的元素。

代码

#include <iostream>
#include <algorithm>
#include <ctime>
using namespace std;
#define MAXSIZE 10
typedef int Elemtype;
class Queue{
private:
    Elemtype data[MAXSIZE];
    int tag[2];
public:
    // 0域表示front、1域表示back
    Queue(){
     tag[0] = 0, tag[1] = 0; }
    void push(Elemtype e);
    int pop();
    bool isEmpty(){
     return tag[0] == tag[1]; };
};
void Queue::push(Elemtype e){
    if ((tag[1] + 1) % MAXSIZE == tag[0]){
        cerr << "队列满!" << endl;
        return;
    }
    data[tag[1]] = e;
    tag[1] = (tag[1] + 1) % MAXSIZE;
    return;
}
int Queue::pop(){
    if (tag[0] == tag[1]) {
        cerr << "队列空!" << endl;
        return -1;
    }
    int x = data[tag[0]];
    tag[0] = (tag[0] + 1) % MAXSIZE;
    return x;
}
int main()
{
    Queue que;
    srand(time(0));
    for (int i = 0; i < 12; i++){
        int x = rand() % 10;
        que.push(x);
        cout << x << " ";
    }
    cout << endl;
    while (!que.isEmpty()){
        cout << que.pop() << " ";
    }
    cout << endl;
    return 0;
}

第二题

题目简述

Q是一个队列，S是一个空栈，利用S实现将Q中的元素逆置。

代码

#include <iostream>
#include <queue>
#include <stack>
using namespace std;
void reverseQueue(queue<int> &que)
{
    stack<int> stk;
    while (que.size()) {
        stk.push(que.front());
        que.pop();
    }
    while (stk.size()){
        que.push(stk.top());
        stk.pop();
    }
}
int main()
{
    queue<int> que;
    que.push(1);
    que.push(2);
    que.push(3);
    que.push(5);
    que.push(4);
    reverseQueue(que);
    while (que.size())
    {
        cout << que.front() << " ";
        que.pop();
    }
    cout << endl;
    return 0;
}

第三题

题目简述

利用两个栈，实现一个队列。

代码

#include <iostream>
#include <stack>
using namespace std;
typedef int Elemtype;
class Queue
{
private:
    stack<Elemtype> stk1, stk2;
public:
    void EnQueue(Elemtype x);
    Elemtype Dequeue();
    bool QueueEmpty(){
     return stk1.empty() && stk2.empty(); };
};
void Queue::EnQueue(Elemtype e){
    // TODO 这个位置应该有判满操作，因为使用的是stl中的nb栈，所以跳过
    stk1.push(e);
}
Elemtype Queue::Dequeue(){
    if (stk1.empty() && stk2.empty()){
        cerr << "队列为空" << endl;
        return -1;
    }
    Elemtype res;
    if (!stk2.empty()){
        res = stk2.top();
        stk2.pop();
    }
    else{
        while (!stk1.empty()){
            stk2.push(stk1.top());
            stk1.pop();
        }
        res = stk2.top();
        stk2.pop();
    }
    return res;
}
int main()
{
    Queue que;
    for (int type, x;;){
        cin >> type;
        if (type){
            cin >> x;
            que.EnQueue(x);
        }
        else{
            cout << que.Dequeue() << endl;
        }
    }
    return 0;
}