برنامه نویسی

صف – جامعه dev

بوها صف یک ساختار داده متداول در برنامه نویسی است. این دقیقاً مانند یک خط از افرادی که منتظر خرید بلیط هستند کار می کند – اولین کسی که به این خط پیوست ، اولین کسی است که خدمت می کند.

این به دنبال اول در ، اول (FIFO) قانون – مورد اضافه شده در ابتدا موردی است که ابتدا بیرون می آید.

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

از نظر برنامه نویسی ، قرار دادن موارد در صف نامیده می شود بررسی، و حذف موارد از صف خوانده می شود چرندبشر

ما می توانیم صف را به هر زبان برنامه نویسی مانند C ، C ++ ، Java ، Python یا C#پیاده سازی کنیم ، اما مشخصات آن تقریباً یکسان است.

عملیات اساسی صف

یک صف یک شی (یک ساختار داده انتزاعی – ADT) است که به عملیات زیر امکان می دهد:

– پرس و جو: یک عنصر را به انتهای صف اضافه کنید
– Dequeue: یک عنصر را از قسمت جلوی صف حذف کنید
– isempty: بررسی کنید که آیا صف خالی است
– isfull: بررسی کنید که آیا صف پر است
– نگاه کردن: بدون حذف آن ، مقدار جلوی صف را دریافت کنید

کار در صف

عملیات صف به شرح زیر است:

  • دو نکته FRONT وت REAR

  • FRONT اولین عنصر صف را پیگیری کنید

  • REAR آخرین عنصر صف را پیگیری کنید

  • در ابتدا ، ارزش را تعیین کنید FRONT وت REAR به -1

عمل جراحی

  • بررسی کنید که آیا صف پر است

  • برای عنصر اول ، مقدار آن را تنظیم کنید FRONT به 0

  • افزایش REAR فهرست توسط 1

  • عنصر جدید را در موقعیتی که به آن اشاره شده اضافه کنید REAR

بینایی

عمل

  • بررسی کنید که آیا صف خالی است

  • مقدار اشاره شده توسط FRONT

  • افزایش FRONT فهرست توسط 1

  • برای آخرین عنصر ، مقادیر آن را مجدداً تنظیم کنید FRONT وت REAR به -1

بینایی

اجرای کد صف:

class Queue {
  constructor(maxSize) {
    this.items = new Array(maxSize);
    this.maxSize = maxSize;
    this.front = -1;
    this.rear = -1;
  }

  isEmpty() {
    return this.front === -1;
  }

  isFull() {
    return this.rear === this.maxSize - 1;
  }

  enqueue(element) {
    if (this.isFull()) {
      throw new Error('Queue is full');
    }
    if (this.front === -1) this.front = 0;
    this.rear += 1;
    this.items[this.rear] = element;
  }

  dequeue() {
    if (this.isEmpty()) {
      return 'Queue is empty';
    }

    const removed = this.items[this.front];

    if (this.front === this.rear) {
      this.front = this.rear = -1;
    } else {
      this.front += 1;
    }

    return removed;
  }

  peek() {
    return this.isEmpty() ? 'Queue is empty' : this.items[this.front];
  }

  print() {
    if (this.isEmpty()) return [];
    return this.items.slice(this.front, this.rear + 1);
  }

  size() {
    return this.isEmpty() ? 0 : this.rear - this.front + 1;
  }

  clear() {
    this.front = this.rear = -1;
  }
}

const queue = new Queue(4);

queue.enqueue(3);
queue.enqueue(5);
queue.enqueue(7);
queue.enqueue(9);

queue.dequeue();

console.log(queue.peek());
console.log(queue.size());
console.log(queue.print());
queue.clear();
console.log(queue.print());


حالت تمام صفحه را وارد کنید

از حالت تمام صفحه خارج شوید

محدودیت های صف

همانطور که در تصویر زیر مشاهده می کنید ، پس از کمی جذابیت و فریب دادن ، اندازه صف کاهش یافته است.

محدودیت بصری

و ما فقط می توانیم شاخص های 0 و 1 را فقط در صورت تنظیم مجدد صف (وقتی همه عناصر از بین رفته اند) اضافه کنیم.

