Understanding Queue End Determination ~ Ring Buffer ~ Algorithms and Data Structures

Asked 2 years ago, Updated 2 years ago, 47 views

Currently, I am reading the here article and do not know the criteria for determining the end of the ring buffer.

#include<iostream>
# include <vector>
using namespace std;
constint MAX=100000; // Maximum size of queue array

intqu [MAX]; // Array representing queues
intail = 0, head = 0; // Variable that represents the elemental interval of the queue

// initialize a queue
void init() {
    head = tail = 0;
}

// determine if the queue is empty
bool isEmpty(){
    return(head==tail);
}

// determine if the stack is full
bool isFull() {
    return(head==(tail+1)%MAX);
}

// enqueue (increment with elements in tail)
void enqueue(intv){
    if(isFull()){
        cout<<"error:queue is full."<<endl;
        return;
    }
    qu [tail++] = v;
    if(tail==MAX)tail=0;// 0 when the ring buffer is terminated
}

// dequeue (return element in head and increment head)
int queue() {
    if(isEmpty()){
        cout<<"error:stack is empty."<<endl;
        return-1;
    }
    intres=qu [head];
    ++head;
    if(head==MAX)head=0;
    return res;
}

int main() {
    init(); // Initialize queue

    enqueue(3); // Load queue 3 {}->{3}
    enqueue(5);// Load queue 5 {3}->{3,5}
    enqueue(7); // Load queue 7 {3,5}-> {3,5,7}

    Output 3 on cout<<dequeue()<endl;//{3,5,7}->{5,7}
    Output 5 on cout<<dequeue()<endl;//{5,7}->{7}

    enqueue(9); // Load new 9 {7}-> {7,9}
    enqueue(11); // {7,9}-> {7,9,11}

    queue(); // {7,9,11}-> {9,11}
    queue();//{9,11}->{11}
    queue();//{11}->{}

    // Check if it is empty:empty output
    cout<<(isEmpty()? "empty": "not empty")<<endl;
}

When the stack is full

// Determine if the stack is full
bool isFull() {
    return(head==(tail+1)%MAX);
}

This function is written, but why do you do (tail+1)%MAX?
In my opinion, head==(tail+1) alone will tell you that the values at the beginning and at the end match.
Why is it necessary to divide by the number of arrays?
I look forward to your kind cooperation.

c algorithm

2022-09-30 17:32

1 Answers

In my opinion, head==(tail+1) alone will show that the values at the beginning and at the end match.

Think about what happens when the tail goes to MAX-1
If head==(tail+1), the head will be MAX.
If I enqueue at this time, what do you think the tail should be?


2022-09-30 17:32

If you have any answers or tips


© 2024 OneMinuteCode. All rights reserved.