c++设计一个代main函数的算法,利用循环队列的基本运算,删除指定队列中的队尾元素,并且保持其他元素次序不变,并且计算循环队列元素个数。要求算法的空间复杂度为O(1)
时间: 2024-03-25 07:35:37 浏览: 54
以下是一个可以代替 `main` 函数的 C++ 算法,它利用循环队列的基本运算删除指定队列中的队尾元素,并保持其他元素次序不变,同时计算循环队列元素个数。该算法的空间复杂度为 O(1)。
```c++
#include <iostream>
using namespace std;
class CircularQueue {
public:
CircularQueue(int s) {
size = s + 1; // 为了区分队列为空和队列已满的情况,需要多分配一个空间
data = new int[size];
front = 0;
rear = 0;
count = 0;
}
~CircularQueue() {
delete[] data;
}
void push(int val) {
if (isFull()) {
cout << "Queue is full!" << endl;
return;
}
data[rear] = val;
rear = (rear + 1) % size;
count++;
}
int pop() {
if (isEmpty()) {
cout << "Queue is empty!" << endl;
return -1;
}
int val = data[front];
front = (front + 1) % size;
count--;
return val;
}
int getSize() {
return count;
}
bool isEmpty() {
return front == rear;
}
bool isFull() {
return (rear + 1) % size == front;
}
void deleteTail(int pos) {
if (isEmpty()) {
cout << "Queue is empty!" << endl;
return;
}
if (pos < 0 || pos >= count) {
cout << "Invalid position!" << endl;
return;
}
if (pos == count - 1) {
pop();
return;
}
int tail = (rear - 1 + size) % size;
int idx = (front + pos) % size;
swap(data[idx], data[tail]);
pop();
}
private:
int* data;
int front;
int rear;
int size;
int count;
};
int main() {
int n, m;
cin >> n >> m;
CircularQueue q(n);
for (int i = 0; i < n; i++) {
int val;
cin >> val;
q.push(val);
}
q.deleteTail(m);
cout << q.getSize() << endl;
return 0;
}
```
在上述代码中,我们定义了一个 `CircularQueue` 类,它包含了循环队列的基本运算,如 `push`、`pop`、`getSize` 等。我们还定义了一个 `deleteTail` 函数,用于删除指定位置的队尾元素。
在 `deleteTail` 函数中,我们首先判断队列是否为空,如果是,则直接输出错误信息并返回。然后,我们判断要删除的位置是否合法,如果不合法,则输出错误信息并返回。接下来,我们分三种情况讨论要删除的元素:
- 如果要删除的元素是队列中唯一的元素,则直接调用 `pop` 函数删除。
- 如果要删除的元素是队列中的最后一个元素,则直接调用 `pop` 函数删除。
- 如果要删除的元素是队列中的其他元素,则先将其与队尾元素交换,然后调用 `pop` 函数删除队尾元素。
最后,我们在 `main` 函数中读入循环队列的大小和要删除的元素位置,然后创建一个循环队列,读入队列元素,并调用 `deleteTail` 函数删除指定位置的队尾元素,并输出删除后的队列元素个数。
阅读全文