صف در ساختمان داده⚡️آموزش صف در ساختمان داده

Q: صف در ساختمان داده چیست؟

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

Q: صف را چگونه پیادهسازی میکنند؟

برای ذخیرهسازی ساختار یک صف میتوان یکی از 2 ساختار زیر را در نظر گرفت: آرایه (Array): که ساختاری ایستا (Static) و محدود دارد. لیست پیوندی (Linked List): که ساختاری پویا (Dynamic) و متناسب با دادهها دارد.

Q: صف حلقوی چیست؟

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

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

هر ساختمان دادهآموزش ساختمان داده و الگوریتمهر ساختمان داده یک نوع فرمت ذخیره‌سازی و مدیریت داده‌ها در کامپیوتر است، که امکان دسترسی و اصلاح کارآمد آن داده‌ها را برای یکسری از الگوریتم‌ها و کاربردها فراهم می‌کند، در این صفحه به بررسی و آموزش ساختمان داده و الگوریتم پرداخته شده است‌ای که در آن عمل درج از یک طرف (انتها = Rear) و عمل حذف (سرویس) از طرف دیگر (ابتدا = Front) انجام شود، صف FIFO (First In First Out) نامیده شده که در بعضی مراجع به آن LILO (Last In Last Out) نیز می‌گویند.

پیاده سازی صف

برای ذخیره‌سازی ساختار یک صف می‌توان یکی از 2 ساختار زیر را در نظر گرفت:

آرایه (Array): که ساختاری ایستا (Static) و محدود دارد.
لیست پیوندی (Linked List): که ساختاری پویا (Dynamic) و متناسب با داده‌ها دارد.

در صورتی که از آرایهآموزش آرایه در ساختمان داده به زبان ساده و از 0 تا 100در این مقاله موارد زیر بررسی شده است : 1- آرایه چیست 2- انواع اندیس گذاری در آرایه 3- انواع آرایه 4- محاسبه آدرس در آرایه 5- محاسبه شماره در آرایه 6- آرایه در برنامه نویسی 7- مزایای استفاده از آرایه n تایی Q[1, ..., n] برای نمایش و ذخیره ساختار یک صف استفاده شود همیشه از دو اشاره‌گر Front و Rear که به‌ترتیب به ابتدا و انتهای صف اشاره می‌کنند استفاده می‌کنیم.

باتوجه به شکل، دیده می‌شود که:

Front: به خانه قبل از خانه اول صف اشاره می‌کند.
Rear: به خانه آخر صف اشاره می‌کند.

حتما بخوانید :

ساختمان داده پشته ⚡️ پشته چیست؟ کاربرد پشته در ساختمان داده

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

هر صف خطی یک آرایه n تایی Q[1, ..., n] است که عناصر از ابتدای صف (Front) حذف شده و به انتهای صف (Rear) اضافه می‌شوند و حرکت عناصر برای درج به سمت جلو است؛ در عین حال عمل حذف نیز خانه‌های خالی در ابتدای آرایه ایجاد می‌کند که با توجه به حرکت عناصر برای درج به سمت جلو، امکان استفاده از این خانه‌ها وجود ندارد. مثال:

صف 6 عضوی روبه‌رو را در نظر بگیرید.
درج عناصر 10، 20، 35، 40
حذف 2 داده (به‌طور عادی داده‌ها از ابتدا حذف می‌شوند.)

در وضعیت بالا با این که 2 داده از ابتدای صف حذف شده‌اند اما فقط دو خانه 5 و 6 برای درج وجود دارند چون حرکت Rear به سمت جلو بوده و امکان استفاده از خانه‌های قبلی را ندارد.

شرایط مرزی و اولیه در صف خطی

در صورتی که:

Front: همیشه به خانه قبل از خانه اول اشاره کند.
Rear: همیشه به خانه آخر صف اشاره کند.

انتخاب آرایه Q[1, ..., n] برای پیاده‌سازی صف خطی دارای شرایط اولیه و مرزی زیر است:

وضعیت اولیه صف	خالی بودن صف خطی	پر بودن صف خطی
Front = Rear = 0	Front = Rear	Rear = n

حتما بخوانید :

کاربرد ساختمان داده ⚡️ کاربرد ساختمان داده در کامپیوتر

عملیات در صف (Queue)

دو عملیات مهم درج و حذف در صف‌ها در ساختمان داده وجود دارد که به ما اجازه اضافه و حذف داده‌ها را در صف‌ها می‌دهد.

درج در صف

procedure insert (var item: data type);
  begin
  if rear = n then
    write ('Queue is Full')
  else
    begin
      rear: = rear + 1;
      Q [rear]: = item;
    end;
  end;

