الأرتال

تشبه الأرتال Queues المكادس Stacks في كونها بنى معطيات خطية تتبع نمطًا معيّنًا في ترتيب العناصر وإجراء العمليات عليها، والترتيب المتّبع في الأرتال هو يدخل أولًا يخرج أولًا (First In First Out أو FIFO اختصارًا). أفضل مثال على الرتل هو طابور المستهلكين الذين يقفون عند المحاسب في المحال التجارية، فأول شخص يدخل إلى الطابور هو أول شخص سيخرج منه بعد دفع الحساب. ومن هنا يمكن معرفة أنّ الفرق بين الرتل والمكدس هو في خروج العناصر، إذ أنّ آخر عنصر يضاف إلى المكدس هو الذي سيخرج أولًا، أما آخر عنصر يضاف إلى المكدس فهو الذي سيخرج آخرًا.

العمليات الخاصة بالأرتال

يمكن -عامّةً- إجراء أربع عمليات أساسية على الأرتال:

الإضافة Enqueue: تضيف هذه العملية عنصرًا إلى الرتل، وإن كان الرتل ممتلئًا فتسمّى الحالة حينئذٍ بحالة الفيض(تجاوز السعة) overflow.

الإزالة Dequeue: تزيل هذه العملية عنصرًا من الرتل، وتُزال العناصر من الرتل بنفس ترتيب إضافتها، وإن كان الرتل فارغًا فتسمّى الحالة حينئذٍ بحالة الغيض undeflow.

العنصر الأمامي Front: يمكن من خلال هذا العملية الحصول على العنصر الأمامي في الرتل.

العنصر الخلفي Rear: يمكن من خلال هذه العملية الحصول على العنصر الخلفي في الرتل.

تطبيقات على الأرتال

تستخدم الأرتال عندما لا تكون هناك حاجة للتعامل مع الأشياء مباشرة، وإنّما يكون التعامل معه حسب الترتيب (يدخل أولًا يخرج أولًا) مثل خوارزمية البحث بالعرض أولًا Breadth First Search، وهذه الخاصية تجعل الأرتال مفيدة في الحالات التالية:

1. عندما يكون المورد مشتركًا بين عددٍ من المستهلكين، مثل جدول المعالج المركزي، وجدولة الأقراص الصلبة.
2. عند نقل البيانات بطريقة غير تزامنية asynchronously (أي لا تكون سرعة استلام البيانات مساوية بالضرورة لسرعة إرسالها) بين عمليتين، مثل ذاكراة المدخلات والمخرجات IO Buffres، الأنابيب pipes ومدخلات ومخرجات الملفات file IO وغيرها.

إنشاء الأرتال باستخدام المصفوفات

يجب متابعة فهرسين من فهارس المصفوفة عند استخدامها في إنشاء الأرتال وهما الفهرسان الأول والأخير، إذ تضاف العناصر إلى نهاية المصفوفة وتزال من بدايتها. قد يبدو الأمر بسيطًا ولكن زيادة الفهرسين الأول والأخير قد يتسبب في حدوث مشكلة هي وصول المؤشر الأول إلى نهاية المصفوفة؛ ولحل هذه المشكلة يجب زيادة الفهرسين الأول والأخير بطريقة دائرية.

التعقيد الزمني

التعقيد الزمني لجميع العمليات الخاصة بالأرتال مثل enqueue()‎ و dequeue()‎ و isFull()‎ وisEmpty()‎ و front()‎ و rear()‎ هو O(1)‎، وذلك لعدم استخدام الحلقات التكرارية لدى تنفيذ هذه العمليات.

أمثلة

تعرض الأمثلة التالية طريقة إنشاء الأرتال باستخدام المصفوفات في عدد من لغات البرمجة:

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

// بنية لتمثيل الأرتال
class Queue 
{ 
	public: 
	int front, rear, size; 
	unsigned capacity; 
	int* array; 
}; 

// تنشئ هذه الدالة رتلًا بسعة معينة
// وتهيئ الرتل ليكون بالحجم 0
Queue* createQueue(unsigned capacity) 
{ 
	Queue* queue = new Queue(); 
	queue->capacity = capacity; 
	queue->front = queue->size = 0; 
	queue->rear = capacity - 1; // enqueue هذه الخطوة مهمة راجع الدالة
	queue->array = new int[(queue->capacity * sizeof(int))]; 
	return queue; 
} 

// يصبح الرتل ممتلئًا عندما
// عندما يصبح حجم الرتل مساويًا لسعته

int isFull(Queue* queue) 
{ return (queue->size == queue->capacity); } 

// يصبح الرتل فارغًا عندما يصبح حجمه مساويًا للصفر

