Algorithms/circular queues

الرتل الدائري -يسمى أيضًا بالذاكرة الحلقية Ring Buffer- هو من بنى المعطيات الخطية والتي تجري فيه العمليات حسب المبدأ FIFO (يدخل أولًا يخرج أولًا) ويرتبط الموقع الأخير في الرتل بالموقع الأول لتكوين دائرة.

لا يمكن إدراج العناصر في الأرتال العادية بعد امتلائها حتى لو كان هناك مساحة أمام الرتل.

يمكن إجراء العمليات التالية على الأرتال الدائرية:

• Front: الحصول على العنصر الأمامي من الرتل.
• Rear: الحصول على العنصر الأخير من الرتل.
• enQueue(value)‎: تستخدم هذه الدالة لإدراج عنصر في الرتل الدائري، ويُدرج العنصر الجديد في نهاية الرتل الدائري دائمًا، وحسب الخطوات التالية:

1. التحقق ممّا إذا كان الرتل ممتلئًا: ‎((rear == SIZE-1 && front == 0) || (rear == front-1))‎
2. إن كان الرتل ممتلئًا فنعرض رسالة تخبر المستخدم بامتلاء الرتل، وإن لم يكن الرتل ممتلئًا فيجري التحقق من الشرط التالي (rear == SIZE – 1 && front != 0) فإن كان النتيجة صحيحة تُنفّذ عملية الإسناد rear = 0 ويُدرج العنصر في الرتل.

• deQueue()‎: تستخدم هذه الدالة لحذف العنصر من الرتل الدائري، والعنصر المحذوف هو العنصر الأمامي في الرتل الدائري دائمًا، وحسب الخطوات التالية:
  1. التحقق من كون الرتل فارغًا أو لا front == -1.
  2. إن كان الرتل فارغًا فنعرض رسالة تخبر المستخدم بأن الرتل فارغ، وإن لم يكن الرتل فارغًا تنتقل الدالة إلى الخطوة الثالثة.
  3. التحقق من كون العنصر الأول مساويًا للعنصر الأخير front==rear فإن كانت النتيجة صحيحة فتنفذ العبارة front=rear=-1 وإلا فإنّ الدالة ستتحقق من الشرط front==size-1 فإن كان الشرط صحيحًا فتنفذ العبارة front=0 وتعيد العنصر المحذوف.

التعقيد الزمني للعمليات الخاصة بالأرتال الدائرية

التعقيد الزمني للعمليتين enQeue()‎ وdeQueue()‎ هو O(1)‎ وذلك لعدم استخدامها لأي حلقة تكرارية عند التنفيذ.

تطبيقات الأرتال الدائرية

1. إدارة الذاكرة: يمكن استغلال مواقع الذاكرة غير المستخدمة في الأرتال العادية واستعمالها في الأرتال الدائرية.
2. نظام حركة البيانات Traffic System: يمكن استخدام الأرتال الدائرية في أنظمة حركة البيانات المسيطر عليها بواسطة الحاسوب وذلك لتبديل إشارات المرور واحدًا تلو الآخر وبصورة متكررة وفي فترات زمنية محددة.
3. جدولة وحدة المعالجة المركزية CPU: تهيّئ أنظمة التشغيل غالبًا رتلًا من العمليات التي تكون جاهزة للتنفيذ أو التي تنتظر وقوع حدث معين.

أمثلة

تعرض الأمثلة التالية طريقة التعامل مع الرتل الدائري وفي عدد من لغات البرمجة:

• C++‎

#include<bits/stdc++.h> 
using namespace std; 

struct Queue 
{ 
	// تهيئة بداية ونهاية الرتل الدائري 
	int rear, front; 

	// الرتل الدائري 
	int size; 
	int *arr; 

	Queue(int s) 
	{ 
	front = rear = -1; 
	size = s; 
	arr = new int[s]; 
	} 

	void enQueue(int value); 
	int deQueue(); 
	void displayQueue(); 
}; 


/* دالة لإنشاء الرتل الدائري */
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) /* إدراج العنصر الأول */
	{ 
		front = rear = 0; 
		arr[rear] = value; 
	} 

	else if (rear == size-1 && front != 0) 
	{ 
		rear = 0; 
		arr[rear] = value; 
	} 

	else
	{ 
		rear++; 
		arr[rear] = value; 
	} 
} 

// دالة لحذف عنصر من الرتل الدائري 
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; 
} 

// دالة لعرض العناصر في الرتل الدائري 
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]); 
	} 
} 

/* اختبار الدوال السابقة */
int main() 
{ 
	Queue q(5); 

	// إدراج العناصر في الرتل الدائري
	q.enQueue(14); 
	q.enQueue(22); 
	q.enQueue(13); 
	q.enQueue(-6); 

	// عرض العناصر الموجودة في الرتل الدائري 
	q.displayQueue(); 

	// حذف عناصر من الرتل الدائري 
	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; 
}

• بايثون:

class CircularQueue(): 

	# الدالة البانية 
	def __init__(self, size): # تهيئة الصنف 
		self.size = size 
		
		# تهيئة الرتل
		self.queue = [None for i in range(size)] 
		self.front = self.rear = -1
	
    # دالة لإضافة العناصر إلى الرتل
	def enqueue(self, data): 
		
		# التحقق من امتلاء الرتل 
		if ((self.rear + 1) % self.size == self.front): 
			print(" Queue is Full\n") 
			
		# الشرط الذي سينفذ إن كان الرتل فارغًا 
		elif (self.front == -1): 
			self.front = 0
			self.rear = 0
			self.queue[self.rear] = data 
		else: 
			
			# الموقع التالي للعنصر الخلفي 
			self.rear = (self.rear + 1) % self.size 
			self.queue[self.rear] = data 

	# دالة لحذف العناصر من الرتل
	def dequeue(self): 
		if (self.front == -1): # الشرط الخاص بالرتل الفارغ
			print ("Queue is Empty\n") 
			
		# الشرط الخاص بعنصر واحد فقط 
		elif (self.front == self.rear): 
			temp=self.queue[self.front] 
			self.front = -1
			self.rear = -1
			return temp 
		else: 
			temp = self.queue[self.front] 
			self.front = (self.front + 1) % self.size 
			return temp 

	# دالة لعرض عناصر الرتل
	def display(self): 
	
		# الشرط الخاص بالرتل الفارغ 
		if(self.front == -1): 
			print ("Queue is Empty") 

		elif (self.rear >= self.front): 
			print("Elements in the circular queue are:", 
											end = " ") 
			for i in range(self.front, self.rear + 1): 
				print(self.queue[i], end = " ") 
			print () 

		else: 
			print ("Elements in Circular Queue are:", 
										end = " ") 
			for i in range(self.front, self.size): 
				print(self.queue[i], end = " ") 
			for i in range(0, self.rear + 1): 
				print(self.queue[i], end = " ") 
			print () 

		if ((self.rear + 1) % self.size == self.front): 
			print("Queue is Full") 

# اختبار الدوال السابقة
ob = CircularQueue(5) 
ob.enqueue(14) 
ob.enqueue(22) 
ob.enqueue(13) 
ob.enqueue(-6) 
ob.display() 
print ("Deleted value = ", ob.dequeue()) 
print ("Deleted value = ", ob.dequeue()) 
ob.display() 
ob.enqueue(9) 
ob.enqueue(20) 
ob.enqueue(5) 
ob.display()

تعطي الشيفرات السابقة المخرجات التالية:

 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

انظر أيضًا

• الأرتال
• رتل الأولوية

مصادر

• صفحة Circular Queue في توثيق بنى المعطيات في موقع GeeksforGeeks.