۱۴۰۰/۰۲/۰۳

صف Queue(حلقوی) در ساختمان داده ها

صف Queue(حلقوی) ۱۳۹۸/۰۴/۲۶

صف Queue

صف حلقوی

یکی از مشکلات صف خطی یا صف سطری این است که در حالیکه بعضی از خانه های صف خالی است یا به عبارت دیگر صف پر است در هنگام استفاده از صف با آن مواجه میشویم

در واقع صف خطی یکبار مصرف است.واگر خانه ای را خالی کنیم دیگر نمی توانیم در آن خانه مقادیری را دخیره کنیم.برای رفع این مشکل از صف حلقوی استفاده میکنیم.

در صف حلقوی در هنگامیکه rear یا front به اندیس n-1برسد باید برگردد و مجددا  از اندیس صفر شروع کند

برای تعریف صف حلقوی آرایه را بصورت ۰ تا n-1 در نظر مگیریم و در این حالت وقتی rear=-1 شد عنصر بعدی در اندیس صفر قرار میگیرد.

نکته ها:

rear=اشاره گر به انتهای صف

front=اشاره گر به ابتدای صف

rear=front=-1مقدار اولیه 

rear=n-1صف پر است 

rear=front

نکته در مورد صف حلقوی:

در صف حلقوی نیز مانند صف خطی اگر rear=1 باشد یعنی صف خالی است

میتوان مقدار اولیه برای front و rear را صفر قرار داد.و شرط پر بودن صف حلقوی آن است که front=rear+1باشد

برای استفاده کردن از صف حلقوی هرگاه rear مثبت , n-1 شد.صفر میشود.

در غیر اینصورت rear یک واحد اضافه میشود.که میتوان آنرا از فرمول زیر بدست آورد:

rear=(rear+1)%n

برای حذف یا DEL کردن از صف هرگاه FRONT برابر n-1 شد صفر میشود.پس میتوان  FRONT را از این فرمول بدست بی اوریم.

یک مثال به زبان C

صف حلقوی در ساختمان داده

عملیات در صف حلقوی :

front: اشاره گر به ابتدای صف

Rear:اشاره گر به انتهای صف

 enQueue (value) این تابع برای وارد کردن یک عنصر در صف دایره ای استفاده شده است. در یک صفحه دایره ای ، عنصر جدید همیشه در موقعیت عقب قرار می گیرد.

مراحل:
 بررسی کنید که آیا صف کامل است -  ((rear == SIZE-1 && front == 0) || (rear == front-1)).
اگر پر باشد ، نمایش صف کامل است. اگر صف کامل نیست ، شرط (rear == SIZE – 1 && front != 0) را برسی میکند.اگر مقدار برگشتی true باشد مقدار rear را مساوی صفر قرار میدهد rear=0 و عنصر را وارد می کند.

()deQueue این تابع برای پاک کردن یک عنصر از صف دایره ای استفاده می شود. در یک صف دایره ای ، عنصر همیشه از موقعیت جلویی حذف می شود.

مراحل :

1-  بررسی میکند که آیا صف خالی است  (front==-1).

2-اگر خالی باشد ، صف نمایش خالی است. اگر صف خالی نیست به مرحله 3 را میرود.

3-بررسی میکند اگر (front==rear) مقدار true را برمیگرداند آنگاه  مقدار frontو rear برابر 1- میشود(front=rear= -1). وگرنه بررسی میکند , اگر (front==size-1) مقدار true باشد آنگاه  front=0  و عنصر را برمیگرداند.

// C or C++ program for insertion and
// deletion in Circular Queue
#include<bits/stdc++.h>
using namespace std;
 
struct Queue
{
    // Initialize front and rear
    int rear, front;
 
    // Circular Queue
    int size;
    int *arr;
 
    Queue(int s)
    {
       front = rear = -1;
       size = s;
       arr = new int[s];
    }
 
    void enQueue(int value);
    int deQueue();
    void displayQueue();
};

 

/* Function to create Circular queue */
void Queue::enQueue(int value)
{
    if ((front == 0 && rear == size-1) ||
            (rear == (front-1)%(size-1)))
    {
        printf("\nQueue is Full");
        return;
    }
 
    else if (front == -1) /* Insert First Element */
    {
        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()
{
    if (front == -1)
    {
        printf("\nQueue is Empty");
        return INT_MIN;
    }
 
    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;
}
 
// Function displaying the elements
// of Circular Queue
void Queue::displayQueue()
{
    if (front == -1)
    {
        printf("\nQueue is Empty");
        return;
    }
    printf("\nElements in Circular Queue 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]);
    }
}
 
/* Driver of the program */
int main()
{
    Queue q(5);
 
    // Inserting elements in Circular Queue
    q.enQueue(14);
    q.enQueue(22);
    q.enQueue(13);
    q.enQueue(-6);
 
    // Display elements present in Circular Queue
    q.displayQueue();
 
    // Deleting elements from Circular Queue
    printf("\nDeleted value = %d", q.deQueue());
    printf("\nDeleted value = %d", q.deQueue());
 
    q.displayQueue();
 
    q.enQueue(9);
    q.enQueue(20);
    q.enQueue(5);
 
    q.displayQueue();
 
    q.enQueue(20);
    return 0;
}

 

Output:

Elements in Circular Queue are: 14 22 13 -6
Deleted value = 14
Deleted value = 22
Elements in Circular Queue are: 13 -6
Elements in Circular Queue are: 13 -6 9 20 5
Queue is Full

 

 


رای :

صف

Queue

حلقوی

صف حلقوی

توضیح کامل نبوداصلا rear و front رو توضیح ندادین چی هست تو شکل هم اصلا rear نیست؟
حامد شعبانی : توضیحات تکمیلی اضافه شد

ارسال نظر
Copyright © All right reserved.