97 lines
2.3 KiB
C++
97 lines
2.3 KiB
C++
|
// 设计一个模板类 Queue，实现基本的队列功能，包括入队（enqueue）、出队（dequeue）、获取队首元素（front）和判断队列是否为空（isEmpty）等操作。
|
|||
|
|
// 【提示】Queue队列结构的特性是FIFO(先进先出)
|
|||
|
|
#include <iostream>
|
|||
|
|
|
|||
|
|
using namespace std;
|
|||
|
|
|
|||
|
|
template <typename T>
|
|||
|
|
class Queue
|
|||
|
|
{
|
|||
|
|
private:
|
|||
|
|
int capacity; // 容量
|
|||
|
|
int size; // 已存数量计数器
|
|||
|
|
T *arr; // 指向数组的指针
|
|||
|
|
|
|||
|
|
public:
|
|||
|
|
Queue(int capacity)
|
|||
|
|
{
|
|||
|
|
this->capacity = capacity;
|
|||
|
|
this->arr = new T[capacity];
|
|||
|
|
this->size = 0;
|
|||
|
|
}
|
|||
|
|
Queue(const Queue<T> &other)
|
|||
|
|
{
|
|||
|
|
this->capacity = other.capacity;
|
|||
|
|
this->size = other.size;
|
|||
|
|
this->arr = new T[capacity];
|
|||
|
|
for (int i = 0; i < size; i++)
|
|||
|
|
{
|
|||
|
|
this->arr[i] = other.arr[i];
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
~Queue()
|
|||
|
|
{
|
|||
|
|
delete[] arr;
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
public:
|
|||
|
|
Queue &enqueue(T val)
|
|||
|
|
{
|
|||
|
|
if (size == capacity)
|
|||
|
|
{
|
|||
|
|
cout << "队列已满!" << endl;
|
|||
|
|
return *this;
|
|||
|
|
}
|
|||
|
|
arr[size++] = val;
|
|||
|
|
return *this;
|
|||
|
|
}
|
|||
|
|
T dequeue() // 取出队首元素，并删除
|
|||
|
|
{
|
|||
|
|
if (size == 0)
|
|||
|
|
{
|
|||
|
|
cout << "队列已空!" << endl;
|
|||
|
|
return -1;
|
|||
|
|
}
|
|||
|
|
T val = arr[0]; // 取出队首元素
|
|||
|
|
for (int i = 0; i < size - 1; i++)
|
|||
|
|
{
|
|||
|
|
arr[i] = arr[i + 1]; // 元素前移
|
|||
|
|
}
|
|||
|
|
size--; // 计数器减一
|
|||
|
|
return val; // 返回队首元素
|
|||
|
|
}
|
|||
|
|
T front() // 只是返回队首元素，并不删除
|
|||
|
|
{
|
|||
|
|
if (size == 0)
|
|||
|
|
{
|
|||
|
|
cout << "队列已空!" << endl;
|
|||
|
|
return -1;
|
|||
|
|
}
|
|||
|
|
return arr[0];
|
|||
|
|
}
|
|||
|
|
string isEmpty()
|
|||
|
|
{
|
|||
|
|
return size == 0 ? "队列空" : "队列未空";
|
|||
|
|
}
|
|||
|
|
};
|
|||
|
|
|
|||
|
|
int main()
|
|||
|
|
{
|
|||
|
|
Queue<float> q(5);
|
|||
|
|
q.enqueue(1.1).enqueue(2.2).enqueue(3.3).enqueue(4.4).enqueue(5.5);
|
|||
|
|
cout << q.dequeue() << endl; // 1.1
|
|||
|
|
cout << q.front() << endl; // 2.2
|
|||
|
|
q.enqueue(6.6);
|
|||
|
|
q.enqueue(7.7); // 队列已满
|
|||
|
|
q.dequeue();
|
|||
|
|
q.dequeue();
|
|||
|
|
cout << q.dequeue() << endl; // 4.4
|
|||
|
|
cout << q.isEmpty() << endl; // 队列未空
|
|||
|
|
cout << q.dequeue() << endl; // 5.5
|
|||
|
|
cout << q.dequeue() << endl; // 6.6
|
|||
|
|
cout << q.isEmpty() << endl; // 队列空
|
|||
|
|
cout << q.dequeue() << endl; // 队列已空
|
|||
|
|
|
|||
|
|
return 0;
|
|||
|
|
}
|