صف در ساختمان داده چیست؟ – به زبان ساده

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

نمایی از صف — «برای مشاهده تصویر در اندازه اصلی، روی آن کلیک کنید»

پس به طور خلاصه، صف به ساختار داده‌ای می‌گویند که هر چیزی اول به آن وارد شود، اول نیز از آن خارج می‌شود. در واقع از سیاست «اولین ورود، اولین خروج» (First In, First Out) پیروی می‌کند. در نظریه محاسبات و سیستم‌ها FIFO روشی برای کار با یکی از ساختار‌های داده‌ -به طور خاص، اغلب بافر داده- است. کلمه FIFO سرنامی از اصطلاح First-In-First-Out است. در این روش، قدیمی‌ترین ورودی یا همان اولین ورودی یا داده موجود در انتهای اول صف، اولین داده‌ای است که پردازش می‌شود.

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

چگونه با فرادرس به ساختمان داده مسلط شویم؟

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

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

در ادامه چند مورد از این فیلم‌های آموزشی مربوط به مبحث ساختمان داده را معرفی کرده‌ایم. در صورتی که تمایل به دیدن فیلم‌های بیشتر دارید با کلیک بر روی تصویر بالا یا مراجعه به سایت فرادرس می‌توانید گزینه‌های بسیار بیشتری حتی در رشته‌ها و زمینه‌های دیگری نیز پیدا کنید.

در ادامه مطلب، قبل از اینکه به بررسی جزییات صف بپردازیم باید درباره «پشته» (Stack) صحبت کنیم و این ساختار داده را نیز به خوبی درک کنیم.

پشته (Stack)، صف (Queue) و تجزیه عبارت — ساختار داده و الگوریتم‌ ها

فیلم آموزش ساختمان داده ها و الگوریتم ها در جاوا Java در فرادرس

پشته چیست؟

پشته در ساختمان داده نوعی داده انتزاعی با ظرفیت از پیش تعریف شده است. ساختار داده ساده‌ای که امکان حذف و اضافه عناصر را با ترتیب خاصی فراهم کرده است. هربار که عنصری اضافه یا PUSH می‌شود در «بالای پشته» (TOP) قرار می‌گیرد. تنها عنصری که پشته می‌تواند حذف یا POP کند بالاترین عنصر است. یعنی در واقع عناصر از بالای پشته به ترتیب خارج می‌شوند. این ساختار داده از این لحاظ بر عکس صف عمل می‌کند.

ویژگی های پشته

پشته‌ها دارای چهار ویژگی عمده و برجسته هستند. این ویژگی‌ها را در ادامه به صورت منظم فهرست کرده‌ایم.

هر پشته، فهرست مرتبی از نوع داده‌های شبیه به‌هم است.
پشته‌ها بر اساس روش LIFO پایه‌گذاری شده‌اند. نام روش LIFO سرنام عبارت Last In First Out است. این عبارت به معنای آخرین ورود، اولین خروج، است.
سه عملیات اصلی بر روی هر پشته اجرا می‌شود. تمام این عملیات بر روی بالاترین محل ذخیره‌سازی در حافظه پشته انجام می‌گیرند.
- push() : برای وارد کردن داده به پشته از بالا استفاده می‌شود.
- pop() : برای حذف بالاترین داده در پشته استفاده می‌شود.
- top() : برای فراخوانی بالاترین داده پشته استفاده می‌شود.
پشته پُر باعث ایجاد حالت «سرریز» (Overflow) و پشته خالی باعث ایجاد حالت «زیرریز» (Underflow) می‌شود.

پیاده سازی پشته با استفاده از صف — به زبان ساده

فیلم آموزش ساختمان داده ها و پیاده سازی در سی پلاس پلاس C++‎ در فرادرس

مثال هایی از پیاده سازی پشته در زبان ++C

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

در کد پیاده‌سازی شده پایین، مثال‌های را از روش اجرای عملیات push() و pop() در زبان برنامه نویسی ++C نمایش داده‌ایم.

مثال اول