int isEmpty(Queue* queue) 
{ return (queue->size == 0); } 

// تضيف الدالة عنصرًا إلى الرتل
// وتعدل الفهرس الأخير وحجم الرتل
void enqueue(Queue* queue, int item) 
{ 
	if (isFull(queue)) 
		return; 
	queue->rear = (queue->rear + 1) % queue->capacity; 
	queue->array[queue->rear] = item; 
	queue->size = queue->size + 1; 
	cout << item << " enqueued to queue\n"; 
} 

// تحذف الدالة عنصرًا من الرتل
// وتعدل الفهرس الأول وحجم الرتل
int dequeue(Queue* queue) 
{ 
	if (isEmpty(queue)) 
		return INT_MIN; 
	int item = queue->array[queue->front]; 
	queue->front = (queue->front + 1) % queue->capacity; 
	queue->size = queue->size - 1; 
	return item; 
} 

// تجلب الدالة العنصر الأول في الرتل
int front(Queue* queue) 
{ 
	if (isEmpty(queue)) 
		return INT_MIN; 
	return queue->array[queue->front]; 
} 

// تجلب الدالة العنصر الأخير في الرتل
int rear(Queue* queue) 
{ 
	if (isEmpty(queue)) 
		return INT_MIN; 
	return queue->array[queue->rear]; 
} 

// اختبار الدوال السابقة
int main() 
{ 
	Queue* queue = createQueue(1000); 

	enqueue(queue, 10); 
	enqueue(queue, 20); 
	enqueue(queue, 30); 
	enqueue(queue, 40); 

	cout<<dequeue(queue)<<" dequeued from queue\n"; 

	cout << "Front item is " << front(queue) << endl; 
	cout << "Rear item is " << rear(queue) << endl; 

	return 0; 
}

• بايثون:

# يستخدم هذا الصنف لتمثيل الرتل
class Queue: 

	# الدالة البانية
	def __init__(self, capacity): 
		self.front = self.size = 0
		self.rear = capacity -1
		self.Q = [None]*capacity 
		self.capacity = capacity 
	
	# يصبح الرتل ممتلئًا عندما
    # يصبح حجمه مساويًا لسعته
    def isFull(self): 
		return self.size == self.capacity 
	
	# يكون الرتل فارغًا عندما يساوي حجمه الصفر
    def isEmpty(self): 
		return self.size == 0

	# تضيف الدالة عنصرًا إلى الرتل
    # وتعدل الفهرس الأخير وحجم الرتل
    def EnQueue(self, item): 
		if self.isFull(): 
			print("Full") 
			return
		self.rear = (self.rear + 1) % (self.capacity) 
		self.Q[self.rear] = item 
		self.size = self.size + 1
		print("%s enqueued to queue" %str(item)) 

	# تحذف الدالة عنصرًا من الرتل
    # وتعدل الفهرس الأول وحجم الرتل
    def DeQueue(self): 
		if self.isEmpty(): 
			print("Empty") 
			return
		
		print("%s dequeued from queue" %str(self.Q[self.front])) 
		self.front = (self.front + 1) % (self.capacity) 
		self.size = self.size -1
		
	# تجلب الدالة العنصر الأول في الرتل
    def que_front(self): 
		if self.isEmpty(): 
			print("Queue is empty") 

		print("Front item is", self.Q[self.front]) 
		
	# تجلب الدالة العنصر الأخير في الرتل
    def que_rear(self): 
		if self.isEmpty(): 
			print("Queue is empty") 
		print("Rear item is", self.Q[self.rear]) 


# اختبار الدوال السابقة
if __name__ == '__main__': 

	queue = Queue(30) 
	queue.EnQueue(10) 
	queue.EnQueue(20) 
	queue.EnQueue(30) 
	queue.EnQueue(40) 
	queue.DeQueue() 
	queue.que_front() 
	queue.que_rear()

• جافا

// يستخدم هذا الصنف لتمثيل الرتل
class Queue 
{ 
	int front, rear, size; 
	int capacity; 
	int array[]; 
	
	public Queue(int capacity) { 
		this.capacity = capacity; 
		front = this.size = 0; 
		rear = capacity - 1; 
		array = new int[this.capacity]; 
			
	} 
	
	// يصبح الرتل ممتلئًا عندما
	// عندما يصبح حجم الرتل مساويًا لسعته

	boolean isFull(Queue queue) 
	{ return (queue.size == queue.capacity); 
	} 
	
	// يصبح الرتل فارغًا عندما يساوي حجمه الصفر
	boolean isEmpty(Queue queue) 
	{ return (queue.size == 0); } 
	
