Algorithms/queues

تشبه الأرتال 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); 
	} 
}

إنشاء الرتل باستخدام المكدس

يمكن إنشاء الرتل باستخدام مكدسين، ولو فرضنا أنّ الرتل المراد إنشاؤه هو q و أنّ المكدسين المستخدمين هما stack1 و stack2. فيمكن إنشاء الرتل بثلاث طرق:

الطريقة الأولى: الاعتماد على عملية enqueue()‎

في هذه الطريقة نحرص على أن نتأكد من أنّ آخر عنصر يدخل هو العنصر الأعلى في المكدس الأول، وبهذا تحذف العملية deQueue()‎ العناصر من المكدس الأول فقط، ويستخدم المكدس الثاني لوضع العنصر في قمة المكدس الأول.

يمكن تلخيص هذه الطريقة بالخطوات التالية:

• enQueue(q,x)‎:

1. ادفع كل شيء من المكدس الأول إلى المكدس الثاني ما دام المكدس الأول غير فارغ.
2. ادفع العنصر x إلى المكدس الأول (على فرض أنّ حجمي المكدسين غير محددين).
3. ادفع كل شيء إلى المكدس الأول.

التعقيد الزمني لهذه العملية سيكون O(n)‎.

• dequeue(q)‎:

1. إن كان المكدس الأول فارغًا فتطلق الدالة خطأً.
2. احذف عنصرًا من المكدس الأول وأعده.

التعقيد الزمني لهذه العملية هو O(1)‎.

أمثلة

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

• C++‎:

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

struct Queue { 
	stack<int> s1, s2; 

	void enQueue(int x) 
	{ 
		// نقل جميع العناصر من المكدس الأول إلى الثاني
		while (!s1.empty()) { 
			s2.push(s1.top()); 
			s1.pop(); 
		} 

		// إدراج العنصر في المكدس الأول 
		s1.push(x); 

		// إرجاع كل شيء إلى المكدس الأول
		while (!s2.empty()) { 
			s1.push(s2.top()); 
			s2.pop(); 
		} 
	} 

	// إزالة عنصر من الرتل 
	int deQueue() 
	{ 
		// إن كان المكدس الأول فارغًا 
		if (s1.empty()) { 
			cout << "Q is Empty"; 
			exit(0); 
		} 

		// إعادة العنصر العلوي في المكدس الأول 
		int x = s1.top(); 
		s1.pop(); 
		return x; 
	} 
}; 

// اختبار الدوال السابقة 
int main() 
{ 
	Queue q; 
	q.enQueue(1); 
	q.enQueue(2); 
	q.enQueue(3); 

	cout << q.deQueue() << '\n'; 
	cout << q.deQueue() << '\n'; 
	cout << q.deQueue() << '\n'; 

	return 0; 
}

• بايثون:

class Queue:
	def __init__(self):
		self.s1 = []
		self.s2 = []
	def enQueue(self, x):
		# نقل جميع العناصر من المكدس الأولى إلى المكدس الثاني
		while len(self.s1) != 0:
			self.s2.append(self.s1[-1])
			self.s1.pop()
		# نقل العنصر إلى المكدس الأول
		self.s1.append(x) 
		# إعادة كل العناصر إلى المكدس الأول
		while len(self.s2) != 0:
			self.s1.append(self.s2[-1])
			self.s2.pop()
	# إزالة عنصر من الرتل
	def deQueue(self):
		#إن كان المكدس الأول فارغًا
		if len(self.s1) == 0:
			print(“Q is Empty”)
		# إعادة العنصر الأول في المكدس الأول
		x = self.s1[-1]
		self.s1.pop()
		return x
# اختبار الدوال السابقة
if __name__ == ‘__main__’:
	q = Queue()
	q.enQueue(1)
	q.enQueue(2)
	q.enQueue(3) 
	print(q.deQueue())
	print(q.deQueue())
	print(q.deQueue())

• جافا:

import java.util.*; 

class GFG 
{ 
static class Queue 
{ 
	static Stack<Integer> s1 = new Stack<Integer>(); 
	static Stack<Integer> s2 = new Stack<Integer>(); 

	static void enQueue(int x) 
	{ 
		// نقل جميع العناصر من المكدس الأول إلى الثاني
		while (!s1.isEmpty()) 
		{ 
			s2.push(s1.pop()); 
			//s1.pop(); 
		} 

		// إدراج العنصر في المكدس الأول 
		s1.push(x); 

		// إعادة كل العناصر من المكدس الثاني إلى المكدس الأول
		while (!s2.isEmpty()) 
		{ 
			s1.push(s2.pop()); 
			//s2.pop(); 
		} 
	} 

	//إزالة عنصر من الرتل
	static int deQueue() 
	{ 
		// إن كان المكدس الأول فارغًا
		if (s1.isEmpty()) 
		{ 
			System.out.println("Q is Empty"); 
			System.exit(0); 
		} 

		// إعادة العنصر لأول في المكدس الأول 
		int x = s1.peek(); 
		s1.pop(); 
		return x; 
	} 
}; 

// اختبار الدوال السابقة 
public static void main(String[] args) 
{ 
	Queue q = new Queue(); 
	q.enQueue(1); 
	q.enQueue(2); 
	q.enQueue(3); 

	System.out.println(q.deQueue()); 
	System.out.println(q.deQueue()); 
	System.out.println(q.deQueue()); 
} 
}

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

