循环队列和优先队列的区别

2024 年 8 月 28 日 | 阅读 6 分钟

循环队列和优先队列都遵循队列机制，可以是线性队列或循环队列。循环队列具有先进先出的功能，而优先队列则根据优先级高低来处理元素。

循环队列	优先队列
元素可以在 O(1) 时间内插入。	执行删除、显示和插入操作。
它是一种循环方式，而不是线性类型的队列数据结构。	插入或删除基于分配的优先级。
所需的内存较少。	优先队列需要更多内存。

循环队列 C++ 代码

// Here we are writing down the simple C++ programming language code to
// demonstrate the concept of the Difference between Circular Queue and Priority 
// Queue with their relevant code supported by comments and their output
#include<bits/stdc++.h>
using namespace std;
// the below code snippet creates the class of Queue for us where we can 
// then perform operations such as insertion, deletion and display later.
class Queue
{

// the small code snippet helps us with initialising the front and the rear 
	int rear, front;

	// creating the circular queue from here onwards
	int size;
	int *arr;
public:
	Queue(int s)
	{
	front = rear = -1;
	size = s;
	arr = new int[s];
	}

// void, int functions to work with circular queue
	void enQueue(int value);
	int deQueue();
	void displayQueue();
};



// as we have created a class, it is time to write code to implement the queue
void Queue::enQueue(int value)
{
	if ((front == 0 && rear == size-1) ||
			(rear == (front-1)%(size-1)))
	{
		printf("\nHey! coder the circular queue is full!");
		return;
	}

	else if (front == -1) 
	// it helps us with implementing the first element in the queue for us
	{
		front = rear = 0;
		arr[rear] = value;
	}

	else if (rear == size-1 && front != 0)
	{
		rear = 0;
		arr[rear] = value;
	}

	else
	{
		rear++;
		arr[rear] = value;
	}
}

// Function to delete element from Circular Queue
int Queue::deQueue()
{
    // the below code snippet helps us with the deletion operation of the 
    // circular queue for us.
	if (front == -1)
	{
		printf("\nthe queue is empty coder");
		return INT_MIN;
	}

// writing down the edge cases to be handled
	int data = arr[front];
	arr[front] = -1;
	if (front == rear)
	{
		front = -1;
		rear = -1;
	}
	else if (front == size-1)
		front = 0;
	else
		front++;

	return data;
}


// the below code functionality helps us display the elements of the circular queue we created above.
void Queue::displayQueue()
{
	if (front == -1)
	{
		printf("\nthe queue is empty coder");
		return;
	}
	printf("\nthe elements in the circular queue created by us are: ");
	if (rear >= front)
	{
		for (int i = front; i <= rear; i++)
			printf("%d ",arr[i]);
	}
	else
	{
		for (int i = front; i < size; i++)
			printf("%d ", arr[i]);

		for (int i = 0; i <= rear; i++)
			printf("%d ", arr[i]);
	}
}

// this is the int main() driver codee functionality of our C++ program
int main()
{
	Queue q(5);

	// these are the small code snippet which helps us with pushing the
	// elements into our priority queues.
	q.enQueue(46);
	q.enQueue(3566);
	q.enQueue(68);
	q.enQueue(-990);


	// calling the function written above, which helps us with displaying!
	q.displayQueue();

// as we wrote a function body which helps us with deleting the elements
	// of the circular queue, it is the time to call them.
	printf("\nthe deleted value is = %d", q.deQueue());
	printf("\nthe deleted value is = %d", q.deQueue());

	q.displayQueue();

	q.enQueue(3566);
	q.enQueue(768);
	q.enQueue(-990);

	q.displayQueue();

	q.enQueue(46);
	return 0;
}

输出

/tmp/U6DBXIRSlF.o
the elements in the circular queue created by us are: 46 3566 68 -990 
the deleted value is = 46
the deleted value is = 3566
the elements in the circular queue created by us are: 68 -990 
the elements in the circular queue created by us are: 68 -990 3566 768 -990 
Hey! Coder, the circular queue is full!

现在，循环队列的时间复杂度部分，enQueue()、deQueue() 操作的时间复杂度几乎是 O(1)，因为任何操作中都没有循环或复杂函数。

优先队列 C++ 代码

// Here we are writing down the simple C++ programming language code to
// demonstrate the concept of the Difference between Circular Queue and 
//Priority 
// Queue with their relevant code supported by comments and their output
#include <bits/stdc++.h>
using namespace std;


// this below code snippet which we have created helps us with making the
// structure for the entities we will be adding to it.
struct item {
	int value;
	int priority;
};

// this below small code snippet helps us with storing up the elements 
// of the priority queue.
item pr[100000];

// this variable size created by us helps us with pointing to the end index
int size = -1;


