ال Circular Queue

السلام عليكم ,,

حياك الله أخي الكريم ,,

بالنسبة للطوابير الحلقية Circular Queues, فيمكن استخدام Static Array أو Linked Lists لتكون

Low Level Data Structure لها,,

قبل الإجابة على سؤالك ,, يجب معرفة التالي ::

- عدد العناصر هل تريده ثابت Static أم متغير Dynamic.

إذا كان ثابتاُ فبالطبع استخدام مصفوفة ثابتة الحجم Static Array سيكون أسهل بكثير ,, و أكثر كفاءة.

أما إذا كان عدد العناصر متغيراً فاستعمال LInked List هو الخيار الأفضل..

حاول أن تشرح لنا, ما الذي ستستخدمه و سنكون متابعين معك إن شاء الله ,,

إضافة بسيطة,, و هي أن معظم كود Queues على الانترنت,, استخدمت القوالب Templates فيه بدلاُ من تخصيصه لنوع معين كما هو معروف,, و كما هي العادة مع بنى الذاكرة data structure الشائعة ,,

و أيضاُ آذكر أن الـ Circular Buffer سيكون أصعب قليلاُ من الشكل الأصلي أو الـ َ Queue العادي ,,

تحياتي ,,

مشكور اخوي على مرورك الكريم

على العموم انا ابي العدد مايكون محدد يعني مفتوح والطريقة بتكون linked listالصراحة انا سويت برنامج عن linked list كيف تسوي عقد وتحذق وتضيف من البدايى والنهاية واشتغل اوكي

بس صراحة الكيو ماعندي فكرة عنه , والمشكلة انه المطلوب مني اسوي circular queue باستخدام اللينكد ليست

شفت كذا موقع فيه برامج عن الكيو بس الاكواد تكاد تكون خرافية بعض الشيئ والبرامج طويلة جدا جدا

أعتقد أن المصفوفه أفضل للكيو

إذا استعملت اللينك ليست لن تنتج كيو فعليا إنما سوف تكون تستخدم اللينك ليست بأسلوب شبيه

بإستخدام الكيو

وأعتقد أن بعض التطبيقات التي تستخدم الكيو مثل نظم التشغيل سوف يكون من غير الجيد

استخدام اللينك ليست لها , وذلك بسبب الكفاءة في التنفيذ .

والخيار يعود لك

تحياتي

بس المصفوفة يكون الحجم محدود اما باستخدام الليست يكون الخيار مفتوح لك

وعشان كذا قلت اني سويت برنامج عن الليست

يااخ خلدون

اذا استخدمت مصفوفة راح يكون العدد محدود اما الليست فالخيار متاح لك لادخال اي عدد من العناصر

صحيح أن العدد يكون محدود لكني أعتقد أن استخدام المصفوفه ممكن ان نضطر إليه في بعض

التطبيقات , حيث يكون من الصعب جدا استخدام اللست ,

انا لست ضد اللست , ولكن كطالب برمجه يجب أن يكون لديك فكره قويه عن إستخدامها مع المصفوفات بكفائة .

والله يااخ خلدون اذا كانت السالفة عن طريق المصفوفة فماكنت كتبت هالموضوع لانه اسهل شي تسويه بالمصفوفة

بس المشكلة انه باللست

وعشان كذا انا ادور كود للكيو عن طريق الليست

السلام عليكم ,,

يا أخ aimn20 أنا آسف للأخطاء التي ذكرتها في ردي السابق ,,

حيقيقة كانت على عجلة ,,

لأنني بدأت الكلام عن الـ َQueues بشكل عام و أدخلت الـ Circular فيها بالخطأ :hmm:

لكن عليك ,, المفروض استخدام مصفوفة ثابتة الحجم ,, لتصميم Circular Queue أو ما يسمى Data Buffer عادة ,,

لأننا لو فكرنا فليلاُ كما قال الأخ خلدون لا فائدة من Circular Queue و سيتحول إلى Linear إذا صممناه متغير الحجم ,,

لي عودة لشرح الأجزاء الرئيسية في الـ Circular Queue و بعض النقاط التي تسهل من عملية التعامل معه :rolleyes: احتاج فقط للرجوع إلى كتابي المفضل