1# Push Operation
2void Stack::push(int x){
3    if(top >= 10){
4        cout << "Stack Overflow \n" }
5    else{
6        a[++top] = x;
7        cout << "Element Inserted \n";}}

مثال دوم

1# Pop Operation
2int Stack::pop(){
3    if(top < 0){
4        cout << "Stack Underflow \n";
5        return 0;}
6    else{
7        int d = a[top--];
8        return d;}}

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

عملیات خاصی، در ارتباط با صف در ساختمان داده وجود دارند که در ادامه فهرست کرده‌ایم.

فیلم آموزش درهم سازی در ساختمان داده (رایگان) در فرادرس

enqueue(data) : این دستور آیتم جدیدی به انتهای صف اضافه می‌کند. دستور enqueue(data) به چیزی به عنوان پارامتر نیاز دارد، اما چیزی در خروجی برنمی‌گرداند.
isEmpty() : این دستور خالی بودن صف را بررسی می‌کند. دستور isEmpty() به هیچ پارامتر ورودی نیاز ندارد و به عنوان خروجی یک مقدار از نوع بولین برمی‌گرداند.
size() : این دستور تعداد آیتم‌های درون صف را برمی‌گرداند. دستور size() به هیچ پارامتر ورودی نیاز ندارد و به عنوان خروجی مقداری از نوع داده Integer برمی‌گرداند.
dequeue() : این دستور آیتم جلو صف را حذف می‌کند. دستور dequeue() به هیچ پارامتر ورودی نیاز ندارد و در خروجی آیتم حذف شده از جلوی صف را برمی‌گرداند.

یک دختر مهندس در حال کدنویسی است. پنجره دارای تزیینات نورانی است

مثال هایی از عملیات خاص صف به زبان python

در این بخش، برای تمام عملیات توصف شده در بخش قبل با زبان برنامه نویسی python مثالی را کدنویسی کرده‌ایم.

1class Queue:
2  def __init__(self):
3      self.items = []
4  def isEmpty(self):
5      return self.items == []
6  def enqueue(self, item):
7      self.items.insert(0,item)
8  def dequeue(self):
9      return self.items.pop()
10  def size(self):
11      return len(self.items)

عملیات مربوط به صف دو سر | Deque

صف دو سر، نوع خاصی از صف‌ها است که امکان بارگذاری و دریافت داده را از هر دو جهت دارد. این نوع از ساختمان داده تعمیمی از پشته‌ها و صف‌ها است. در واقع صفی است که از هر دو طرف هم امکان حذف عناصر را دارد و هم امکان اضافه کردن عنصر. صف دو سر را «صف با پایان دوگانه» (Double-Ended Queue) یا به صورت خلاصه Deque نیز می‌نامند. در خصوص این نوع از صف‌ها نیز عملیات خاصی وجود دارد که برای استفاده از عناصر درون صف به‌کار می‌روند. عملیات مربوط به صف دو سر در ادامه نمایش داده شده‌اند.

addFront(data) : این تابع، آیتم جدیدی به جلوی صف اضافه می‌کند. دستور addFront(data) به چیزی به عنوان پارامتر دریافتی نیاز دارد، اما در خروجی چیزی برنمی‌گرداند.
addRear(data) : این تابع، آیتم جدیدی به انتهای صف اضافه می‌کند. دستور addRear(data) به چیزی به عنوان پارامتر دریافتی نیاز دارد، اما در خروجی چیزی برنمی‌گرداند.
removeFront() : این تابع، آیتم جلویی صف را حذف می‌کند. دستور removeFront() به چیزی به عنوان پارامتر دریافتی نیاز ندارد و در خروجی آیتم حذف شده از جلوی صف را برمی‌گرداند. بعد از اعمال این تابع، Deque تغییر می‌کند.
removeRear() : این تابع، آیتم انتهایی صف را حذف می‌کند. دستور removeRear() به چیزی به عنوان پارامتر دریافتی نیاز ندارد و در خروجی آیتم حذف شده از انتهای صف را برمی‌گرداند. بعد از اعمال این تابع، Deque تغییر می‌کند.