procedure insert (var item: data type);
  begin
  if rear = n then
    write ('Queue is Full')
  else
    begin
      rear: = rear + 1;
      Q [rear]: = item;
    end;
  end;

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

حذف از صف

procedure delete (var item: data type);
  begin
  if front = rear then
    write ('Queue is Empty')
  else
    begin
      front: = front + 1;
      item: = Q [front];
    end;
  end;

procedure delete (var item: data type);
  begin
  if front = rear then
    write ('Queue is Empty')
  else
    begin
      front: = front + 1;
      item: = Q [front];
    end;
  end;

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

مشکل صف‌ خطی

همان‌طور که احتمالاً متوجه شده‌اید، مشکل صف خطی، حرکت تدریجی عناصر به سمت انتهای صف و عدم امکان استفاده از خانه‌های ابتدای صف که در اثر حذف خالی شده‌اند، است.

رفع مشکل صف‌ خطی

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

روش دوم در عمل مقرون به صرفه‌تر بوده و استفاده می‌شود.

حتما بخوانید :

ساختمان داده در پایتون – انواع داده در پایتون

صف حلقوی در ساختمان داده

آرایه n تایی Q[0, ..., n-1] را ‌می‌توان به صورت یک صف حلقوی (Circular Queue) در نظر گرفت به‌طوری که در این صف زمانی‌که Rear برابر n-1 می‌شود، عنصر بعدی در خانه قرار می‌گیرد.

نمایش اول
	\[{{\stackrel{درج\mathrm{\ 50}}{\Longrightarrow}}}\]

نمایش دوم
	\[{{\stackrel{درج\mathrm{\ 50}}{\Longrightarrow}}}\]

شرایط مرزی در صف حلقوی

خالی (Empty)	پر (Full)
Front = Rear	Front = (Rear + 1) Mod n

تعداد خانه‌های قابل استفاده در صف حلقوی

در هر صف حلقوی Q[0, ..., n-1] با ظرفیت n، همیشه یک خانه باید خالی باشد و حداکثر از n-1 خانه صف می‌توان استفاده کرد. این به آن علت است که بتوان وضعیت پر یا خالی بودن صف حلقوی را تشخیص داد. توجه داشته باشید در صورتی‌که در یک صف حلقوی Q[0, ..., n-1] با ظرفیت n از همه خانه‌های صف استفاده کنیم و یک خانه را خالی نگذاریم، وضعیت پر یا خالی بودن صف حلقوی قابل تشخیص نخواهد بود.

صف حلقوی غیر استاندارد به دلیل پر شدن تمامی خانه های آن

\[{{\stackrel{درج\mathrm{\ 80}}{\Longrightarrow}}}\]

در مثال قبل بعد از درج 80 در صف حلقوی و استفاده از همان یک خانه‌ای که باید در صف خالی می‌ماند، Front = Rear = 7 می‌شود که همان شرط خالی بودن صف است، در صورتی‌که صف پر شده و این یک تناقض است. برای نبودن تناقض فوق و امکان تشخیص وضعیت پر یا خالی بودن صف حلقوی، یک خانه را خالی نگه می‌داریم.

تعداد خانه‌های پر و خالی یک صف حلقوی با ظرفیت n

الف) Front به قبل از اول صف اشاره می‌کند:

ردیف	وضعیت	تعداد خانه‌های صف	تعداد خانه‌های خالی
1	\[\mathrm{Rear\ }\mathrm{\ge }\mathrm{\ Front}\]	Rear - Front	n - (Rear - Front)
2	\[\mathrm{Rear\ <\ Front}\]	n - (Front - Rear)	Front - Rear

تبصره: رابطه (Rear - Front) - n را می‌توان به‌صورت (Front - Rear) + n نوشت.

مثال: برای یک صف حلقوی زیر با ظرفیت n=8 همواره داریم:

خانه‌های صف: Rear - Front = 5 خانه‌های خالی: n - (Rear - Front) = 3	Rear $\ge$ Front
خانه‌های صف: n - (Front - Rear) = 5 خانه‌های خالی: Front - Rear = 3	Front $>$ Rear

ب) Front به اول صف اشاره می‌کند:

ردیف	وضعیت	تعداد خانه‌های صف	تعداد خانه‌های خالی
1	Rear $\ge$ Front	Rear - Front + 1	n - (Rear - Front + 1)
2	Front $>$ Rear	n - (Front - Rear - 1)	Front - Rear - 1

عملیات در صف حلقوی

