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

循环队列和优先队列都遵循队列的机制，可以是线性或循环队列形式。循环队列具有先入先出的功能，而优先队列则按照优先级最高的元素先被服务。

圆形队列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
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 
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 
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