مثال هایی از عملیات مربوط به Deque به زبان python

در این قسمت از مطلب، برای تمام عملیات مربوط به deque توصف شده در بالا، با استفاده از زبان python، مثال‌هایی را کدنویسی کرده‌ایم.

1class Deque:
2  def __init__(self):
3      self.items = []
4  def addFront(self, item):
5       self.items.append(item)
6  def addRear(self, item):
7       self.items.insert(0,item)
8  def removeFront(self):
9       return self.items.pop()
10  def removeRear(self):
11       return self.items.pop(0)

در تصویر پایین، مقایسه بصری بین Deque، صف و پشته نمایش داده شده است.

«برای مشاهده تصویر در اندازه اصلی، روی آن کلیک کنید»

پیاده سازی صف در ساختمان داده

در بیشتر موارد، دو روش اصلی برای پیاده‌سازی صف وجود دارد. هم پشته‌ها و هم صف‌ها به صورت موثری می‌‌توانند به عنوان آرایه‌های کامپیوتری یا لیست‌های مرتبط باهم پیاده‌سازی شوند. به عملیات پیاده‌سازی آرایه‌های مرتبط با هم «تخصیص متوالی» (Sequential Allocation) و عملیات پیاده‌سازی لیست‌های مرتبط با هم، «تخصیص لیست‌های پیوندی» (Linked List Allocation) می‌گویند. در ادامه هر کدام از موارد ذکر شده را به صورت جداگانه بررسی کرده‌ایم.

Sequential‎ Allocation

تخصیص متوالی یا Sequential Allocation به معنای استفاده کردن از آرایه‌ای برای اختصاص آیتم‌ها به منظور ذخیره‌سازی در صف است.

هر دنباله به خوبی عناصر ابتدا و انتهای خود را تعریف کرده‌ است. هر عنصری در یک دنباله به غیر از اولین عنصر، یک عنصر قبلی دارد و هر عنصری به جز آخرین عنصر، یک عنصر بعدی دارد.

در تصویر بالا آرایه‌ای با نام X داده شده است. می‌توانیم این آرایه را به ترتیب X[1] و X[2] و غیره یا به طور کلی‌تر با X[n] ایندکس‌گذاری کنیم. به صورت منطقی X[0] اولین جایگاه قرارگیری عناصر در آرایه را نشان می‌دهد، X[1] دومین جایگاه، X[2] سومین جایگاه و همین‌طور الی آخر. این روش یکی از رایج‌ترین روش‌های پیاده‌سازی پشته یا صف در ساختمان داده است. البته به شرط اینکه بیشترین اندازه مورد استفاده آرایه از قبل مشخص شده باشد.

مانیتورهای روشن صفحه ادیتور کدنویسی را نشان می‌دهند.

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

Linked List Allocation

برای برنامه‌هایی که با داده‌های بسیار زیادی کار می‌کنند، «لیست‌های پیوندی» (Linked Lists) می‌توانند به عنوان جایگزین مناسبی برای آرایه‌ها در نظر گرفته شوند. نمایش پیوندی صفی با n تعداد عنصر، نیازمند فضای ذخیره‌سازی به اندازه O(n) است. در همین حال، زمان مورد نیاز برای اجرای همچنین عملیاتی برابر با O(1) است.

در صف‌های پیوندی، هر گره شامل ۲ بخش است. بخش مربوط به داده و بخش مربوط به پیوند. هر عنصر در صف به عنصر بعد از خودش در حافظه اشاره می‌کند. روش کلی و اساسی کار لیست‌های پیوند‌ی به این شکل است.

لیست پیوندی - صف در ساختمان داده — «برای مشاهده تصویر در اندازه اصلی، روی آن کلیک کنید»

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

انواع صف در ساختمان داده

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

در مبحث ساختمان داده انواع گوناگونی صف برای نمایش ساختارهای داده‌ای تعریف شده است.

صف های خطی

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

صف های حلقوی

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