و أيضاً للأخ خلدون لي عودة للكلام و مناقشة Data Buffers في أنظمة التشغيل و كيفية جعلها Very Optimized للتسريع من عملها بشكل لا يصدق و طبعاُ يتم هذا بالأسمبلي أحياناُ و لكن لنا عودة بعد الفاصل :thumb_up:

السلام عليكم أخ aimn20 ,,

سأبداُ بالشرح و لكن على افتراض أنك تعرف ما هو شكل الـ Circular Queue بالطبع قبل البدء في الكلام حوله ,,

سنحتاج إلى المتغيرات التالية ,,

1 - متغير أو ثابت constant يحمل سعة المصفوفة أو العدد الأقصى للعناص Capacity

2 - مصفوفة من أي نوع ترغب به كـ int على سبيل المثال و يكون حجمها هو Capacity

3 - متغيرين كـ index لمعرفة العنصر الأول في المصفوفة و العنصر الأخير first و last

4 - دالة مساعدة private ,, و ذلك للحصول على رقم العنصر التالي لأي عنصر نختاره ,,

طبعاُ سأذكر لك ما هي فائدة هذه الدالة مع أنه يمكن الاستغناء عنها إلا أننا سنحتاج لكتابة كود الدالة في الكثير من الأمكان أو نقوم باستدعائها و ترك الأمور لها لحساب موقع العنصر التالي لأي عنصر نختاره ,,

طبعاُ كل هذه الأمور سوف تكون في فئة و بالتالي تكون private!

المرة القادمة سوف أشرح ماهي الدالة المساعدة مع شرح بسيط لكيفية حركة البيانات داخل الـ Circular Queue ثم بعد ذلك الكلام عن أشهر الدوال التي تستخدم للتعامل مع الـ Queues كـ pop و push و غيرها,,

تحياتي ,,

السلام عليكم ,,

سنستخدم الدالة المساعدة لحل مشكلة بسيطة في تصميم الـ Circular Queue = CQ نفسه ,,

المشكلة تحدث عندما يكون أول عنصر في الـ CQ هو آخر عنصر في المصفوفة المستخدمة ,, و ذلك يحدث عندما يتم ادخال عناصر للـ CQ ثم اخراجها و بالتالي نقل مؤشر العنصر الأول في CQ إلى آخر عنصر في المصفوفة و بعدها يتم تعبئة الـ CQ من العنصر الأول من جديد و اكمال العملية كالسابق ,,

لفهم العملية بشكل أفضل انظر الى الصورتين التاليتين ,, في الأولى شكل الـ CQ و في الثانية شكل الـ Array التي تستخدم لحفظ عناصر الـ CQ ,, مع ملاحظة أن هاتين الصورتين توضحان الشكل الممكن بعد ادخال و اخراج عناصر من الـCQ بعد فترة من استخدامه ,, حيث أصبح first يؤشر على آخر عنصر في الـ CQ و last على عنصر معين بعد first,,

--- الصور رديئة لأنني لست من هواة التلوين :D ----

و المهم هنا هو first تصور أنه تم استخراج عنصر من الـ CQ و هي بهذا الشكل ,,

بالطبع,, سيكون هناك خطأ لأن مصفوفتنا لا تحتوي إلا على 9 عناصر و لا يوجد لدينا عنصر عاشر ,,

حل هذه المشكلة بأن نقوم بفحص قيمة first قبل استخراج أي عنصر ,,

أولاً للتأكد بأننا لسنا عند آخر عنصر في المصفوفة و إذا كنا عند آخر عنصر فسيكون first = 1 و الأمر الثاني بأن لا يكون last = first و معنى هذه العبارة أنه لا يوجد لدينا عناصر في الـ ْْCQ ,,

سنستخدم الدالة المساعدة في حساب next index دائماُ ,, و بالتالي هي التي تقوم بحساب العنصر التالي الذي يمكن استخدامه ,,

على كل حال أعتقد أن كلامي غير واضح كثيراُ و بإمكانك السؤال عن أي شيء إذا أردت ,,

و هذه هي طريقة حساب العنصر التالي في المصفوفة التي استخدمناها ,,

int next_index( int index ){

	int NextIndex;
	NextIndex = (Index + 1) % Capacity;

	return NextIndex;
}

