صف حلقوی در ساختمان داده چیست و چگونه پیاده‌سازی می‌شود؟

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

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

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

عملیات رایج بر روی صف حلقوی عبارتند از:

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

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

بررسی خالی بودن صف (isEmpty): این عملیات بررسی می‌کند که آیا صف خالی است یا خیر. اگر اشاره‌گر جلو و عقب در یک مکان قرار داشته باشند، صف خالی است.

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

نمایش عناصر صف (Peek): این عمل اولین عنصر در صف را بدون حذف آن برمی گرداند.

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

کاربردهای صف حلقوی

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

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

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

شبکه‌های کامپیوتری: در شبکه‌های کامپیوتری، صف حلقوی برای مدیریت بسته‌های داده استفاده می‌شود. روترها و سوئیچ‌ها از صف حلقوی برای ذخیره بسته‌های داده‌ای که در حال پردازش هستند، استفاده می‌کنند.

پردازش سیگنال: در پردازش سیگنال، صف حلقوی برای ذخیره نمونه‌های سیگنال استفاده می‌شود. این امر به ویژه در سیستم‌هایی که با سیگنال‌های پیوسته سروکار دارند، مانند سیستم‌های صوتی و تصویری، مفید است.

زمانبندی پردازش‌ها: در سیستم‌های عامل، صف حلقوی برای زمان‌بندی پردازش‌ها مورد استفاده قرار می‌گیرد. به این ترتیب که پردازش‌هایی که می‌خواهند از cpu استفاده کنند را در داخل یک صف حلقوی قرار می‌دهند و cpu به ترتیب پردازش‌ها را اجرا می‌کند.

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

عملیات ورود به صف

عملیات ورود به صف یا "Enqueue" در ساختار داده صف، فرآیند اضافه کردن یک عنصر جدید به انتهای صف است. این عملیات به طور معمول با استفاده از یک اشاره‌گر به نام "عقب" یا "tail" انجام می‌شود. ابتدا، بررسی می‌شود که آیا صف پر است یا خیر. در صورتی که صف پر باشد، عملیات با خطا مواجه شده و عنصر جدید اضافه نمی‌شود. اگر صف پر نباشد، اشاره‌گر "عقب" به مکانی اشاره می‌کند که عنصر جدید باید در آن اضافه شود. عنصر جدید در این مکان قرار داده می‌شود. سپس، اشاره‌گر "عقب" یک واحد افزایش می‌یابد تا به مکان بعدی برای اضافه کردن عنصر جدید اشاره کند. در صف‌های حلقوی، اگر اشاره‌گر "عقب" به انتهای آرایه برسد، به ابتدای آرایه برمی‌گردد. این فرآیند اطمینان می‌دهد که عناصر به ترتیب ورود به صف اضافه می‌شوند و اصل FIFO (اولین ورودی، اولین خروجی) رعایت می‌شود.

سناریو‌های مختلف افزودن عنصر به لیست

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

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

الگوریتم افزودن عنصر به صف حلقوی (Enqueue) به شرح زیر است:

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

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

افزودن عنصر: عنصر جدید در مکان اشاره شده توسط اشاره‌گر عقب قرار می‌گیرد.

بررسی خالی بودن صف (در صورت نیاز): اگر صف قبلا خالی بوده و اکنون اولین عنصر اضافه شده است، اشاره‌گر جلو نیز باید به مکان اولین عنصر اشاره کند. به این صورت که اگر جلو -1==  باشد، جلو = 0 قرار داده می‌شود.

هنگام کار با صف حلقوی مهم است به چند نکته مهم دقت کنید. ظرفیت (capacity) نشان‌دهنده اندازه آرایه مورد استفاده برای صف حلقوی است. اشاره‌گر جلو به اولین عنصر صف و اشاره‌گر عقب به آخرین عنصر صف اشاره می‌کند. اگر صف خالی باشد، جلو == عقب == -1 است. اگر صف پر باشد، (عقب + 1) % ظرفیت == جلو است.

این الگوریتم اطمینان می‌دهد که عناصر به ترتیب ورود به صف اضافه می‌شوند و اصل FIFO (اولین ورودی، اولین خروجی) رعایت می‌شود.

عملیات استخراج داده از صف

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

پیاده سازی صف حلقوی با زبان پایتون

اکنون که اطلاعات اولیه در ارتباط با صف حلقوی را به دست آوریم، وقت آن رسیده تا نحوه پیاده‌سازی صف حلقوی در پایتون را مورد بررسی قرار دهیم. این فرآیند به شرح زیر است:

class CircularQueue:

    def __init__(self, capacity):

        self.capacity = capacity

        self.queue = [None] * capacity

        self.front = self.rear = -1

    def enqueue(self, item):

        if (self.rear + 1) % self.capacity == self.front:

            print("صف پر است")

            return

        elif self.front == -1:

            self.front = 0

            self.rear = 0

        else:

            self.rear = (self.rear + 1) % self.capacity

        self.queue[self.rear] = item

    def dequeue(self):

        if self.front == -1:

            print("صف خالی است")

            return

        elif self.front == self.rear:

            temp = self.queue[self.front]

            self.front = self.rear = -1

            return temp

        else:

            temp = self.queue[self.front]

            self.front = (self.front + 1) % self.capacity

            return temp

    def display(self):

        if self.front == -1:

            print("صف خالی است")

            return

        elif self.rear >= self.front:

            for i in range(self.front, self.rear + 1):

                print(self.queue[i], end=" ")

            print()

        else:

            for i in range(self.front, self.capacity):

                print(self.queue[i], end=" ")

            for i in range(0, self.rear + 1):

                print(self.queue[i], end=" ")

            print()

# مثال استفاده

q = CircularQueue(5)

q.enqueue(1)

q.enqueue(2)

q.enqueue(3)

q.enqueue(4)

q.enqueue(5)

q.display()  # خروجی: 1 2 3 4 5

q.dequeue()

q.display()  # خروجی: 2 3 4 5

q.enqueue(6)

q.display() # خروجی 2 3 4 5 6

توضیحات قطعه کد بالا به شرح زیر است:

__init__(self, capacity): سازنده کلاس است که ظرفیت صف و آرایه را برای ذخیره عناصر صف ایجاد می‌کند. همچنین، اشاره‌گرهای front و rear را با مقدار اولیه -1 مقداردهی می‌کند.

enqueue(self, item): این متد یک عنصر جدید را به انتهای صف اضافه می‌کند. ابتدا بررسی می‌کند که آیا صف پر است یا خیر. اگر پر باشد، پیام "صف پر است" را چاپ می‌کند. در غیر این صورت، عنصر جدید را به انتهای صف اضافه می‌کند و اشاره‌گر rear را به‌روزرسانی می‌کند.

dequeue(self): این متد اولین عنصر صف را حذف می‌کند و مقدار آن را برمی‌گرداند. ابتدا بررسی می‌کند که آیا صف خالی است یا خیر. اگر خالی باشد، پیام "صف خالی است" را چاپ می‌کند. در غیر این صورت، اولین عنصر صف را حذف می‌کند و اشاره‌گر front را به‌روزرسانی می‌کند.

display(self): این متد تمام عناصر موجود در صف را چاپ می‌کند. ابتدا بررسی می‌کند که آیا صف خالی است یا خیر. اگر خالی باشد، پیام "صف خالی است" را چاپ می‌کند. در غیر این صورت، تمام عناصر موجود در صف را به ترتیب چاپ می‌کند.