صف یا Queue یکی از رایجترین ساختارهای داده است که آیتمها را به ترتیب first-in, first-out (FIFO) سازماندهی میکند؛ به این معنا که اولین آیتمی که به صف اضافه میشود، اولین آیتمی است که از آن خارج خواهد شد. در این مقاله با مفهوم صف در تایپ اسکریپت و نحوه پیادهسازی آن با استفاده از لیستهای پیوندی آشنا خواهیم شد.
برای بهرهمندی کامل از این آموزش، داشتن دانش پایه در موارد زیر ضروری است:
برای شروع این آموزش، از یک پروژه آماده استفاده خواهیم کرد که بهطور خاص برای تمرین و پیادهسازی صف طراحی شده است. Repository مربوطه را از GitHub کلون کرده و همزمان با پیشروی در آموزش، کدنویسی را انجام میدهیم.
ساختار پروژه به شکل زیر خواهد بود:
.
├── index.ts
├── examples
│ ├── 01-linked-list.ts
│ ├── 02-simple-queue.ts
│ ├── 03-circular-queue.ts
│ ├── 04-double-ended-queue.ts
│ └── 05-priority-queue.ts
└── playground
├── 01-linked-list.ts
├── 02-simple-queue.ts
├── 03-circular-queue.ts
├── 04-double-ended-queue.ts
└── 05-priority-queue.ts
در طول آموزش، ما از دایرکتوری playground برای پیادهسازی و تست کدهای خود استفاده خواهیم کرد.
دایرکتوری examples شامل نسخه نهایی هر پیادهسازی است. اگر در بخشی از کدنویسی دچار مشکل شدیم، میتوانیم بهعنوان راهحل به این فایلها مراجعه نماییم.
صف یا Queue، یک ساختار داده است که آیتمها را به صورت FIFO مدیریت میکند. یعنی اولین آیتمی که وارد صف میشود، اولین آیتمی است که از آن خارج خواهد شد.
بهعنوان مثال، فرض کنید یک چاپگر در حال پردازش درخواستها است. اگر سه داکیومنت برای چاپ ارسال شود، چاپگر آنها را به ترتیب دریافتشان پردازش میکند: ابتدا داکیومنت اول، سپس داکیومنت دوم و در نهایت داکیومنت سوم چاپ میشود.
در دنیای برنامهنویسی، صفها برای مدیریت وظایفی به کار میروند که نیاز به اجرای ترتیبی دارند؛ برای مثال:
در علم ساختمان داده، چهار نوع اصلی صف وجود دارد:
هر یک از انواع صف دارای مجموعهای از عملیات استاندارد برای مدیریت آیتمها هستند. در این آموزش، با رایجترین و پرکاربردترین عملیاتها آشنا خواهیم شد:
enqueue: افزودن یک آیتم به انتهای صف.dequeue: حذف و بازگرداندن آیتمی که در ابتدای صف قرار دارد.getFront: مشاهده آیتم موجود در ابتدای صف بدون حذف آن.getRear: مشاهده آیتم موجود در انتهای صف بدون حذف آن.isEmpty: بررسی خالی بودن صف.isFull: بررسی پر بودن صف (در صورتی که محدودیت ظرفیت وجود داشته باشد).peek: مشابه getFront عمل میکند و بدون حذف، آیتم ابتدایی را نمایش میدهد.size: بازگرداندن تعداد آیتمهای موجود در صف.اکنون که با مفاهیم صف و عملیاتهای اصلی آن آشنا شدیم، وقت آن است که به سراغ پیادهسازی عملی برویم.
راههای مختلفی برای پیادهسازی صف وجود دارد، اما در این آموزش تمرکز ما بر پیادهسازی صف در تایپ اسکریپت بر پایه لیست پیوندی (Linked List) است.
در گام اول، مروری کوتاه بر ساختار داده لیست پیوندی خواهیم داشت و سپس وارد فاز پیادهسازی صف میشویم.
لیست پیوندی، روشی برای ذخیرهسازی مجموعهای از آیتمهاست که در آن هر آیتم، که «گره» یا Node نامیده میشود، شامل دو بخش است: داده اصلی و ارجاعی به گره بعدی در لیست.
بر خلاف آرایهها که همه المنتها در حافظه بهصورت پشتسرهم قرار دارند، در لیست پیوندی، گرهها با استفاده از این ارجاعها به یکدیگر متصل میشوند؛ درست مثل یک زنجیره.
لیستهای پیوندی یکی از روشهای رایج برای پیادهسازی صفها هستند، زیرا عملیات اضافه کردن در انتها و حذف کردن از ابتدا را بسیار کارآمد انجام میدهند، یعنی دقیقاً همان دو عملیاتی که در صف اهمیت دارند.
در صفهایی که با لیست پیوندی پیادهسازی میشوند، میتوان در زمان ثابت (O(1)) یک گره جدید به انتهای لیست اضافه کرد و یک گره را از ابتدای لیست حذف نمود، بدون نیاز به جابجایی المنتها، برخلاف آنچه در آرایهها لازم است.
در این آموزش، از نوع خاصی از لیست پیوندی استفاده خواهیم کرد به نام لیست پیوندی دایرهای دوطرفه (Circular Doubly Linked List).
لیست پیوندی دایرهای دوطرفه نوعی از لیستهای پیوندی است که در آن هر گره به هر دو گره بعدی و قبلی متصل میشود، و گره انتهایی نیز به گره ابتدایی متصل است تا یک حلقه ایجاد شود.
این ساختار به ما این امکان را میدهد تا در لیست حرکت هم به جلو و هم به عقب کنیم، بدون اینکه به بنبست برسیم. این ویژگی باعث میشود پیمایش در لیست سادهتر باشد و دیگر نیازی به مدیریت حالتهای خاص مانند رسیدن به مقدار null در ابتدا یا انتهای لیست نباشد.
در این نوع ساختار، همه گرهها بهصورت حلقهای به یکدیگر متصلاند که باعث میشود برخی از عملیات صف به شکل مؤثرتری انجام شوند.
لیست پیوندی دایرهای دوطرفه از قبل در فایل src/playground/01-linked-list.ts آماده شده است:
// 📁 src/playground/01-linked-list.ts
/**
* Node for doubly linked list
*/
export class NodeItem<T> {
value: T;
next: NodeItem<T> | null = null;
prev: NodeItem<T> | null = null;
constructor(value: T) {
this.value = value;
}
}
/**
* Circular Doubly Linked List
*/
export class LinkedList<T> {
private head: NodeItem<T> | null = null;
private tail: NodeItem<T> | null = null;
private currentSize: number = 0;
/**
* Add a new node to the front of the list
* @param value The value to add
*/
prepend(value: T): void {
const newNode = new NodeItem(value);
if (this.isEmpty()) {
this.head = newNode;
this.tail = newNode;
newNode.next = newNode;
newNode.prev = newNode;
} else {
newNode.next = this.head;
newNode.prev = this.tail;
this.head!.prev = newNode;
this.tail!.next = newNode;
this.head = newNode;
}
this.currentSize++;
}
/**
* Add a new node to the back of the list
* @param value The value to add
*/
append(value: T): void {
const newNode = new NodeItem(value);
if (this.isEmpty()) {
this.head = newNode;
this.tail = newNode;
newNode.next = newNode;
newNode.prev = newNode;
} else {
newNode.next = this.head;
newNode.prev = this.tail;
this.tail!.next = newNode;
this.head!.prev = newNode;
this.tail = newNode;
}
this.currentSize++;
}
/**
* Remove and return the value from the front of the list
* @returns The value at the head or undefined if empty
*/
deleteHead(): T | undefined {
if (this.isEmpty()) {
return undefined;
}
const value = this.head!.value;
if (this.currentSize === 1) {
this.head = null;
this.tail = null;
} else {
this.head = this.head!.next;
this.head!.prev = this.tail;
this.tail!.next = this.head;
}
this.currentSize--;
return value;
}
/**
* Remove and return the value from the back of the list
* @returns The value at the tail or undefined if empty
*/
deleteTail(): T | undefined {
if (this.isEmpty()) {
return undefined;
}
const value = this.tail!.value;
if (this.currentSize === 1) {
this.head = null;
this.tail = null;
} else {
this.tail = this.tail!.prev;
this.tail!.next = this.head;
this.head!.prev = this.tail;
}
this.currentSize--;
return value;
}
/**
* Get the value at the front without removing it
* @returns The value at the head or undefined if empty
*/
getHead(): T | undefined {
return this.head?.value;
}
/**
* Get the value at the back without removing it
* @returns The value at the tail or undefined if empty
*/
getTail(): T | undefined {
return this.tail?.value;
}
/**
* Check if the list is empty
* @returns True if the list is empty, false otherwise
*/
isEmpty(): boolean {
return this.currentSize === 0;
}
/**
* Get the current size of the list
* @returns The number of nodes in the list
*/
size(): number {
return this.currentSize;
}
}
در این ماژول، یک لیست پیوندی دایرهای دوطرفه با ۸ متد مختلف وجود دارد که در ادامه برای ساخت صف در تایپ اسکریپت از آن استفاده خواهیم کرد:
prepend: افزودن مقدار جدید به ابتدای لیستappend: افزودن مقدار جدید به انتهای لیستdeleteHead: حذف و بازگرداندن مقدار موجود در ابتدای لیستdeleteTail: حذف و بازگرداندن مقدار موجود در انتهای لیستgetHead: مشاهده مقدار ابتدای لیست بدون حذف آنgetTail: مشاهده مقدار انتهای لیست بدون حذف آنisEmpty: بررسی خالی بودن لیستsize: بازگرداندن تعداد آیتمهای موجود در لیستاکنون که لیست پیوندی ما آماده است، ساخت اولین صف خود را شروع میکنیم.
صف ساده پیرو قانون اصلی FIFO است: یعنی آیتمها از انتها به صف اضافه میشوند و از ابتدا خارج میشوند.
برای شروع پیادهسازی، فایل src/playground/02-simple-queue.ts را باز میکنیم. در این فایل، جایگاه اولیهای برای تعریف کلاس SimpleQueue و متدهای آن در نظر گرفته شده است:
// 📁 src/playground/02-simple-queue.ts
import { LinkedList } from "./01-linked-list";
/**
* Simple Queue implemented with a circular doubly linked list
*/
export class SimpleQueue<T> {
private list: LinkedList<T>;
private maxSize?: number;
/**
* @param maxSize Optional maximum size of the queue
*/
constructor(maxSize?: number) {
this.list = new LinkedList<T>();
this.maxSize = maxSize;
}
...methods
}
در هسته کلاس SimpleQueue، ما از لیست پیوندی دایرهای دوطرفه برای نگهداری آیتمها استفاده میکنیم و بهصورت اختیاری میتوانیم یک محدودیت برای اندازه صف نیز تعیین نماییم.
private list: LinkedList<T> در این ویژگی، دادههای صف در تایپ اسکریپت ذخیره میشود. برخلاف استفاده از آرایه، در اینجا از لیست پیوندی سفارشی بهره میگیریم که باعث میشود اضافه یا حذف آیتمها از ابتدا یا انتها بهصورت مؤثر و سریع انجام شود. لیست پیوندی مدیریت ساختار داده را بر عهده دارد تا ما بتوانیم روی منطق صف تمرکز کنیم.private maxSize این ویژگی یک محدودیت اختیاری برای حداکثر تعداد آیتمهایی است که صف میتواند نگه دارد. اگر مقداردهی نشود، صف میتواند به اندازه دلخواه رشد کند.constructor، این متد زمانی اجرا میشود که یک نمونه جدید از صف ایجاد میکنیم. در اینجا یک لیست پیوندی خالی برای نگهداری آیتمهای صف ساخته میشود.اکنون به سراغ پیادهسازی متدهای صف میرویم.
کد ادیتور خود را باز کرده و فایل src/playground/02-simple-queue.ts را با قطعه کد زیر بهروزرسانی میکنیم:
// 📁 src/playground/02-simple-queue.ts
import { LinkedList } from "./01-linked-list";
/**
* Simple Queue implemented with a circular doubly linked list
*/
export class SimpleQueue<T> {
private list: LinkedList<T>;
private maxSize?: number;
/**
* @param maxSize Optional maximum size of the queue
*/
constructor(maxSize?: number) {
this.list = new LinkedList<T>();
this.maxSize = maxSize;
}
/**
* Add an element to the rear of the queue
* @param item The element to add
*/
enqueue(item: T): void {
if (this.isFull()) {
throw new Error("Queue is full");
}
this.list.append(item);
}
/**
* Remove and return the element from the front of the queue
* @returns The element at the front or undefined if empty
*/
dequeue(): T | undefined {
return this.list.deleteHead();
}
/**
* Get the element at the front without removing it
* @returns The element at the front or undefined if empty
*/
getFront(): T | undefined {
return this.list.getHead();
}
/**
* Get the element at the rear without removing it
* @returns The element at the rear or undefined if empty
*/
getRear(): T | undefined {
return this.list.getTail();
}
/**
* Check if the queue is empty
* @returns True if the queue is empty, false otherwise
*/
isEmpty(): boolean {
return this.list.isEmpty();
}
/**
* Check if the queue is full
* @returns True if the queue is full, false otherwise
*/
isFull(): boolean {
return this.maxSize !== undefined && this.list.size() >= this.maxSize;
}
/**
* Peek at the front element without removing it
* @returns The element at the front or undefined if empty
*/
peek(): T | undefined {
return this.getFront();
}
/**
* Get the current size of the queue
* @returns The number of elements in the queue
*/
size(): number {
return this.list.size();
}
}
همانطور که مشاهده میکنیم، استفاده از لیست پیوندی باعث سادهتر شدن پیادهسازی صف میشود، چرا که این لیست نقش هسته اصلی را در ساختار صف ایفا میکند.
در ادامه، عملکرد کلاس SimpleQueue را بررسی میکنیم:
این متد بررسی میکند که آیا صف هیچ آیتمی در خود دارد یا خیر. برای این منظور، متد isEmpty() مربوط به لیست پیوندی فراخوانی میشود که درون خود بررسی میکند آیا اندازه لیست برابر صفر است یا نه. اگر هیچ گرهای در لیست وجود نداشته باشد، مقدار true برمیگردد و به این معناست که صف خالی است. این متد ابزاری پایهای است که اغلب پیش از عملیاتهایی مانند dequeue یا بررسی وضعیت صف استفاده میشود.
این متد بررسی میکند که آیا صف به ظرفیت نهایی خود رسیده است یا خیر. اندازه فعلی لیست پیوندی، از طریق متد size()، با مقدار اختیاری maxSize مقایسه میشود. اگر maxSize تعریف شده باشد و اندازه لیست برابر یا بزرگتر از آن باشد، متد مقدار true بازمیگرداند. این ویژگی در صفهایی با ظرفیت محدود برای جلوگیری از overflow بسیار کاربردی است.
این متد تعداد آیتمهای فعلی موجود در صف را بازمیگرداند. مستقیماً متد size() از لیست پیوندی فراخوانی میشود که تعداد گرههای موجود را رهگیری میکند. این مقدار به ما کمک میکند تا میزان استفاده از صف و ظرفیت باقیمانده را بررسی نماییم.
این متد آیتم جدیدی را به انتهای صف (rear) اضافه میکند. ابتدا با استفاده از isFull() بررسی میشود که آیا صف پر است یا نه. اگر پر باشد، یک خطا دریافت میشود. در غیر این صورت، مقدار جدید با استفاده از متد append() به انتهای لیست پیوندی داخلی افزوده میشود. این عملیات گره جدیدی را به انتهای لیست دایرهای دوطرفه اضافه میکند.
این متد آیتمی که در ابتدای صف قرار دارد را حذف و مقدار آن را بازمیگرداند. با استفاده از متد deleteHead() از لیست پیوندی، گره ابتدایی حذف میشود و ارتباط گرهها برای حفظ ساختار دایرهای بهروزرسانی میگردد. اگر صف خالی باشد، مقدار undefined بازگردانده میشود.
این متد مقدار آیتم موجود در ابتدای صف را بدون حذف آن بازمیگرداند. برای این منظور از متد getHead() در لیست پیوندی استفاده میشود. این عملیات صف را تغییر نمیدهد و برای پیشنمایش آیتم بعدی جهت حذف مفید است.
این متد مقدار آیتم موجود در انتهای صف را بدون حذف آن بازمیگرداند. از متد getTail() استفاده میشود که مقدار گره انتهایی را فراهم میکند. این متد به ما امکان بررسی آخرین آیتم اضافه شده را میدهد بدون آنکه تغییری در صف ایجاد کند.
این متد، در واقع یک نام مستعار برای getFront() است. آیتم ابتدایی صف را بدون حذف آن بازمیگرداند. به صورت داخلی، از متد getFront() استفاده میکند. در بسیاری از APIهای صف، این متد برای بررسی سریع آیتم بعدی رایج است.
ما موفق شدیم اولین صف خود را در تایپ اسکریپت پیادهسازی کنیم.
برای اطمینان از عملکرد صحیح پیادهسازی، دستور زیر را در ترمینال، در root پروژه اجرا کنیم:
npm run test:file 02
اگر هر یک از تستها با خطا مواجه شد، میتوانیم از نسخه نهایی پیادهسازی در مسیر src/examples/02-simple-queue.ts کمک بگیریم، اشکال را برطرف کرده و تستها را دوباره اجرا نماییم.
اگر تمام تستها با موفقیت پشت سر گذاشته شدند، میتوانیم به بخش بعدی برویم، جایی که صف دایرهای را پیادهسازی خواهیم کرد.
CircularQueue نوعی صف با اندازه ثابت است که در آن موقعیت آخر به موقعیت اول متصل میشود. این ویژگی باعث میشود فضای صف بعد از حذف آیتمها دوباره قابل استفاده باشد.
برای درک بهتر، تصور کنید که در یک بوفه، تعداد محدودی بشقاب وجود دارد. وقتی یک بشقاب از جلوی صف برداشته میشود، یک بشقاب جدید در انتها اضافه میشود، اما در همان فضای قبلی.
CircularQueue از لحاظ عملکرد بسیار شبیه SimpleQueue است، اما چند تفاوت کلیدی دارد.
برای شروع، فایل src/playground/03-circular-queue.ts را باز کرده و قطعه کد زیر را به آن اضافه میکنیم:
// 📁 src/playground/03-circular-queue.ts
import { LinkedList } from "./01-linked-list";
/**
* Circular Queue implemented with a circular doubly linked list
*/
export class CircularQueue<T> {
private list: LinkedList<T>;
private maxSize: number;
/**
* @param maxSize Required maximum size of the circular queue
*/
constructor(maxSize: number) {
this.list = new LinkedList<T>();
this.maxSize = maxSize;
}
/**
* Add an element to the rear of the queue
* @param item The element to add
*/
enqueue(item: T): void {
if (this.isFull()) {
throw new Error("Circular queue is full");
}
this.list.append(item);
}
/**
* Remove and return the element from the front of the queue
* @returns The element at the front or undefined if empty
*/
dequeue(): T | undefined {
return this.list.deleteHead();
}
/**
* Get the element at the front without removing it
* @returns The element at the front or undefined if empty
*/
getFront(): T | undefined {
return this.list.getHead();
}
/**
* Get the element at the rear without removing it
* @returns The element at the rear or undefined if empty
*/
getRear(): T | undefined {
return this.list.getTail();
}
/**
* Check if the queue is empty
* @returns True if the queue is empty, false otherwise
*/
isEmpty(): boolean {
return this.list.isEmpty();
}
/**
* Check if the queue is full
* @returns True if the queue is full, false otherwise
*/
isFull(): boolean {
return this.list.size() >= this.maxSize;
}
/**
* Peek at the front element without removing it
* @returns The element at the front or undefined if empty
*/
peek(): T | undefined {
return this.getFront();
}
/**
* Get the current size of the queue
* @returns The number of elements in the queue
*/
size(): number {
return this.list.size();
}
}
در نگاه اول، پیادهسازی CircularQueue ممکن است شبیه SimpleQueue به نظر بیاید، اما چند تفاوت مهم بین این دو وجود دارد:
برخلاف SimpleQueue که مقدار maxSize را به صورت اختیاری دریافت میکند، در CircularQueue این پارامتر اجباری است. این ویژگی، محدودیت سختگیرانهای بر تعداد المنتهای موجود در صف اعمال میکند.
این تفاوت باعث میشود صف دایرهای گزینهای مناسب برای سناریوهایی باشد که نیاز به کنترل حافظه یا منابع وجود دارد، مانند سیستمهای بلادرنگ یا کش کردن دادهها.
این متد از لحاظ عملکرد بسیار شبیه به متد enqueue() در SimpleQueue است، اما از نظر هدف طراحی، تفاوت مهمی دارد. در ircularQueue، پر شدن صف و ارسال خطا، بخشی از قرارداد عملکردی آن محسوب میشود.
ساختار دایرهای بیشتر به صورت مفهومی خود را نشان میدهد: زمانی که صف پر شود، هیچ داده جدیدی نمیتواند وارد شود مگر اینکه آیتمهای قدیمی حذف شوند. این رفتار مشابه یک الگوی بازنویسی دایرهای است، گرچه در این پیادهسازی خاص، بازنویسی خودکار انجام نمیشود.
عملکرد این متد مشابه SimpleQueue است زمانی که maxSize تعریف شده باشد. با این تفاوت که در CircularQueue، مقدار maxSize همیشه تعریف شده و الزامی است. وجود دائمی محدودیت اندازه باعث میشود رفتار صف پیشبینیپذیر و مناسب برای سناریوهای محدود (مانند پردازش دادههای جریانی یا کنترل نرخ) باشد.
پس از پیادهسازی صف دایرهای، زمان آن است که اجرای آن را تست کنیم:
npm run test:file 03
اگر هر کدام از تستها شکست خوردند، میتوانیم از مثال نهایی موجود در دایرکتوری /examples برای دیباگ کردن استفاده کنیم.
در صورتی که همه تستها موفقیتآمیز باشند، آمادهایم که وارد بخش بعدی شویم: Double-Ended Queue یا همان صف دوطرفه.
صف دوطرفه، که به اختصار Deque گفته میشود، ساختاری است که امکان اضافه کردن یا حذف آیتمها از هر دو انتها را فراهم میکند.
برای شروع، فایل src/playground/04-double-ended-queue.ts را باز کرده و کد زیر را به آن اضافه میکنیم:
// 📁 src/playground/04-double-ended-queue.ts
import { LinkedList } from "./01-linked-list";
/**
* Double-Ended Queue (Deque) implemented with a circular doubly linked list
*/
export class Deque<T> {
private list: LinkedList<T>;
private maxSize?: number;
/**
* @param maxSize Optional maximum size of the deque
*/
constructor(maxSize?: number) {
this.list = new LinkedList<T>();
this.maxSize = maxSize;
}
/**
* Add an element to the front of the deque
* @param item The element to add
*/
enqueueFront(item: T): void {
if (this.isFull()) {
throw new Error("Deque is full");
}
this.list.prepend(item);
}
/**
* Add an element to the rear of the deque
* @param item The element to add
*/
enqueueRear(item: T): void {
if (this.isFull()) {
throw new Error("Deque is full");
}
this.list.append(item);
}
/**
* Remove and return the element from the front of the deque
* @returns The element at the front or undefined if empty
*/
dequeueFront(): T | undefined {
return this.list.deleteHead();
}
/**
* Remove and return the element from the rear of the deque
* @returns The element at the rear or undefined if empty
*/
dequeueRear(): T | undefined {
return this.list.deleteTail();
}
/**
* Get the element at the front without removing it
* @returns The element at the front or undefined if empty
*/
getFront(): T | undefined {
return this.list.getHead();
}
/**
* Get the element at the rear without removing it
* @returns The element at the rear or undefined if empty
*/
getRear(): T | undefined {
return this.list.getTail();
}
/**
* Check if the deque is empty
* @returns True if the deque is empty, false otherwise
*/
isEmpty(): boolean {
return this.list.isEmpty();
}
/**
* Check if the deque is full
* @returns True if the deque is full, false otherwise
*/
isFull(): boolean {
return this.maxSize !== undefined && this.list.size() >= this.maxSize;
}
/**
* Peek at the front element without removing it
* @returns The element at the front or undefined if empty
*/
peek(): T | undefined {
return this.getFront();
}
/**
* Get the current size of the deque
* @returns The number of elements in the deque
*/
size(): number {
return this.list.size();
}
}
این متد اجازه میدهد تا المنتی به ابتدای صف اضافه شود، در حالی که SimpleQueue و CircularQueue تنها افزودن به انتها را پشتیبانی میکنند. به صورت داخلی، این کار با فراخوانی list.prepend(item) انجام میشود.
این عملیات صف دوطرفه را برای سناریوهایی مانند سیستمهای Undo/Redo یا برنامهریزهای تسک بسیار کاربردی میسازد.
این متد مشابه enqueue() در SimpleQueue است و با استفاده از list.append(item) آیتمها را به انتهای صف اضافه میکند، اما در Deque، این تنها یکی از دو عملیات متقارن موجود است و کنترل کامل را برای کار با هر دو انتها در اختیار ما میگذارد.
این متد آیتم موجود در ابتدای صف را حذف و بازمیگرداند. از list.deleteHead() استفاده میکند. گرچه از لحاظ عملکرد شبیه به enqueue() در صفهاست، اما نامگذاری آن به وضوح نشان میدهد که در حال کار با ابتدای صف هستیم.
ویژگی منحصربهفرد صف دوطرفه، این متد است که آیتم موجود در انتهای صف را حذف و مقدار آن را بازمیگرداند. برای این کار از list.deleteTail() استفاده میشود.
این متد، مکمل dequeueFront() است و امکان رفتارهای LIFO (مشابه stack) را نیز فراهم میکند.
مانند SimpleQueue، صف دوطرفه نیز میتواند به صورت اختیاری maxSize داشته باشد. این موضوع، امکان پیکربندی منعطف را فراهم میکند:
maxSize تعریف نشده باشد، Deque به صورت بدون محدودیت کار خواهد کرد.maxSize، میتوان Deque را به صورت محدود و کنترل شده اجرا کرد.این در حالی است که در CircularQueue، مقدار maxSize الزامی است.
پس از تکمیل پیادهسازی صف دوطرفه، دستور زیر را برای تست ماژول اجرا میکنیم:
npm run test:file 04
اکنون آمادهایم تا وارد آخرین بخش آموزش، یعنی صف اولویتدار شویم.
یک صف اولویتدار، آیتمها را بر اساس اولویت آنها پردازش میکند، نه بر اساس ترتیب ورود.
آیتمهایی با اولویت بالاتر زودتر حذف میشوند، مانند اورژانس بیمارستان که در آن بیماران با شرایط حاد پیش از سایرین درمان میشوند.
در ادامه فایل src/playground/05-priority-queue.ts را اصلاح خواهیم کرد:
// 📁 src/playground/05-priority-queue.ts
import { LinkedList, NodeItem } from "./01-linked-list";
/**
* Interface for an element with priority
*/
interface PriorityItem<T> {
value: T;
priority: number;
}
/**
* Priority Queue implemented with a circular doubly linked list
*/
export class PriorityQueue<T> {
private list: LinkedList<PriorityItem<T>>;
private maxSize?: number;
/**
* @param maxSize Optional maximum size of the priority queue
*/
constructor(maxSize?: number) {
this.list = new LinkedList<PriorityItem<T>>();
this.maxSize = maxSize;
}
/**
* Add an element to the queue based on its priority
* Higher priority numbers are dequeued first
* @param value The value to add
* @param priority The priority of the value (higher number = higher priority)
*/
enqueue(value: T, priority: number): void {
if (this.isFull()) {
throw new Error("Priority queue is full");
}
const newItem: PriorityItem<T> = { value, priority };
if (this.isEmpty()) {
this.list.prepend(newItem);
return;
}
let current = this.list["head"];
let count = 0;
while (
current &&
current.value.priority >= priority &&
count < this.size()
) {
current = current.next;
count++;
}
if (count === this.size()) {
this.list.append(newItem);
} else {
const newNode = new NodeItem(newItem);
newNode.next = current;
newNode.prev = current!.prev;
if (current!.prev) {
current!.prev.next = newNode;
} else {
this.list["head"] = newNode;
}
current!.prev = newNode;
if (current === this.list["head"]) {
this.list["head"] = newNode;
}
this.list["tail"]!.next = this.list["head"];
this.list["head"]!.prev = this.list["tail"];
this.list["currentSize"]++;
}
}
/**
* Remove and return the element with the highest priority from the queue
* @returns The value with the highest priority or undefined if empty
*/
dequeue(): T | undefined {
return this.list.deleteHead()?.value;
}
/**
* Get the element with the highest priority without removing it
* @returns The value at the front or undefined if empty
*/
getFront(): T | undefined {
return this.list.getHead()?.value;
}
/**
* Get the element with the lowest priority without removing it
* @returns The value at the rear or undefined if empty
*/
getRear(): T | undefined {
return this.list.getTail()?.value;
}
/**
* Check if the queue is empty
* @returns True if the queue is empty, false otherwise
*/
isEmpty(): boolean {
return this.list.isEmpty();
}
/**
* Check if the queue is full
* @returns True if the queue is full, false otherwise
*/
isFull(): boolean {
return this.maxSize !== undefined && this.list.size() >= this.maxSize;
}
/**
* Peek at the element with the highest priority without removing it
* @returns The value at the front or undefined if empty
*/
peek(): T | undefined {
return this.getFront();
}
/**
* Get the current size of the queue
* @returns The number of elements in the queue
*/
size(): number {
return this.list.size();
}
}
این متد یک المنت جدید را بر اساس priority آن به صف اضافه میکند. برخلاف سایر انواع صف که ترتیب بر اساس زمان درج است، در PriorityQueue از یک سازوکار مرتبسازی استفاده میشود که در آن المنتها با مقدار priority بالاتر، در قسمت نزدیکتر به ابتدای صف قرار میگیرند.
این متد، لیست پیوندی را از ابتدای آن پیمایش میکند تا موقعیت مناسب برای درج المنت جدید بهگونهای پیدا شود که ترتیب نزولی اولویتها حفظ شود. سپس بهصورت دستی اشارهگرهای prev و next را تنظیم میکند تا ساختار لیست پیوندی دوطرفه دایرهای حفظ شود. این مرتبسازی حین درج باعث میشود دسترسی به المنت با بالاترین اولویت در مراحل بعدی سریع انجام شود.
این متد، المنتی با بالاترین اولویت را که همیشه در ابتدای صف قرار دارد، حذف و بازمیگرداند. در پشتصحنه، از deleteHead() استفاده میکند و value موجود در گره PriorityItem<T> را برمیگرداند. از آنجا که المنتها هنگام درج مرتب میشوند، این عملیات همواره با کارایی بالا انجام شده و آیتم صحیح را بازیابی میکند.
مقدار موجود در ابتدای صف را بدون حذف آن بازیابی میکند. از آنجا که لیست بهصورت نزولی مرتب شده، این مقدار همواره نشان دهنده آیتم با بالاترین اولویت است.
مقدار انتهای صف را که نشان دهنده آیتم با کمترین اولویت است، بازمیگرداند. برای این کار از getTail() استفاده کرده و value المنت نهایی را استخراج میکند.
بررسی میکند که آیا صف خالی است یا خیر. این بررسی با استفاده از متد isEmpty() موجود در لیست پیوندی انجام میشود.
بررسی میکند که آیا صف به حداکثر ظرفیت مجاز خود رسیده یا خیر. این بررسی از طریق مقایسه اندازه فعلی صف با maxSize (در صورت تعریف شدن) صورت میگیرد.
از نظر عملکرد مشابه getFront() است، اما از نظر معنایی کاربرد روشنتری دارد، مخصوصاً زمانی که بخواهیم آیتم با بیشترین اولویت را، بدون حذف کردن آن، بررسی کنیم.
تعداد کل آیتمهای موجود در صف را بازمیگرداند. این اطلاعات برای نظارت بر ظرفیت یا دیباگکردن مفید است.
صف اولویتدار، برخلاف دیگر انواع صف، ترتیب المنتها را هنگام درج و بر اساس مقدار عددی اولویت آنها مشخص میکند. این ویژگی امکان دسترسی با زمان ثابت به آیتم با بالاترین اولویت را فراهم میسازد، اما باعث میشود عملیات درج به زمان خطی نیاز داشته باشد؛ زیرا باید موقعیت مناسب در لیست مشخص شود.
این نوع صف در تایپ اسکریپت برای مواردی مانند زمانبندی پیشرفته و تعادل بار مناسب است؛ جایی که فوریت یا اهمیت تسکها نسبت به زمان ورود آنها اولویت دارد.
زمانی که پیادهسازی ما به پایان رسید، برای تست کد خود، دستور زیر را اجرا میکنیم:
npm run test:file 05
صفها در سناریوهایی که نیاز به پردازش دادهها یا تسکها به همان ترتیب ورود دارند، بسیار ایدهآل هستند؛ مانند سیستمهای زمانبندی کارها و مدیریت رویدادها. برای مثال، زمانی که چندین فایل چاپی بهطور همزمان به یک پرینتر ارسال میشوند، یک صف میتواند تضمین کند که هر داکیومنت به ترتیب ارسال شدن، چاپ شود.
بهطور مشابه، در سیستمعاملها از صفها برای مدیریت تسکها در مجموعه threadها یا زمانبندی پردازنده (مانند الگوریتم Round Robin) استفاده میشود؛ جایی که حفظ ترتیب اجرا اهمیت بالایی دارد.
همچنین، صفها بهطور گسترده در سیستمهای ارتباطی asynchronous مانند پیامگراهایی نظیر RabbitMQ و Kafka مورد استفاده قرار میگیرند.
در این سیستمها، تولیدکننده و مصرفکننده بهطور مستقل عمل میکنند: تولیدکننده پیامها را وارد صف میکند و مصرفکننده آنها را در زمان مناسب پردازش میکند.
این الگو در معماریهای میکروسرویس یا محیطهای Serverless بسیار کاربردی است؛ جایی که اجزای مختلف یک سامانه باید با با وابستگی حداقلی به یکدیگر و در عین حال با قابلیت مقیاسپذیری بالا عمل کنند.
به همین ترتیب، در سیستمهای بلادرنگ مانند پخش ویدیو یا دریافت داده از حسگرها، صفها کمک میکنند تا دادههای ورودی بافر شوند تا از اتلاف داده جلوگیری شود و پردازش بعدی بهصورت روان و منظم انجام گیرد.
صف در تایپ اسکریپت برای مسائلی که نیاز به دسترسی تصادفی به المنتها، انجام عملیات جستجوی پیچیده یا مرتبسازی پیشرفته دارند، انتخاب مناسبی نیست.
از آنجا که صفها معمولاً تنها اجازه ورود داده از یک سو و خروج داده از سو دیگر را میدهند، در کاربردهایی که نیاز به دسترسی مکرر به المنتهای میانی یا جستجو در کل دادهها وجود دارد، کارایی چندانی ندارند.
در چنین مواردی، استفاده از آرایهها، درختها یا Hash Mapها عملکرد بهتری ارائه میدهد.
استفاده نادرست از صفها میتواند پیچیدگی غیرضروری و گلوگاههای پنهان ایجاد کند. برای نمونه، استفاده کورکورانه از صف میان هر میکروسرویس ممکن است به جداسازی کامپوننتها کمک کند، اما دیباگ کردن و مدیریت خطا را دشوارتر میکند.
همچنین، استفاده بیشازحد و نادرست از صفها میتواند منجر به بروز Backpressure شود؛ وضعیتی که در آن صفها تحت بار سنگین بهسرعت بزرگ شده، تأخیر در پاسخگویی افزایش مییابد و در صورت عدم مدیریت صحیح، ممکن است منجر به Crash شدن یا از کار افتادن سامانه شود.
بنابراین، استفاده از صف در تایپ اسکریپت باید با دقت و آگاهی انجام شود؛ آن هم فقط در شرایطی که ترتیب اجرا، بافرسازی یا پردازش asynchronous واقعاً ضروری است.
صفها یکی از ساختارهای پایهای در مباحث ساختمان داده بهشمار میروند؛ که در شرایطی مانند حفظ ترتیب اجرای تسکها یا پردازش asynchronous، عملکرد بسیار مؤثری از خود نشان میدهند.
صف در تایپ اسکریپت برای مدیریت تسکها، پردازش streaming data و هماهنگی میان سرویسها کاربرد دارد و به اجرای روان و منظم سیستم کمک میکند.
با این حال، صفها برای همه نوع مسئله مناسب نیستند. شناخت دقیق مزایا و محدودیتهای آنها، کلید استفاده درست و بهینه است. در غیر این صورت، ممکن است موجب ایجاد پیچیدگیهای غیرضروری یا مشکلات سیستمی شوند.