حاول الاطلاع على الكود و فهمه فسيسهل لك الكثير في برمجة الـ CQ ,,

بالتوفيق إن شاء الله و لي عودة بعد أخذ فاصل طويل :thumb_up:

أهلاُ من جديد ,,

ستحتاج في الغالب لبرمجة الدوال التالية كواجهة للـ CQ :

أول شيء طبعاُ هو الـ Constructor ,,

ثانياُ دالة لمعرفة إذا كانت الـ CQ فارغة أم لا ,,

دالة لمعرفة عدد العناصر الموجودة في CQ ,,

دالة الحصول على عنصر pop و دالة اخرى لإدخال عنصر push ,,

أتمنى أنني استطعت المساعدة ,,

تحياتي لك و إذا واجهت مشكلة في كتابة الكود فلا تتردد في السؤال ,,

مشكور يااخ خالد على التوضيح

بس ياحبذا يكون الشرح مع الاكواد

أهلاُ أخ aimn20 ,,

قم بكتابة الكود اللازم ثم سنساعدك إن كان هناك أخطاء في البرنامج ,,

لأن عملية الشرح مع الكود طويلة و لست متفرغاُ هذه الأيام ,,

تحياتي ,,

ماهي هذي المشكلة بالكود لانه صراحة الدكتور بالمحاضرات مايشرح شي

على العموم انا عندي كود queue بس عادي ماهو دائري راح احطه لك

لو وضعت محاولتك سيكون أفضل لك حتى تفهم البرنامج و تستفيد منه مستقبلاُ لأنه سيمر عليك كثيراُ إذا كنت تدرس البرمجة في الجامعة :resentful: ,,

#include <iostream>
#include <stdlib.h>

using namespace std;


class Queue
{
private:
	enum {MAX=10};
	int array[MAX];
	int back,front;

public:
	Queue();

	void enqueue(int e);
	int dequeue();
	bool isFull();
	bool isEmpty();
};


Queue::Queue():
back(0),front(0)
{}

void Queue::enqueue(int e)
{
	if(isFull())
	{
		cout<<"\nQueue is Full";
		exit(1);
	}

	back=(back+1)%MAX;
	array[back]=e;
}


int Queue::dequeue()
{
	if(isEmpty())
	{
		cout<<"\nQueue is Empty";
		exit(1);
	}

	front=(front+1)%MAX;
	return array[front];
}


bool Queue::isFull()
{
	if( (back+1)%MAX == front )
		return true;
	else
		return false;
}

bool Queue::isEmpty()
{
	if( back == front )
		return true;
	else
		return false;
}


int main()
{
	Queue q;
	cout<<"\nenqueue(2)";
	q.enqueue(2);
	cout<<"\nenqueue(4)";
	q.enqueue(4);
	cout<<"\nenqueue(6)";
	q.enqueue(6);

	cout<<"\nDequeue elements\n";

	cout<<"dequeue: "<<q.dequeue()<<endl;
	cout<<"dequeue: "<<q.dequeue()<<endl;
	cout<<"dequeue: "<<q.dequeue()<<endl;

	return 0;
}

أعتقد أن هذا هو الكود المطلوب :clapping:

إذا كان هناك مشاكل تواجهها مع الكود أعلمنا بها ,,

تحياتي ,,

Khaled.Alshaya كتب:

أعتقد أن هذا هو الكود المطلوب :clapping:

إذا كان هناك مشاكل تواجهها مع الكود أعلمنا بها ,,

تحياتي ,,

اخ خالد

يعني افهم من كلامك انه هذا هو الكود المطلوب

ولنفترض انه هو

فالكود هو مدخل قيم ثابتة من

يعني كيف اخلي المستخدم هو اللي يدخل القيم

السلام عليكم ,,

أخ aimn20 طلبت المساعدة في تصميم Circular Queue و أنت لا تعرف كيف تستلم مدخلات من المستخدم عن طريق الكائن cin ,,

عجيب !!! :hmm:

اقتباس

و أيضاً للأخ خلدون لي عودة للكلام و مناقشة Data Buffers في أنظمة التشغيل و كيفية جعلها Very Optimized للتسريع

تحياتي

Khaled.Alshaya كتب:

السلام عليكم ,,