1
2
3

الطريقة الثانية: الاعتماد على عملية deQueue

يُدرج العنصر الجديد في قمة المكدس الأول بواسطة عملية enQueue، أما عملية dequeue فيجري التحقق ممّا إذا كان المكدس الثاني فارغًا و لا، فإن كان كذلك تُنقل جميع العناصر إلى المكدس الثاني وتعيد العملية أعلى عنصر فيه.

ويمكن تلخيص هذه الطريقة بالخطوات التالية:

• enQueue(q, x)‎

  1. إضافة العنصر x إلى المكدس الأول (على فرض أنّ حجم المكدسين غير محدود). التعقيد الزمني لهذه العملية هو O(1)‎.

• deQueue(q)‎:

  1. إن كان المكدسان فارغين تطلق العملية خطأً.

  2. إن كان المكدس الثاني فارغًا وما دام المكدس الأول غير فارغ فستنقل الدالة جميع العناصر من المكدس الأول إلى المكدس الثاني.

  3. تحذف الدالة أعلى عنصر المكدس الثاني وتعيده.

     التعقيد الزمني لهذه العملية هو O(n)‎.

يجدر الانتباه إلى أنّ الطريقة الثانية أفضل من الطريقة الأولى بكثير، وذلك لأنّ الطريقة الأولى تنقل جميع العناصر مرتين في عملية enQueue، في حين أنّ الطريقة الثانية تنقل العناصر مرة واحدة وعندما يكون المكدس الثاني فارغًا فقط.

أمثلة

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

• C++‎:

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

struct Queue { 
	stack<int> s1, s2; 

	// إضافة عنصر إلى الرتل
	void enQueue(int x) 
	{ 
		// إضافة العنصر إلى المكدس الأول 
		s1.push(x); 
	} 

	// إزالة عنصر من الرتل 
	int deQueue() 
	{ 
		// إن كان المكدسان فارغين 
		if (s1.empty() && s2.empty()) { 
			cout << "Q is empty"; 
			exit(0); 
		} 

		// إن كان المكدس الثاني فارغًا فسننقل جميع العناصر من المكدس الأول إلى المكدس الثاني
		if (s2.empty()) { 
			while (!s1.empty()) { 
				s2.push(s1.top()); 
				s1.pop(); 
			} 
		} 

		// إعادة أعلى عنصر في المكدس الثاني 
		int x = s2.top(); 
		s2.pop(); 
		return x; 
	} 
}; 

// اختبار الدوال السابقة
int main() 
{ 
	Queue q; 
	q.enQueue(1); 
	q.enQueue(2); 
	q.enQueue(3); 

	cout << q.deQueue() << '\n'; 
	cout << q.deQueue() << '\n'; 
	cout << q.deQueue() << '\n'; 

	return 0; 
}

• جافا:

يلاحظ أنّ الشيفرة تستخدم الصنف Stack لإنشاء الأكداس:

import java.util.Stack; 

public class GFG { 
	/* صنف الرتل المكوّن من مكدسين */
	static class Queue { 
		Stack<Integer> stack1; 
		Stack<Integer> stack2; 
	} 

	/* دالة لإدراج العناصر في المكدس*/
	static void push(Stack<Integer> top_ref, int new_data) 
	{ 
		// إضافة البيانات إلى المكدس 
		top_ref.push(new_data); 
	} 

	/* دالة لحذف البيانات من المكدس*/
	static int pop(Stack<Integer> top_ref) 
	{ 
		/*إطلاق خطأ إن كان المكدس فارغًا */
		if (top_ref.isEmpty()) { 
			System.out.println("Stack Underflow"); 
			System.exit(0); 
		} 

		// إزالة البيانات من المكدس 
		return top_ref.pop(); 
	} 

	// دالة لإدراج عنصر في الرتل 
	static void enQueue(Queue q, int x) 
	{ 
		push(q.stack1, x); 
	} 

	/* دالة لإزالة عنصر من الرتل */
	static int deQueue(Queue q) 
	{ 
		int x; 

		/* إطلاق خطأ إن كان المكدسان فارغين */
		if (q.stack1.isEmpty() && q.stack2.isEmpty()) { 
			System.out.println("Q is empty"); 
			System.exit(0); 
		} 

		/* نقل جميع العناصر من المكدس الأول إلى الثاني بشرط أن يكون المكدس الثاني فارغًا */
		if (q.stack2.isEmpty()) { 
			while (!q.stack1.isEmpty()) { 
				x = pop(q.stack1); 
				push(q.stack2, x); 
			} 
		} 
		x = pop(q.stack2); 
		return x; 
	} 

