برنامه مسیر ۸ ماهه تا کنکور: مشاوره خصوصیت با استاد رضوی رو رزرو کن!
رزرو مشاوره
کنکور کامپیوتر
0
ورود | ثبت نام
نظرات
اشتراک
بالا
علاقه‌مندی

اشتراک
 

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

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

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

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

پیاده سازی صف

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

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

پیاده سازی صف، عبارت Rear به آخر صف و عبارت Front به جلوی صف اشاره دارد.

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

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

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

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

در وضعیت بالا با این که 2 داده از ابتدای صف حذف شده‌اند اما فقط دو خانه 5 و 6 برای درج وجود دارند چون حرکت 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;

دیده می‌شود که چون 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;

دیده می‌شود که چون 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  خانه های خالی در صف زمانی که Rear از Front بزرگ تر یا مساوی است
خانه‌های صف: n - (Front - Rear) = 5
خانه‌های خالی: Front - Rear = 3
Front $>$ Rear  خانه های خالی در صف زمانی که 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  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)

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

همان‌طور که گفته شد، صف، ساختمان داده‌ای است که عناصر را به روش 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

خروجی کد:

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

Elements dequeued from queue
a
b
c

Queue after removing elements
[]

صف در جاوا

پیاده‌سازی صف در جاواجاوا چیست؟ تعریف، معنی و ویژگی های جاوا (java) از 0تا100جاوا چیست؟ تعریف، معنی و ویژگی های جاوا (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);
  }
}

خروجی کد:

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++ پرداخته و نمونه هایی از کدهای زبان برنامه نویسی ++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;
}

خروجی کد:

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) و متناسب با داده‌ها دارد.

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

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

امتیازدهی4.8333333333333 1 1 1 1 1 1 1 1 1 14.83 امتیاز (3 رای)
اشتراک
بارگذاری نظرات
تلگرام اینستاگرام تماس با پشتیبانی: 09378555200 تماس با پشتیبانی: 09378555200