	// يضيف التابع عنصرًا إلى الرتل
    // ويعدل الفهرس الأخير وحجم الرتل
    void enqueue( int item) 
	{ 
		if (isFull(this)) 
			return; 
		this.rear = (this.rear + 1)%this.capacity; 
		this.array[this.rear] = item; 
		this.size = this.size + 1; 
		System.out.println(item+ " enqueued to queue"); 
	} 
	
	// يحذف التابع عنصرًا من الرتل
    // ويعدل الفهرس الأمامي وحجم الرتل
    int dequeue() 
	{ 
		if (isEmpty(this)) 
			return Integer.MIN_VALUE; 
		
		int item = this.array[this.front]; 
		this.front = (this.front + 1)%this.capacity; 
		this.size = this.size - 1; 
		return item; 
	} 
	
	// يجلب التابع العنصر الأول في الرتل
	int front() 
	{ 
		if (isEmpty(this)) 
			return Integer.MIN_VALUE; 
		
		return this.array[this.front]; 
	} 
		
	// يجلب التابع العنصر الأخير في الرتل
	int rear() 
	{ 
		if (isEmpty(this)) 
			return Integer.MIN_VALUE; 
		
		return this.array[this.rear]; 
	} 
} 

	
// اختبار التوابع السابقة
public class Test 
{ 
	public static void main(String[] args) 
	{ 
		Queue queue = new Queue(1000); 
			
		queue.enqueue(10); 
		queue.enqueue(20); 
		queue.enqueue(30); 
		queue.enqueue(40); 
		
		System.out.println(queue.dequeue() + 
					" dequeued from queue\n"); 
		
		System.out.println("Front item is " + 
							queue.front()); 
		
		System.out.println("Rear item is " + 
								queue.rear()); 
	} 
}

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

10 enqueued to queue
20 enqueued to queue
30 enqueued to queue
40 enqueued to queue
10 dequeued from queue
Front item is 20
Rear item is 40

إنشاء الأرتال باستخدام القوائم المترابطة

يجب الاهتمام بمؤشرين اثنين عند استخدام القوائم المترابطة في إنشاء الأرتال، وهما المؤشر الأمامي front والخلفي rear. يشير المؤشر الأمامي إلى العنصر الأول في الرتل، ويشير المؤشر الخلفي إلى العنصر الأخير في الرتل.

العملية enQueue()‎: تضيف هذه العملية عقدة جديد بعد المؤشر الخلفي وتحركه إلى العقدة التالية.

العملية deQueue()‎: تحذف هذه العملية العقدة الأمامية وتحرّك المؤشر الأمامي إلى العقد التالية.

التعقيد الزمني

التعقيد الزمني للعمليتين enqueue()‎ و dequeue()‎ هو O(1)‎ وذلك لأنّ العمليتين تعدّلان عددًا قليلًا من المؤشرات، ولا تُستخدم الحلقات التكرارية في أيّ منهما.

أمثلة

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

• C++‎:

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

// إنشاء عقدة في قائمة مترابطة لتخزين الرتل
class QNode 
{ 
	public: 
	int key; 
	QNode *next; 
}; 

// يخزّن المؤشر الأمامي العقدة الأمامية في القائمة المترابطة
// ويخزن المؤشر الخلفي العقدة الخلفية في القائمة المترابطة
class Queue 
{ 
	public: 
	QNode *front, *rear; 
}; 

// دالة مساعدة لإنشاء
// عقدة جديدة في القائمة المترابطة
QNode* newNode(int k) 
{ 
	QNode *temp = new QNode(); 
	temp->key = k; 
	temp->next = NULL; 
	return temp; 
} 

// دالة مساعدة لإنشاء رتل فارغ
Queue *createQueue() 
{ 
	Queue *q = new Queue(); 
	q->front = q->rear = NULL; 
	return q; 
} 

// تضيف الدالة مفتاحًا إلى الرتل
void enQueue(Queue *q, int k) 
{ 
	// إنشاء قائمة مترابطة جديدة
	QNode *temp = newNode(k); 

	// إن كان الرتل فارغًا فإنّ
    // العقدة الجديدة هي الأمامية والخلفية في نفس الوقت
    if (q->rear == NULL) 
	{ 
	q->front = q->rear = temp; 
	return; 
	} 

	// إضافة العقدة الجديدة
    // في نهاية الرتل وتعديل المؤشر الخلفي
    q->rear->next = temp; 
	q->rear = temp; 
} 

// تحذف الدالة
// مفتاحًا من الرتل المعطى
QNode *deQueue(Queue *q) 
{ 
	// Null إن كان الرتل فارغًا نعيد 
	if (q->front == NULL) 
	return NULL; 

	// تخزين المؤشر الأمامي السابق
    // وتحريكه خطوة واحدة إلى الأمام
    QNode *temp = q->front; 
	q->front = q->front->next; 

	// Null إن كانت قيمة المؤشر الأمامي 
    // Null عدّل المؤشر الخلفي ليصبح 
	if (q->front == NULL) 
	q->rear = NULL; 
	return temp; 
} 