	/* اختبار الدوال السابقة */
	public static void main(String args[]) 
	{ 
		/* إنشاء رتل يتضمن ثلاثة عناصر*/
		Queue q = new Queue(); 
		q.stack1 = new Stack<>(); 
		q.stack2 = new Stack<>(); 
		enQueue(q, 1); 
		enQueue(q, 2); 
		enQueue(q, 3); 

		/* إزالة العناصر من الرتل */
		System.out.print(deQueue(q) + " "); 
		System.out.print(deQueue(q) + " "); 
		System.out.println(deQueue(q) + " "); 
	} 
}

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

1
2
3

الطريقة الثالثة: استخدام مكدس واحد إلى جانب مكدس استدعاء الدالة

يمكن إنشاء رتل باستخدام مكدس واحد إلى جانب مكدس استدعاء الدالة Function Call Stack، ويمكن تلخيص هذه الطريقة بالخطوات التالية:

• enQueue(x)‎
  1. إضافة العنصر x إلى المكدس الأول.
• deQueue:
  1. نطلق خطأً إن كان المكدس الأول فارغًا.
  2. إن كان هناك عنصر واحد في المكدس الأول فنعيد ذلك العنصر.
  3. نحذف كل شيء من المكدس الأول تعاوديًا، ثم نخزّن العناصر المحذوفة في متغير لنعيدها بعد ذلك إلى المكدس الأول ونعيد قيمة المتغير.

تضمن الخطوة 3 إعادة آخر عنصر يُحذف من الرتل، ولما كانت عملية التعاود ستتوقف عند وصول عدد العناصر في المكدس الأول إلى عنصر واحد (الخطوة 2) فسنحصل على العنصر الأخير في المكدس الأول باستخدام الدالة deQueue()‎ ونعيد باقي العناصر إلى المكدس الأول في الخطوة 3.

أمثلة

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

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

struct Queue { 
	stack<int> s; 

	// إدراج عنصر في الرتل
	void enQueue(int x) 
	{ 
		s.push(x); 
	} 

	// إزالة عنصر من الرتل 
	int deQueue() 
	{ 
		if (s.empty()) { 
			cout << "Q is empty"; 
			exit(0); 
		} 

		// حذف عنصر من المكدس 
		int x = s.top(); 
		s.pop(); 

		// إن أصبح المكدس فارغًا، نعيد العنصر المحذوف
		if (s.empty()) 
			return x; 

		// استدعاء تعاودي 
		int item = deQueue(); 

		// إرجاع العنصر المحذوف إلى المكدس 
		s.push(x); 

		// إعاد نتيجة استدعاء الدالة 
		return item; 
	} 
}; 

// اختبار الدوال السابقة
int main() 
{ 
	Queue q; 
	q.enQueue(1); 
	q.enQueue(2); 
	q.enQueue(3); 

	cout << q.deQueue() << '\n'; 
	cout << q.deQueue() << '\n'; 
	cout << q.deQueue() << '\n'; 

	return 0; 
}

• جافا:

import java.util.Stack; 

public class QOneStack { 
	// صنف الرتل الذي يمتلك مكدسًا واحدًا
	static class Queue { 
		Stack<Integer> stack1; 
	} 

	/* دالة لإدراج العناصر في المكدس*/
	static void push(Stack<Integer> top_ref, int new_data) 
	{ 
		/* إضافة البيانات */
		top_ref.push(new_data); 
	} 

	/* دالة لإزالة العناصر من المكدس*/
	static int pop(Stack<Integer> top_ref) 
	{ 
		/*إطلاق خطأ في حال كان المكدس فارغًا */
		if (top_ref == null) { 
			System.out.println("Stack Underflow"); 
			System.exit(0); 
		} 
		// إعادة عنصر من المكدس 
		return top_ref.pop(); 
	} 

	/* دالة لإدراج عنصر في الرتل */
	static void enQueue(Queue q, int x) 
	{ 
		push(q.stack1, x); 
	} 

	/* دالة لإزالة عنصر من الرتل */
	static int deQueue(Queue q) 
	{ 
		int x, res = 0; 
		/* إطلاق خطأ إن كان المكدس فارغًا */
		if (q.stack1.isEmpty()) { 
			System.out.println("Q is Empty"); 
			System.exit(0); 
		} 
		// التحقق من كون هذا العنصر هو العنصر الأخير 
		else if (q.stack1.size() == 1) { 
			return pop(q.stack1); 
		} 
		else { 

			/* حذف عنصر من المكدس الأول */
			x = pop(q.stack1); 

			/* تخزين آخر عنصر محذوف */
			res = deQueue(q); 

			/* إرجاع كل شيء إلى المكدس الأول */
			push(q.stack1, x); 
			return res; 
		} 
		return 0; 
	} 

	/* اختبار الدوال السابقة */
	public static void main(String[] args) 
	{ 
		/* إنشاء رتل بثلاثة عناصر*/
		Queue q = new Queue(); 
		q.stack1 = new Stack<>(); 

		enQueue(q, 1); 
		enQueue(q, 2); 
		enQueue(q, 3); 

		/* إزالة العناصر */
		System.out.print(deQueue(q) + " "); 
		System.out.print(deQueue(q) + " "); 
		System.out.print(deQueue(q) + " "); 
	} 
}

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

1
2
3

المصادر

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