欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

队列——数组实现(循环队列)

程序员文章站 2024-03-18 11:18:16
...
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <ctime> 

using namespace std;

using ElemType = int;
const int MAXSIZE = 20;

// 队列结构
class Queue {
public:
	ElemType data[MAXSIZE];
	int front;		// 队首 
	int rear;		// 队尾 
};

// 初始化队列 
void initQueue(Queue &queue)
{
	queue.front = 0;
	queue.rear = 0;
}

// 判空:front == rear 
bool isEmpty(const Queue &queue)
{
	if (queue.front == queue.rear)
		return true;
	return false;
}

// 判满:(rear+1) % MAXSIZE == front 
bool isFull(const Queue &queue)
{
	if (queue.front == (queue.rear+1) % MAXSIZE)
		return true;
	return false;
}

// 进队列 
void addElem(Queue &queue, ElemType val)
{
	if (isFull(queue)) {
		cout << "queue is full...\n";
		return;
	}
	queue.data[queue.rear] = val;
	queue.rear = (queue.rear + 1) % MAXSIZE;
}

// 出队列 
void delElem(Queue &queue)
{
	if (isEmpty(queue)) {
		cout << "queue is empty...\n";
		return;
	}
	cout << "队首元素为" << queue.data[queue.front] << endl;
	queue.front = (queue.front + 1) % MAXSIZE;
}

// 获取队列长度:(rear - front) % MAXSIZE 
int getLen(const Queue &queue)
{
	return (queue.rear - queue.front) % MAXSIZE;
}

int main()
{
	Queue queue;
	int queLen = 0;
	initQueue(queue);
	queLen = getLen(queue);
	cout << "当前队列的长度为:" << queLen << endl;
	addElem(queue, 1);
	addElem(queue, 2);
	addElem(queue, 3);
	addElem(queue, 4);
	queLen = getLen(queue);
	cout << "当前队列的长度为:" << queLen << endl;
	delElem(queue);
	delElem(queue); 
	queLen = getLen(queue);
	cout << "当前队列的长度为:" << queLen << endl;
}

【补充】

循环队列队首和队尾的一些关系(假设队首下标为front,队尾下标为rear,数组长度为MAXSIZE):

  • 队列为空:rear == front
  • 队列为满:(rear + 1) % MAXSIZE == front          //(基于给队列留一个空闲位置而实现,不然和队列为空时条件重合)
  • 队列长度:(rear - front) % MAXSIZE