// this is one of the most important functions which will help us with 
// pushing the elements into the queue priority
void enqueue(int value, int priority)
{
	//to increase the size of the priority variable,e we are
	// incrementing it.
	size++;

	// this below couple of code snippets will helps us with insertion
	pr[size].value = value;
	pr[size].priority = priority;
}

// this is another function named peek, which will help us with checking
// the topmost element in the queue priority
int peek()
{
	int highestPriority = INT_MIN;
	int ind = -1;

	// Check for the element with
	// highest priority using a for loop, which is looping till size 
	// variable
	for (int i = 0; i <= size; i++) {

		// If the priority is the same, choose
		// the element with the
		// highest value
		if (highestPriority == pr[i].priority && ind > -1
			&& pr[ind].value < pr[i].value) {
			highestPriority = pr[i].priority;
			ind = i;
		}
		else if (highestPriority < pr[i].priority) {
			highestPriority = pr[i].priority;
			ind = i;
		}
	}

	// Return position of the element
	return ind;
}

// Function to remove the element with
// the highest priority
void dequeue()
{
	// Find the position of the element
	// with the highest priority
	int ind = peek();


	// these are the for loop lines code helping us with shifting the 
	// element position from one index before the index of the element 
	// which has got the top priority of the queue where it is found
	for (int i = ind; i < size; i++) {
		pr[i] = pr[i + 1];
	}


	// the below small decrement operation helps us with decreasing the 
	// priority of the queue one by one using the(--) functionality
	size--;
}

// from the below lines of code, we will be dealing with the int main()
// driver code functionality
int main()
{
	
	// these are a few function calls that we have written to insert the 
	// elements as per the priority which we have set
	enqueue(10, 2);
	enqueue(14, 4);
	enqueue(16, 4);
	enqueue(12, 3);


	// the below variable is named and helps us with storing the topmost 
	// element temporarily in the next section of the code, we will be 
	// performing dequeue and insertion operations
	int ind = peek();

	cout << pr[ind].value << endl;

	// this below code function calling helps us with the dequeue operation
	dequeue();

	
    // calling the peek function to check for the element at the top 
	ind = peek();
	cout << pr[ind].value << endl;

	// this below code function calling helps us with the dequeue operation
	dequeue();

	// calling the peek function to check for the element at the top
	ind = peek();
	cout << pr[ind].value << endl;

	return 0;
}

Priority Queue (using LinkedList) C++ code
#include <bits/stdc++.h>
using namespace std;
typedef struct node {
	int data;
	int priority;

	struct node* next;

} Node;
Node* newNode(int d, int p)
{
	Node* temp = (Node*)malloc(sizeof(Node));
	temp->data = d;
	temp->priority = p;
	temp->next = NULL;

	return temp;
}
int peek(Node** head) { return (*head)->data; }
void pop(Node** head)
{
	Node* temp = *head;
	(*head) = (*head)->next;
	free(temp);
}
void push(Node** head, int d, int p)
{
	Node* start = (*head);
	Node* temp = newNode(d, p);
	if ((*head)->priority < p) {
		temp->next = *head;
		(*head) = temp;
	}
	else {
		while (start->next != NULL
			&& start->next->priority > p) {
			start = start->next;
		}
		temp->next = start->next;
		start->next = temp;
	}
}
int isEmpty(Node** head) { return (*head) == NULL; }
int main()
{
	Node* pq = newNode(4, 1);
	push(&pq, 5, 2);
	push(&pq, 6, 3);
	push(&pq, 7, 0);

	while (!isEmpty(&pq)) {
		cout << " " << peek(&pq);
		pop(&pq);
	}
	return 0;
}

输出

6 5 47

下一个主题C++ STL 中的 forward_list::cbefore_begin()

← 上一个下一个 →

循环队列和优先队列的区别

优先队列 C++ 代码

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

C++ 教程

C++ 控制语句

C++ 函数

C++ 数组

C++ 类和对象

C++ 构造函数

C++ 继承

C++ 多态

C++ 抽象

C++ 命名空间

C++ 模板

C++ 字符串

C++ 指针

信号处理

C++ 异常

C++ 文件与流

C++ STL 教程

面试题

选择题

C++ 程序

C++ STL Stack

C++ STL Bitset

C++ STL Deque

C++ STL List

C++ STL Map

C++ STL Math

C++ STL priority_queue

C++ STL Queue

C++ STL Multiset

C++ STL Multimap

C++ STL Set

C++ STD Strings

C++ STL Vector

C++ 操纵符

C++ STL Algorithms

C++ Algorithm

C++ Iterators

C++ 杂项

循环队列和优先队列的区别

优先队列 C++ 代码

相关帖子

C++ 跳转语句

C++ String_view

C++ STL 中的 multimap find()

C++ AVL 树

C++ Bellman-Ford 算法

为什么（非 const）全局变量在 C++ 中是邪恶的

C++ 程序实现 Park-Miller 随机数生成算法

C++ 变量遮蔽

C++ 树同构问题

C++ 汉诺塔算法

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器