xxyQwQ
0%

【题解】ACMOJ 14373 循环队列

发表于 更新于 分类于

题目描述

ACMOJ - 14373 - 循环队列

实现一个循环队列，支持如下操作：

  1. 将新的元素入队，并输出当前队尾的下标和元素个数
  2. 将队首元素出队，并输出当前队首的下标和元素个数

问题分析

按照题目要求实现即可，本题输出较为严格，请注意实现的规范性

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
#include <iostream>

template <typename ElementType>
class Queue
{
public:
    virtual ~Queue() {}
    virtual bool empty() const = 0;
    virtual void push(const ElementType &element) = 0;
    virtual ElementType pop() = 0;
    virtual ElementType front() const = 0;
    virtual void clear() = 0;
};

template <typename ElementType>
class SequentialQueue : public Queue<ElementType>
{
private:
    ElementType *elementData;
    int headPosition, tailPosition, totalCapacity;
    void expand();

public:
    SequentialQueue(int size = 10);
    ~SequentialQueue();
    bool empty() const;
    void push(const ElementType &element);
    ElementType pop();
    ElementType front() const;
    void clear();
    int get_head_position();
    int get_tail_position();
    int get_queue_length();
};

template <typename ElementType>
void SequentialQueue<ElementType>::expand()
{
    ElementType *temp = elementData;
    elementData = new ElementType[2 * totalCapacity];
    for (int i = 1; i < totalCapacity; i++)
        elementData[i] = temp[(headPosition + i) % totalCapacity];
    headPosition = 0;
    tailPosition = totalCapacity - 1;
    totalCapacity *= 2;
    delete[] temp;
}

template <typename ElementType>
SequentialQueue<ElementType>::SequentialQueue(int size)
{
    elementData = new ElementType[size];
    totalCapacity = size;
    headPosition = tailPosition = 0;
}

template <typename ElementType>
SequentialQueue<ElementType>::~SequentialQueue()
{
    delete[] elementData;
}

template <typename ElementType>
bool SequentialQueue<ElementType>::empty() const
{
    return headPosition == tailPosition;
}

template <typename ElementType>
void SequentialQueue<ElementType>::push(const ElementType &element)
{
    if ((tailPosition + 1) % totalCapacity == headPosition)
        expand();
    tailPosition = (tailPosition + 1) % totalCapacity;
    elementData[tailPosition] = element;
}

template <typename ElementType>
ElementType SequentialQueue<ElementType>::pop()
{
    if (headPosition == tailPosition)
        throw "Queue is already empty!";
    headPosition = (headPosition + 1) % totalCapacity;
    return elementData[headPosition];
}

template <typename ElementType>
ElementType SequentialQueue<ElementType>::front() const
{
    if (headPosition == tailPosition)
        throw "Queue is already empty!";
    return elementData[(headPosition + 1) % totalCapacity];
}

template <typename ElementType>
void SequentialQueue<ElementType>::clear()
{
    headPosition = tailPosition = 0;
}

template <typename ElementType>
int SequentialQueue<ElementType>::get_head_position()
{
    return headPosition;
}

template <typename ElementType>
int SequentialQueue<ElementType>::get_tail_position()
{
    return tailPosition;
}

template <typename ElementType>
int SequentialQueue<ElementType>::get_queue_length()
{
    return (tailPosition - headPosition + totalCapacity) % totalCapacity;
}

template <typename T>
void read(T &x)
{
    x = 0;
    char c = getchar();
    while (c < '0' || c > '9')
        c = getchar();
    while ('0' <= c && c <= '9')
    {
        x = x * 10 + c - '0';
        c = getchar();
    }
}

int main()
{
    int s, n, t, x;
    read(s), read(n);
    SequentialQueue<int> Q(s);
    while (n--)
    {
        read(t);
        if (t == 0)
        {
            read(x);
            Q.push(x);
            std::cout << Q.get_tail_position() << " " << Q.get_queue_length() << std::endl;
        }
        else if (t == 1)
        {
            if (!Q.empty())
                Q.pop();
            std::cout << Q.get_head_position() << " " << Q.get_queue_length() << std::endl;
        }
    }
    return 0;
}