پس از REAR به آخرین شاخص می رسد ، اگر بتوانیم عناصر اضافی را در فضاهای خالی (0 و 1) ذخیره کنیم ، می توانیم از فضاهای خالی استفاده کنیم. این توسط یک صف اصلاح شده به نام صف دایره ای اجرا می شود.

تجزیه و تحلیل پیچیدگی

پیچیدگی زمانی از enqueue در یک صف که با استفاده از یک آرایه اجرا می شود o (1) هنگام قرار دادن در پایان (به عنوان مثال ، استفاده push() در جاوا اسکریپت).
پیچیدگی زمانی از dequeue است ، o (n) هنگام برداشتن از جلو (به عنوان مثال ، استفاده shift()) ، زیرا همه عناصر بعدی باید یک موقعیت را به سمت چپ منتقل کنند.

برنامه های صف (لیست گسترده)

1. برنامه ریزی CPU

  • فرآیندها با استفاده از صف در الگوریتم های مختلف برنامه ریزی مانند FCFS (اولین بار ارائه می شوند) ، رابین گرد و غیره برنامه ریزی شده اند.

2. برنامه ریزی دیسک

  • درخواست های دیسک I/O در صف ها برای بهبود زمان و کارآیی جستجو می شوند.

3. انتقال داده های ناهمزمان (هماهنگ سازی)

  • صف ها به داده های بافر بین فرآیندهای تولید کننده و مصرف کننده کمک می کنند.

  • مثال: بافر I/O ، لوله ها ، پرونده I/O ، جریان.

4. قطع کار در سیستم های زمان واقعی

  • وقفه های سخت افزاری در صف هایی ذخیره می شود که بر اساس اولویت یا زمان ورود به آنها رسیدگی می شود.

5. سیستم های مرکز تماس بگیرید

  • تماس های ورودی به ترتیب دریافت شده در صف و پاسخ داده می شوند.

6. صف چاپ در سیستم عامل ها

  • اسناد متعدد ارسال شده به چاپگر در یک صف نگهداری می شوند و به ترتیب چاپ می شوند.

7. برنامه ریزی کار در سیستم عامل ها

  • وظایفی که منتظر اجرا هستند توسط برنامه ریزی کار در یک صف قرار می گیرند.

8. اولین جستجوی (BFS) در نمودارها

  • BFS از یک صف برای کشف سطح گره ها بر اساس سطح استفاده می کند.

9. صف پیام در سیستم های توزیع شده

  • سیستم هایی مانند RabbitMQ ، Apache Kafka و AWS SQS از صف ها برای مدیریت ارتباطات ناهمزمان بین خدمات استفاده می کنند.

10. برنامه ریزی شغلی در سیستم های دسته ای

  • مشاغل ارسال شده توسط کاربران یک به یک یا به صورت تقسیم وقت صف می شوند و اجرا می شوند.

11. مدیریت بسته شبکه

  • روترها و سوئیچ ها قبل از پردازش و حمل و نقل از صف ها برای ذخیره بسته ها استفاده می کنند.

12. پردازش سفارش در تجارت الکترونیکی

  • سفارشات در یک صف قرار می گیرند و به ترتیب دریافت شده پردازش می شوند.

13. بافر در سرویس های جریان (به عنوان مثال ، YouTube ، Netflix)

  • قبل از اینکه روی صفحه نمایش داده شود ، داده های ویدیویی در صف قرار می گیرند.

14. صف خدمات مشتری

  • بلیط یا درخواست های پشتیبانی به ترتیب FIFO انجام می شود.

15. سیستم های شبیه سازی (به عنوان مثال ، فرودگاه ها ، بانک ها)

  • از صف ها برای شبیه سازی خطوط انتظار برای خدمات استفاده می شود.

16. سیستم های مدیریت ترافیک

  • وسایل نقلیه در سیگنال های ترافیکی یا غرفه های عوارض قبل از اجازه عبور از صف صف بندی می شوند.

نوشته های مشابه

دیدگاهتان را بنویسید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *

دکمه بازگشت به بالا