// اختبار الدوال السابقة
int main() 
{ 
	Queue *q = createQueue(); 
	enQueue(q, 10); 
	enQueue(q, 20); 
	deQueue(q); 
	deQueue(q); 
	enQueue(q, 30); 
	enQueue(q, 40); 
	enQueue(q, 50); 
	QNode *n = deQueue(q); 
	if (n != NULL) 
	cout << "Dequeued item is " << n->key; 
	return 0; 
} 

// This code is contributed by rathbhupendra

• بايثون

# قائمة مترابطة لتخزين الرتل
class Node: 
	
	def __init__(self, data): 
		self.data = data 
		self.next = None

# إنشاء صنف يمثل الرتل

# يخزن العنصر الأول في الرتل العقدة الأولى
# ويخزن العنصر الأخير العقدة الأخيرة في القائمة المترابطة
class Queue: 
	
	def __init__(self): 
		self.front = self.rear = None

	def isEmpty(self): 
		return self.front == None
	
	# يضيف التابع عنصرًا إلى الرتل
    def EnQueue(self, item): 
		temp = Node(item) 
		
		if self.rear == None: 
			self.front = self.rear = temp 
			return
		self.rear.next = temp 
		self.rear = temp 

	# يحذف التابع عنصرًا من الرتل
    def DeQueue(self): 
		
		if self.isEmpty(): 
			return
		temp = self.front 
		self.front = temp.next

		if(self.front == None): 
			self.rear = None
		return str(temp.data) 

# اختبار التوابع السابقة
if __name__== '__main__': 
	q = Queue() 
	q.EnQueue(10) 
	q.EnQueue(20) 
	q.DeQueue() 
	q.DeQueue() 
	q.EnQueue(30) 
	q.EnQueue(40) 
	q.EnQueue(50) 
	
	print("Dequeued item is " + q.DeQueue())

• جافا

// إنشاء عقدة لتخزين الرتل
class QNode 
{ 
	int key; 
	QNode next; 
	
	// دالة بانية لإنشاء عقدة جديدة في القائمة المترابطة
    public QNode(int key) { 
		this.key = key; 
		this.next = null; 
	} 
} 

// إنشاء صنف لتمثيل الرتل

// يخزّن المؤشر الأمامي العقدة الأمامية في القائمة المترابطة
// ويخزن المؤشر الخلفي العقدة الخلفية في القائمة المترابطة

class Queue 
{ 
	QNode front, rear; 
	
	public Queue() { 
		this.front = this.rear = null; 
	} 
	
	// يضيف التابع مفتاحًا إلى الرتل
    void enqueue(int key) 
	{ 
		
		// إنشاء عقدة جديدة
		QNode temp = new QNode(key); 
	
		// إن كان الرتل فارغًا فإنّ
	    // العقدة الجديدة هي الأمامية والخلفية في نفس الوقت

		if (this.rear == null) 
		{ 
		this.front = this.rear = temp; 
		return; 
		} 
	
		// إضافة العقدة الجديدة إلى نهاية الرتل وتعديل المؤشر الخلفي
        this.rear.next = temp; 
		this.rear = temp; 
	} 
	
	// يحذف التابع مفتاحًا من الرتل
	QNode dequeue() 
	{ 
		// Null إن كان الرتل فارغًا نعيد
        if (this.front == null) 
		return null; 
	
		// تخزين المؤشر الأمامي السابق وتحريكه خطوة إلى الأمام
		QNode temp = this.front; 
		this.front = this.front.next; 
	
		// Null إن أصبح المؤشر الأمامي
        // Null سنعدّل المؤشر الخلفي ليصبح
		if (this.front == null) 
		this.rear = null; 
		return temp; 
	} 
} 

	
// اختبار التوابع السابقة
public class Test 
{ 
	public static void main(String[] args) 
	{ 
		Queue q=new Queue(); 
		q.enqueue(10); 
		q.enqueue(20); 
		q.dequeue(); 
		q.dequeue(); 
		q.enqueue(30); 
		q.enqueue(40); 
		q.enqueue(50); 
		
		System.out.println("Dequeued item is "+ q.dequeue().key); 
	} 
}

المصادر

• صفحة Queue | Set 1 (Introduction and Array Implementation)‎ في توثيق بنى المعطيات في موقع GeeksforGeeks.
• صفحة Queue | Set 2 (Linked List Implementation)‎ في توثيق بنى المعطيات في موقع GeeksforGeeks.