أخ aimn20 طلبت المساعدة في تصميم Circular Queue و أنت لا تعرف كيف تستلم مدخلات من المستخدم عن طريق الكائن cin ,,

عجيب !!! :hmm:

طيب

عديها

قول لي وشفايدة class و private

يعني اا سالني الدكتور بالمناقشة وش اقول له

السلام عليكم

(انا سويت برنامج عن linked list كيف تسوي عقد وتحذق وتضيف من البدايى والنهاية واشتغل اوكي)

ممكن الكود بصراحه انا لاول مره اسمع عن ال linked list .

او يمكن انا اعرفها بس باسم اخر لذى اتمنى لو حطيت الكود الذي كتبته .

مع التحيه

list.h

// list.h
// Template List class definition.
#ifndef LIST_H
#define LIST_H

#include <iostream>

using std::cout;

#include <new>
#include "listnode.h"  // ListNode class definition

template< class NODETYPE >
class List {

public:
   List();	  // constructor
   ~List();	 // destructor
   void insertAtFront( const NODETYPE & );
   void insertAtBack( const NODETYPE & );
   bool removeFromFront( NODETYPE & );
   bool removeFromBack( NODETYPE & );
   bool isEmpty() const;
   void print() const;

private:
   ListNode< NODETYPE > *firstPtr;  // pointer to first node
   ListNode< NODETYPE > *lastPtr;   // pointer to last node

   // utility function to allocate new node
   ListNode< NODETYPE > *getNewNode( const NODETYPE & );

}; // end class List

// default constructor
template< class NODETYPE >
List< NODETYPE >::List() 
   : firstPtr( 0 ), 
	 lastPtr( 0 ) 
{ 
   // empty body

} // end List constructor

// destructor
template< class NODETYPE >
List< NODETYPE >::~List()
{
   if ( !isEmpty() ) {	// List is not empty
	  cout << "Destroying nodes ...\n";

	  ListNode< NODETYPE > *currentPtr = firstPtr;
	  ListNode< NODETYPE > *tempPtr;

	  while ( currentPtr != 0 ) {  // delete remaining nodes
		 tempPtr = currentPtr;
		 cout << tempPtr->data << '\n';
		 currentPtr = currentPtr->nextPtr;
		 delete tempPtr;

	  } // end while

   } // end if

   cout << "All nodes destroyed\n\n";

} // end List destructor

// insert node at front of list
template< class NODETYPE >
void List< NODETYPE >::insertAtFront( const NODETYPE &value )
{
   ListNode< NODETYPE > *newPtr = getNewNode( value );

   if ( isEmpty() )  // List is empty
	  firstPtr = lastPtr = newPtr;

   else {  // List is not empty
	  newPtr->nextPtr = firstPtr;
	  firstPtr = newPtr;

   } // end else

} // end function insertAtFront

// insert node at back of list
template< class NODETYPE >
void List< NODETYPE >::insertAtBack( const NODETYPE &value )
{
   ListNode< NODETYPE > *newPtr = getNewNode( value );

   if ( isEmpty() )  // List is empty
	  firstPtr = lastPtr = newPtr;

   else {  // List is not empty
	  lastPtr->nextPtr = newPtr;
	  lastPtr = newPtr;

   } // end else

} // end function insertAtBack

// delete node from front of list
template< class NODETYPE >
bool List< NODETYPE >::removeFromFront( NODETYPE &value )
{
   if ( isEmpty() )  // List is empty
	  return false;  // delete unsuccessful

   else {  
	  ListNode< NODETYPE > *tempPtr = firstPtr;

	  if ( firstPtr == lastPtr )
		 firstPtr = lastPtr = 0;
	  else
		 firstPtr = firstPtr->nextPtr;

	  value = tempPtr->data;  // data being removed
	  delete tempPtr;

	  return true;  // delete successful

   } // end else

} // end function removeFromFront