صف حلقوی - صف در ساختمان داده — «برای مشاهده تصویر در اندازه اصلی، روی آن کلیک کنید»

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

لیست پیوندی یک طرفه، دو طرفه و حلقوی — ساختمان داده و الگوریتم ها

فیلم آموزش رایگان ساختمان داده ها – سریع و آسان در ۱۲۰ دقیقه در فرادرس

صف های اولویت‌دار

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

اگر عناصری با اولویت یکسان ظاهر شوند، با این عنصٰرها بر اساس قانون FIFO رفتار می‌شود. صف‌های اولویت‌دار با استفاده از Heap پیاده‌سازی می‌شوند. این نوع خاص از صف در موارد فهرست شده زیر به‌کار می‌رود.

زمان‌بندی اجرای پردازش‌ها در CPU
الگوریتم‌های گرافی مانند الگوریتم پیداکردن کوتاه‌ترین مسیر «دایجسترا» (Dijkstra)
همه کاربرد‌های صف‌ که در آن‌ها اولویت اجرا یکی از مسائل مهم بین عناصر صف است.

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

مفاهیم مقیاس پذیری صف در ساختمان داده

مسئله‌ای که باید درک شود این است که چگونه سیستم‌های توزیع شده در مقیاس بزرگ با بخش‌های بسیار زیاد تشکیل دهنده آن‌ها به قابلیت پایداری دست پیدا می‌کنند و چنین مستحکم هستند؟

کلید حل این مسئله «سیستم پردازش غیرهم‌زمانی» (Asynchronous Processing System) است. این سیستم به طور معمول بر روی ابزار بنیادینی به نام «صف پیام» (Message Queue) یا «کارگزار پیام» (Message Broker) ساخته می‌شود.

پردازشگر غیر هم زمان — «برای مشاهده تصویر در اندازه اصلی، روی آن کلیک کنید»

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

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

یکی از اپلیکیشن‌هایی که می‌تواند، پردازش داده‌ها را در مقیاس‌های بزرگ هم از طریق اجرای موازی عملیات، مدیریت کند نرم افزار Apache Kafka است. این نوع از نرم‌افزارها «مدل پیام‌رسانی انتشار-مشترک» (Publish-Subscribe Messaging Model)‌ را پیاده‌سازی می‌کنند.

این مدل پیام‌رسانی به معنی این است که داده‌ها توسط منتشر کننده‌گان ارسال و توسط مشترکین دریافت می‌شود. این مدل برای مدیریت مقادیر بسیار زیاد داده‌های در جریان، طراحی شده است. چنین سیستم مدیریتی برای سامانه‌هایی که باید حجم زیادی از داده را به سرعت پردازش کنند عالی است. این نوع از نرم‌افزارها امکاناتی مانند تلورانس خطا و مقیاس‌پذیری را ارائه می‌دهند. این نرم‌افزار‌ها از نوع «سیستم‌های پردازشی بلادرنگ» (Real-Time DataProcessing System) هستند. نرم‌افزار Apache Kafka گپ‌هایی را برطرف می‌کند که سیستم‌های پیام‌رسان سنتی نمی‌توانستند پُرکنند.

راهنمای نصب آپاچی کافکا (Apache Kafka) روی CentOS 7 — به زبان ساده

فیلم مجموعه آموزش ساختمان داده و طراحی الگوریتم – از دروس دانشگاهی تا کاربردی در فرادرس

آموزش پروژه محور برنامه نویسی و ساختمان داده

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

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

جمع بندی

همین‌طور که به پایان این مطلب از مجله فرادرس می‌رسیم باید نکات مهم این مطلب را جمع‌بندی کنیم. صف، مجموعه منظمی از آیتم‌ها است که ورود به آن از سَمتی به نام انتهای عقب یا دم صف انجام می‌گیرد و خروج از آن از سَمت دیگر صف به نام انتهای جلو یا سر صف بر اساس اصل FIFO انجام می‌گیرد.

کامپیوتر روشن بر روی میز آماده کار کدنویسی است

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