درج در صف حلقوی

procedure  Addqueue  (item : type);
  begin
  if (rear + 1) mod n = front then
    write ('Queue is Full')
  else
    begin
      rear : = (rear + 1) mod n;
      Q [rear]: = item;
    end;
  end;

procedure  Addqueue  (item : type);
  begin
  if (rear + 1) mod n = front then
    write ('Queue is Full')
  else
    begin
      rear : = (rear + 1) mod n;
      Q [rear]: = item;
    end;
  end;

حذف از صف حلقوی

Procedure  delqueue (item : type);
  begin
  if front = rear then
    write('Queue is Empty')
  else
    begin
    front : = (front + 1) mod n;
    item : = Q [front];
    end;
  end;

Procedure  delqueue (item : type);
  begin
  if front = rear then
    write('Queue is Empty')
  else
    begin
    front : = (front + 1) mod n;
    item : = Q [front];
    end;
  end;

در هر دو روش حذف و درج به ترتیب از جملات front: = (front + 1) mod n و rear: = (rear + 1) mod n استفاده شده است که علت استفاده از mod در شرایطی است که front یا rear به خانه آخر اشاره کرده باشند و حرکت به جلو، آن‌ها را به ابتدای صف منتقل می‌کند.

حتما بخوانید :

تفاوت ساختمان داده های خطی و غیرخطی

کاربردهای صف (Queue)

صف پردازش‌های سیستم عاملسیستم عامل چیست به زبان ساده، چرا باید از OS استفاده کنیم؟این مقاله عالی به معرفی سیستم عامل (Operating System|OS) به زبان ساده پرداخته، همچنین بررسی کرده که چرا باید از سیستم عامل استفاده کنیم
صف چاپگر
پیمایش BFS = Breath First Search (سطحی، ردیفی، پهنا) در درخت و گرافگراف چیست، آموزش گراف از 0 تا 100 توسط دانشجو ارشد صنعتی شریفدر این مقاله تمامی مطالب مربوط به گراف از 0 تا 100 تدریس شده است. مواردی همچون : گراف چیست؟ انواع گراف، گراف همبند، مکمل گراف،‌ گراف کامل، گراف جهت دار، گراف بدون جهت،‌ گراف ساده و ...

صف در برنامه نویسی

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

صف در پایتون

راه‌های مختلفی برای پیاده‌سازی صف در پایتونزبان برنامه نویسی پایتون چیست؟ – نحوه شروع و دلایل محبوبیتزبان برنامه نویسی پایتون (Python) چیست؟ این مقاله عالی به بررسی دلایل محبوبیت پایتون، موارد استفاده از پایتون و نحوه شروع به برنامه نویسی پایتون پرداخته وجود دارد. یکی از روش‌ها با استفاده از متد List است که در این مقاله به آن می‌پردازیم. به‌منظور آشنایی بیشتر با دیگر روش‌های پیاده‌سازی صف در پایتون می‌توانید به سایت geeksforgeeks مراجعه کنید.

# Python program to
# demonstrate queue implementation
# using list

# Initializing a queue
queue = []

# Adding elements to the queue
queue.append('a')
queue.append('b')
queue.append('c')

print("Initial queue")
print(queue)

# Removing elements from the queue
print("\nElements dequeued from queue")
print(queue.pop(0))
print(queue.pop(0))
print(queue.pop(0))

print("\nQueue after removing elements")
print(queue)

# Uncommenting print(queue.pop(0))
# will raise and IndexError
# as the queue is now empty

# Python program to
# demonstrate queue implementation
# using list

# Initializing a queue
queue = []

# Adding elements to the queue
queue.append('a')
queue.append('b')
queue.append('c')

print("Initial queue")
print(queue)

# Removing elements from the queue
print("\nElements dequeued from queue")
print(queue.pop(0))
print(queue.pop(0))
print(queue.pop(0))

print("\nQueue after removing elements")
print(queue)

# Uncommenting print(queue.pop(0))
# will raise and IndexError
# as the queue is now empty

خروجی کد:

Initial queue
['a', 'b', 'c']

Elements dequeued from queue
a
b
c

Queue after removing elements
[]

صف در جاوا

پیاده‌سازی صف در جاواجاوا چیست؟ تعریف، معنی و ویژگی های جاوا (java) از 0تا100جاوا یک زبان برنامه نویسی همه منظوره، مبتنی بر کلاس و شی گرا است که برای داشتن وابستگی های پیاده سازی کمتر طراحی شده است، زبان برنامه نویسی جاوا شبیه ++C است به‌صورت زیر است:

// Java program to demonstrate a Queue

