پیاده سازی صف با لیست پیوندی+ جستجو در لیست پیوندی

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

چرا به پیاده‌سازی صف با استفاده از لیست پیوندی نیاز داریم؟

پیاده‌سازی صف با استفاده از ساختار داده‌ای ایستا (آرایه‌ی یک‌بعدی) با محدودیت‌های عجیبی از نظر هدررفت حافظه مواجه می‌شود. در طراحی راه‌حل‌ها یا الگوریتم‌ها، باید همواره به حفاظت از این منابع حیاتی با تحلیل همه جنبه‌های توسعه توجه داشته باشیم. تکنیک پیاده‌سازی صف با استفاده از آرایه با مشکلات زیر همراه است که نیاز به یک روش پیاده‌سازی دیگر را ایجاد می‌کند:

مشکل اندازه ثابت: آرایه یک ساختار داده‌ای ایستا است. این بدان معناست که باید اندازه آرایه را قبل از اجرای برنامه تعیین کنیم. علاوه بر این، این اندازه در زمان اجرا قابل تغییر نیست. این واقعیت درباره آرایه‌ها، با ویژگی اصلی صف که باید بتواند در زمان اجرا گسترش یابد، در تضاد است.

هدررفت حافظه در هنگام حل مشکل اندازه ثابت: وقتی آرایه به اتمام می‌رسد، نمی‌توان اندازه آن را در زمان اجرا تغییر داد. این سناریو ما را تنها با یک گزینه روبرو می‌کند: ایجاد یک آرایه بزرگ‌تر جدید و کپی کردن محتویات آرایه قبلی در آن. اما این روش نیز معایب بیشتری به همراه دارد:

• عملیات کپی به اندازه O(N) هزینه دارد.
• از دست دادن حافظه بیشتر به دلیل ایجاد آرایه بزرگ‌تر.

برای مثال، به سناریوی نشان داده شده در شکل زیر توجه کنید. آرایه اول در شکل یک آرایه کاملاً استفاده شده با اندازه ۴ است. و دیگری یک آرایه جدید و بزرگ‌تر با اندازه ۱۰ است. وقتی محتویات آرایه استفاده‌شده در آرایه جدید و بزرگ‌تر ذخیره می‌شود، فضای زیادی از آرایه جدید خالی می‌ماند.

هدررفت حافظه به دلیل حذف عناصر داده‌ای: پس از انجام عملیات ()Dequeue، ممکن است در صف فضاهای خالی باقی بمانند. و اگر مقدار اشاره‌گر انتهایی (rear) بسیار بالا باشد، این فضاهای خالی دیگر قابل استفاده مجدد نخواهند بود.

 نمایش صف با استفاده از لیست پیوندی

در یک صف پیوندی، هر گره از صف شامل دو بخش است: یک بخش داده و یک بخش ارجاع (اشاره‌گر). هر موجودیت در صف پیوندی به موجودیت بعدی خود در حافظه اشاره می‌کند. علاوه بر این، برای ردیابی گره‌های جلویی (front) و انتهایی (rear)، دو اشاره‌گر در حافظه نگهداری می‌شوند. اولین اشاره‌گر مکان شروع صف را ذخیره می‌کند و اشاره‌گر دوم آخرین عنصر داده‌ای صف را ردیابی می‌کند.

برنامه نویسی چیست؟ انواع آن و نکات کاربردی

در دیاگرام بالا، یک نمایش از صف پیوندی نشان داده شده است که شامل ۳ فیلد داده‌ای و آدرس‌های موجودی های بعدی در صف است.

در صف پیوندی، عملیات درج (Enqueue) در انتهای صف انجام می‌شود. این کار با به‌روزرسانی مقدار آدرس گره قبلی که اشاره‌گر انتهایی به آن اشاره می‌کند، صورت می‌گیرد. به‌عنوان مثال، صف پیوندی با اندازه ۳ را در نظر بگیرید. ما نیاز داریم که یک گره جدید با آدرس ۳۵۰ و مقدار ۷ در فیلد داده‌اش اضافه کنیم. برای انجام این کار، فقط مقدار اشاره‌گر انتهایی و فیلد آدرس گره قبلی را به‌روزرسانی می‌کنیم.

مقدار اشاره‌گر انتهایی اکنون به ۳۵۰ تغییر می‌کند، در حالی که اشاره‌گر جلویی بدون تغییر باقی می‌ماند. پس از حذف یک عنصر از صف پیوندی، مقدار اشاره‌گر جلویی از ۱۰۰ به ۲۰۰ تغییر خواهد کرد. صف پیوندی پس از انجام این عملیات به‌صورت زیر خواهد بود:

اکنون که فهمیدید چگونه می‌توان یک صف را با استفاده از لیست پیوندی نمایش داد، بیایید عملیات اصلی صف را پیاده‌سازی کنیم.

 پیاده‌سازی عملیات صف

عملیات ()Enqueue و ()Dequeue عملیات‌های اصلی صف هستند که به ما اجازه می‌دهند جریان داده را مدیریت کنیم. این توابع به تعداد عناصر داخل صف یا اندازه آن وابسته نیستند؛ به همین دلیل، این عملیات‌ها زمان اجرای ثابت i.e., O(1) [time-complexity] دارند. در اینجا، این عملیات‌های اصلی را پیاده‌سازی خواهیم کرد:

1. عملیات()Enqueue

فرآیند اضافه کردن عناصر به صف به‌عنوان عملیات Enqueue شناخته می‌شود. این عملیات در گره انتهایی صف انجام می‌شود. در این تابع، ابتدا حافظه برای گره جدید با استفاده از دستور زیر تخصیص می‌یابد:

struct Node temp = (struct Node)malloc(sizeof(struct Node));

پس از ایجاد گره جدید، مقادیر را به فیلدهای داده و ارجاع وارد می‌کنیم. مقدار داده توسط کاربر وارد می‌شود و فیلد ارجاع ابتدا به null تنظیم می‌شود:

temp->data = x;

temp->next = NULL;

دو حالت ممکن است برای درج گره جدید در صف پیوندی وجود داشته باشد.

حالت اول: اگر صف خالی باشد. در این حالت، هر دو اشاره‌گر جلویی و انتهایی باید Null باشند. این وضعیت را با شرط `front == NULL` بررسی می‌کنیم. اگر درست باشد، عنصر جدید به‌عنوان اولین عنصر صف اضافه می‌شود و هر دو اشاره‌گر جلویی و انتهایی به این گره جدید اشاره خواهند کرد:

if(front == NULL && rear == NULL){

    front = rear = temp;

    return;

}

آموزش صفر تا صد اصول و مبانی برنامه ‌نویسی (8 درس و 6 اصل)

حالت دوم: اگر صف شامل بیش از یک عنصر داده‌ای باشد. در این حالت، شرط `front == NULL` نادرست خواهد بود. در این وضعیت، فقط اشاره‌گر انتهایی را به گره جدید اشاره خواهیم داد و همچنین فیلد آدرس گره قبلی را برای ایجاد پیوند جدید به‌روزرسانی می‌کنیم:

rear->next = temp;

rear = temp;

کدc  برای این عملیات:

struct Node {

    int data;

    struct Node next;

};

struct Node front = NULL;

struct Node rear = NULL;

void Enqueue(int x) {

    struct Node temp = (struct Node)malloc(sizeof(struct Node));

    temp->data = x;

    temp->next = NULL;

    if (front == NULL && rear == NULL) {

        front = rear = temp;

        return;

    }

    rear->next = temp;

    rear = temp;

}

بسیار کاربردی: بهترین زبان برنامه نویسی برای هک و هکر شدن

2. عملیات ()Dequeue

عملیات Dequeue فرآیندی است که در آن عناصر از صف حذف می‌شوند. عنصری فقط در صورتی می‌تواند حذف شود که حداقل یک عنصر برای حذف وجود داشته باشد، یعنی Rear > 0 (صف نباید خالی باشد). اگر صف خالی باشد، با چاپ یک پیام خطای "Underflow" (سرریز معکوس) از تابع خارج می‌شویم.

if (front == NULL) {

    printf("Queue is Empty\n");

    return;

}

اگر تنها یک عنصر در صف وجود داشته باشد، اشاره‌گرهای front و rear را به NULL تنظیم می‌کنیم:

if (front == rear) {

    front = rear = NULL;

}

در غیر این صورت، مقدار اشاره‌گر front را به گره بعدی به‌روزرسانی می‌کنیم و همچنین حافظه گره حذف‌شده را با استفاده از تابع `()free` در C آزاد می‌کنیم:

else {

    front = front->next;

}

free(temp);

حتما در کنار این مطلب بخوانید: نحوه یادگیری یک زبان برنامه نویسی و روش ورود به این رشته

کد تابع Dequeue در C :

void Dequeue() {

    struct Node* temp = front;

    if (front == NULL) {

        printf("Queue is Empty\n");

        return;

    }

    if (front == rear) {

        front = rear = NULL;

    } else {

        front = front->next;

    }

    free(temp);

}

3. عملیات ()Peek

تابع Peek به ما کمک می‌کند تا عنصر داده‌ای که اشاره‌گر front به آن اشاره می‌کند را بدون حذف آن از صف استخراج کنیم. ابتدا بررسی می‌کنیم که آیا front برابر NULL است یا نه. اگر برابر NULL باشد، پیام "Queue is Empty" را به کنسول بازمی‌گردانیم:

if (front == NULL) {

    printf("Queue is empty\n");

    return;

}

در غیر این صورت، عنصر داده‌ای موجود در گره جلویی (front) را بازمی‌گردانیم:

return front->data;

 کد تابع Peek در C:

int Peek() {

    if (front == NULL) {

        printf("Queue is empty\n");

        return -1; // Added to handle empty queue case properly

    }

    return front->data;

}

4. تابع ()Print

تابع Print مسئول چاپ تمام عناصر داده‌ای در برنامه صف پیاده‌سازی شده با استفاده از لیست پیوندی است. در این تابع، اشاره‌گر `temp` را به گره جلویی (front) اشاره می‌دهیم و با استفاده از شرط `while`، صف پیوندی را پیمایش می‌کنیم.

راهنمای کامل انتخاب زبان برنامه نویسی: کدام زبان برنامه نویسی را یاد بگیریم؟

 کد تابع Print در C:

void Print() {

    struct Node* temp = front;

    while (temp != NULL) {

        printf("%d ", temp->data);

        temp = temp->next;

    }

    printf("\n");

}

 کد کامل برنامه در C برای پیاده‌سازی صف با استفاده از لیست پیوندی:

#include <stdio.h></stdio.h>

#include <stdlib.h></stdlib.h>

struct Node {

    int data;

    struct Node* next;

};

// دو متغیر سراسری برای ذخیره آدرس‌های گره‌های جلویی و انتهایی

struct Node* front = NULL;

struct Node* rear = NULL;

// تابع Enqueue برای افزودن یک عدد صحیح به صف

void Enqueue(int x) {

    struct Node* temp = (struct Node*)malloc(sizeof(struct Node));

    temp->data = x;

    temp->next = NULL;

    if (front == NULL && rear == NULL) {

        front = rear = temp;

        return;

    }

    rear->next = temp;

    rear = temp;

}

// تابع Dequeue برای حذف یک عدد صحیح از صف

void Dequeue() {

    struct Node* temp = front;

    if (front == NULL) {

        printf("Queue is Empty\n");

        return;

    }

    if (front == rear) {

        front = rear = NULL;

    } else {

        front = front->next;

    }

    free(temp);

}

// تابع Peek برای مشاهده عنصر جلویی صف بدون حذف آن

int Peek() {

    if (front == NULL) {

        printf("Queue is empty\n");

        return -1; // Added to handle empty queue case properly

    }

    return front->data;

}

// تابع Print برای چاپ تمام عناصر صف

void Print() {

    struct Node* temp = front;

    while (temp != NULL) {

        printf("%d ", temp->data);

        temp = temp->next;

    }

    printf("\n");

}

int main() {

    // چاپ عناصر صف پس از هر عملیات Enqueue یا Dequeue

    printf("\n");

    printf("اولین درج\n");

    Enqueue(2); Print();

    printf("دومین درج\n");

    Enqueue(4); Print();

    printf("سومین درج\n");

    Enqueue(6); Print();

    printf("وضعیت صف پس از عملیات Dequeue()\n");

    Dequeue(); Print();

    printf("چهارمین درج\n");

    Enqueue(8); Print();

}

 نتیجه اجرای برنامه:

در این برنامه، ما عملیات‌های Enqueue را با انجام چهار فراخوانی مختلف انجام می‌دهیم و یک عملیات Dequeue را نیز انجام می‌دهیم. در نهایت، وضعیت صف پس از هر عملیات با استفاده از تابع `()Print` چاپ می‌شود.

از دست ندهید: چند زبان برنامه نویسی داریم؟ چند تا باید یاد بگیریم؟

در این مقاله، شما با پیاده‌سازی صف با استفاده از لیست پیوندی آشنا شدید. لیست پیوندی یک ساختار داده‌ای پویا است که می‌تواند عناصر داده‌ای با انواع مختلف را ذخیره کند. همچنین، ماهیت پویا بودن لیست‌های پیوندی به حل مشکلات هدر رفت حافظه در پیاده‌سازی صف کمک می‌کند. در اینجا، شما با توسعه عملیات‌های اصلی صف با استفاده از توضیحات کد آشنا شدید. پس از آن، پیاده‌سازی کد صف با استفاده از زبان برنامه‌نویسی C را مشاهده کردید.

در پایان، اگر سوالی در مورد این مقاله و پیاده‌سازی صف با استفاده از لیست پیوندی دارید، لطفاً آن را در بخش نظرات این صفحه مطرح کنید؛ ما به زودی به آن‌ها پاسخ خواهیم داد!