// delete node from back of list
template< class NODETYPE >
bool List< NODETYPE >::removeFromBack( NODETYPE &value )
{
   if ( isEmpty() )
	  return false;  // delete unsuccessful

   else {
	  ListNode< NODETYPE > *tempPtr = lastPtr;

	  if ( firstPtr == lastPtr )
		 firstPtr = lastPtr = 0;
	  else {
		 ListNode< NODETYPE > *currentPtr = firstPtr;

		 // locate second-to-last element
		 while ( currentPtr->nextPtr != lastPtr )
			currentPtr = currentPtr->nextPtr;

		 lastPtr = currentPtr;
		 currentPtr->nextPtr = 0;

	  } // end else

	  value = tempPtr->data;
	  delete tempPtr;

	  return true;  // delete successful

   } // end else

} // end function removeFromBack

// is List empty?
template< class NODETYPE > 
bool List< NODETYPE >::isEmpty() const 
{ 
   return firstPtr == 0; 

} // end function isEmpty

// return pointer to newly allocated node
template< class NODETYPE >
ListNode< NODETYPE > *List< NODETYPE >::getNewNode( 
   const NODETYPE &value )
{
   return new ListNode< NODETYPE >( value );

} // end function getNewNode

// display contents of List
template< class NODETYPE >
void List< NODETYPE >::print() const
{
   if ( isEmpty() ) {
	  cout << "The list is empty\n\n";
	  return;

   } // end if

   ListNode< NODETYPE > *currentPtr = firstPtr;

   cout << "The list is: ";

   while ( currentPtr != 0 ) {
	  cout << currentPtr->data << ' ';
	  currentPtr = currentPtr->nextPtr;

   } // end while

   cout << "\n\n";

} // end function print

#endif

listnode.h

// listnode.h
// Template ListNode class definition.
#ifndef LISTNODE_H
#define LISTNODE_H

// forward declaration of class List 
template< class NODETYPE > class List;  

template< class NODETYPE >
class ListNode {
   friend class List< NODETYPE >; // make List a friend

public:
   ListNode( const NODETYPE & );  // constructor
   NODETYPE getData() const;	  // return data in node

private:
   NODETYPE data;				 // data
   ListNode< NODETYPE > *nextPtr; // next node in list

}; // end class ListNode

// constructor
template< class NODETYPE >
ListNode< NODETYPE >::ListNode( const NODETYPE &info )
   : data( info ), 
	 nextPtr( 0 ) 
{ 
   // empty body

} // end ListNode constructor

// return copy of data in node
template< class NODETYPE >
NODETYPE ListNode< NODETYPE >::getData() const 
{ 
   return data; 

} // end function getData

#endif

main.cpp

// main.cpp
// List class test program.
#include <iostream>

using std::cin;
using std::endl;

#include <string>

using std::string;

#include "list.h"  // List class definition

// function to test a List
template< class T >
void testList( List< T > &listObject, const string &typeName )
{
   cout << "Testing a List of " << typeName << " values\n";

   instructions();  // display instructions

   int choice;
   T value;

   do {
	  cout << "? ";
	  cin >> choice;

	  switch ( choice ) {
		 case 1:
			cout << "Enter " << typeName << ": ";
			cin >> value;
			listObject.insertAtFront( value );
			listObject.print();
			break;

		 case 2:
			cout << "Enter " << typeName << ": ";
			cin >> value;
			listObject.insertAtBack( value );
			listObject.print();
			break;

		 case 3:
			if ( listObject.removeFromFront( value ) )
			   cout << value << " removed from list\n";

			listObject.print();
			break;

		 case 4:
			if ( listObject.removeFromBack( value ) )
			   cout << value << " removed from list\n";

			listObject.print();
			break;

	  } // end switch

   } while ( choice != 5 );  // end do/while

   cout << "End list test\n\n";

} // end function testList

// display program instructions to user
void instructions()
{
   cout << "Enter one of the following:\n"
		<< "  1 to insert at beginning of list\n" 
		<< "  2 to insert at end of list\n" 
		<< "  3 to delete from beginning of list\n" 
		<< "  4 to delete from end of list\n" 
		<< "  5 to end list processing\n";

} // end function instructions

int main()
{
   // test List of int values
   List< int > integerList;
   testList( integerList, "integer" ); 

   // test List of double values
   List< double > doubleList;
   testList( doubleList, "double" ); 

   return 0;

} // end main

مشكور اخي da666ni

ما قصرت والاكواد شويه غريبه على .

هل ممكن شوية توضيح او فكره على المضمون العام .

مع التحيه