import java.util.LinkedList;
import java.util.Queue;

public class QueueExample {

  public static void main(String[] args)
  {
    Queue<integer> q
    = new LinkedList<>();

    // Adds elements {0, 1, 2, 3, 4} to
    // the queue
	for (int i = 0; i < 5; i++)
      q.add(i);

    // Display contents of the queue.
    System.out.println("Elements of queue "
            + q);

    // To remove the head of queue.
    int removedele = q.remove();
    System.out.println("removed element-"
            + removedele);

    System.out.println(q);

    // To view the head of queue
    int head = q.peek();
    System.out.println("head of queue-"
            + head);

    // Rest all methods of collection
    // interface like size and contains
    // can be used with this
    // implementation.
    int size = q.size();
    System.out.println("Size of queue-"
            + size);
  }
}

// Java program to demonstrate a Queue

import java.util.LinkedList;
import java.util.Queue;

public class QueueExample {

  public static void main(String[] args)
  {
    Queue<integer> q
    = new LinkedList<>();

    // Adds elements {0, 1, 2, 3, 4} to
    // the queue
	for (int i = 0; i < 5; i++)
      q.add(i);

    // Display contents of the queue.
    System.out.println("Elements of queue "
            + q);

    // To remove the head of queue.
    int removedele = q.remove();
    System.out.println("removed element-"
            + removedele);

    System.out.println(q);

    // To view the head of queue
    int head = q.peek();
    System.out.println("head of queue-"
            + head);

    // Rest all methods of collection
    // interface like size and contains
    // can be used with this
    // implementation.
    int size = q.size();
    System.out.println("Size of queue-"
            + size);
  }
}

خروجی کد:

Elements of queue [0, 1, 2, 3, 4]
removed element-0
[1, 2, 3, 4]
head of queue-1
Size of queue-4

صف در ++C

پیاده‌سازی صف در زبان C++‎برنامه نویسی سی پلاس پلاس چیست؟ مزایای برنامه نویسی C++‎؟برنامه نویسی سی پلاس پلاس چیست و چه کاربردی دارد؟ این صفحه عالی به بررسی مزایای برنامه نویسی C++ پرداخته و نمونه هایی از کدهای زبان برنامه نویسی ++C را آورده به‌صورت زیر است:

// CPP code to illustrate Queue in
// Standard Template Library (STL)
#include <iostream>
#include <queue>

using namespace std;

// Print the queue
void showq(queue<int> gq)
{
  queue<int> g = gq;
  while (!g.empty()) {
    cout << '\t' << g.front();
    g.pop();
  }
  cout << '\n';
}

// Driver Code
int main()
{
  queue<int> gquiz;
  gquiz.push(10);
  gquiz.push(20);
  gquiz.push(30);

  cout << "The queue gquiz is : ";
  showq(gquiz);

  cout << "\ngquiz.size() : " << gquiz.size();
  cout << "\ngquiz.front() : " << gquiz.front();
  cout << "\ngquiz.back() : " << gquiz.back();

  cout << "\ngquiz.pop() : ";
  gquiz.pop();
  showq(gquiz);

  return 0;
}

// CPP code to illustrate Queue in
// Standard Template Library (STL)
#include <iostream>
#include <queue>

using namespace std;

// Print the queue
void showq(queue<int> gq)
{
  queue<int> g = gq;
  while (!g.empty()) {
    cout << '\t' << g.front();
    g.pop();
  }
  cout << '\n';
}

// Driver Code
int main()
{
  queue<int> gquiz;
  gquiz.push(10);
  gquiz.push(20);
  gquiz.push(30);

  cout << "The queue gquiz is : ";
  showq(gquiz);

  cout << "\ngquiz.size() : " << gquiz.size();
  cout << "\ngquiz.front() : " << gquiz.front();
  cout << "\ngquiz.back() : " << gquiz.back();

  cout << "\ngquiz.pop() : ";
  gquiz.pop();
  showq(gquiz);

  return 0;
}

خروجی کد:

The queue gquiz is :     10    20    30

gquiz.size() : 3
gquiz.front() : 10
gquiz.back() : 30
gquiz.pop() :     20    30

جمع‌بندی

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

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

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

صف را چگونه پیاده‌سازی می‌کنند؟

برای ذخیره‌سازی ساختار یک صف می‌توان یکی از 2 ساختار زیر را در نظر گرفت:
آرایه (Array): که ساختاری ایستا (Static) و محدود دارد.
لیست پیوندی (Linked List): که ساختاری پویا (Dynamic) و متناسب با داده‌ها دارد.