Stack و Queue

آشنایی با سلسله‌مراتب Queue

Java SE 5 یک رابطه‌ی جدید در Collections Framework معرفی کرد: رابطه‌ی Queue که در Java SE 6 با رابطه‌ی Deque گسترش یافت. رابطه‌ی Queue یک extension از رابطه‌ی Collection است.

[دیاگرام: سلسله‌مراتب رابطه‌ی Queue]

Push، Pop و Peek

ساختارهای Stack و Queue از داده‌ساختارهای کلاسیک در علوم کامپیوتر هستند. Stackها همچنین با نام LIFO Stack شناخته می‌شوند که LIFO مخفف Last In, First Out است. Queueها با نام FIFO شناخته می‌شوند: First In, First Out.

این ساختارها بسیار ساده هستند و سه عملیات اصلی ارائه می‌دهند:

• push(element): یک عنصر به صف یا پشته اضافه می‌کند
• pop(): یک عنصر را از پشته حذف می‌کند (یعنی جدیدترین عنصر اضافه‌شده)
• poll(): یک عنصر را از صف حذف می‌کند (یعنی قدیمی‌ترین عنصر اضافه‌شده)
• peek(): به شما اجازه می‌دهد عنصری که با pop() یا poll() دریافت خواهد شد را ببینید، بدون اینکه از صف یا پشته حذف شود

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

مدل‌سازی صف‌ها و پشته‌ها

Collections Framework دو رابطه برای مدل‌سازی صف‌ها و پشته‌ها ارائه می‌دهد:

• رابطه‌ی Queue یک صف را مدل‌سازی می‌کند
• رابطه‌ی Deque یک صف دوطرفه (Double Ended Queue) را مدل‌سازی می‌کند. می‌توانید عملیات push، pop، poll و peek را هم در انتهای عقب و هم در انتهای جلوی یک Deque انجام دهید و آن را هم صف و هم پشته می‌سازد.

Stackها و Queueها در برنامه‌نویسی همزمان (Concurrent Programming) هم بسیار پرکاربرد هستند. رابطه‌های BlockingQueue، BlockingDeque و TransferQueue در تقاطع Collections Framework و برنامه‌نویسی همزمان قرار دارند که خارج از محدوده‌ی این آموزش است.

هر دو رابطه‌ی Queue و Deque رفتارهایی برای مقابله با دو حالت خاص به این سه عملیات اضافه می‌کنند:

• یک صف ممکن است پر باشد و نتواند عنصر بیشتری بپذیرد
• یک صف ممکن است خالی باشد و نتواند با عملیات pop، poll یا peek عنصری برگرداند

سوال اینجاست: یک پیاده‌سازی در این دو حالت چگونه باید رفتار کند؟

مدل‌سازی صف‌های FIFO با Queue

رابطه‌ی Queue دو روش برای مقابله با این حالت‌های خاص ارائه می‌دهد: پرتاب exception یا برگرداندن یک مقدار خاص.

جدول متدهایی که Queue ارائه می‌دهد:

عملیات	متد	رفتار وقتی صف پر یا خالی است
push	add(element)	خطای IllegalStateException پرتاب می‌کند
	offer(element)	false برمی‌گرداند
poll	remove()	خطای NoSuchElementException پرتاب می‌کند
	poll()	null برمی‌گرداند
peek	element()	خطای NoSuchElementException پرتاب می‌کند
	peek()	null برمی‌گرداند

مدل‌سازی پشته‌های LIFO و صف‌های FIFO با Deque

Java SE 6 رابطه‌ی Deque را به‌عنوان extension رابطه‌ی Queue اضافه کرد. متدهای تعریف‌شده در Queue همچنان در Deque موجود هستند، اما Deque یک قرارداد نام‌گذاری جدید معرفی کرد و متدها طبق این قرارداد جدید duplicated شدند.

جدول متدهای FIFO تعریف‌شده در Deque:

عملیات FIFO	متد	رفتار وقتی صف پر یا خالی است
push	addLast(element)	خطای IllegalStateException پرتاب می‌کند
	offerLast(element)	false برمی‌گرداند
poll	removeFirst()	خطای NoSuchElementException پرتاب می‌کند
	pollFirst()	null برمی‌گرداند
peek	getFirst()	خطای NoSuchElementException پرتاب می‌کند
	peekFirst()	null برمی‌گرداند

و جدول متدهای LIFO تعریف‌شده در Deque:

عملیات LIFO	متد	رفتار وقتی صف پر یا خالی است
push	addFirst(element)	خطای IllegalStateException پرتاب می‌کند
	offerFirst(element)	false برمی‌گرداند
pop	removeFirst()	خطای NoSuchElementException پرتاب می‌کند
	pollFirst()	null برمی‌گرداند
peek	getFirst()	خطای NoSuchElementException پرتاب می‌کند
	peekFirst()	null برمی‌گرداند

قرارداد نام‌گذاری Deque ساده و مشابه رابطه‌ی Queue است. یک تفاوت وجود دارد: عملیات peek در Deque getFirst() و getLast() نام دارند، در حالی که در Queue element() نام دارد.

علاوه بر این، Deque متدهایی را تعریف می‌کند که از آن‌ها انتظار دارید:

• push(element): عنصر را به انتهای جلوی صف دوطرفه اضافه می‌کند. اگر صف نتواند عنصر را بپذیرد، خطای IllegalStateException پرتاب می‌کند.
• pop(): عنصر انتهای جلو را حذف و برمی‌گرداند. اگر عنصری برای حذف وجود نداشته باشد، خطای NoSuchElementException پرتاب می‌کند.
• poll(): همان کار را در انتهای جلوی صف انجام می‌دهد. اگر عنصری وجود نداشته باشد، null برمی‌گرداند.
• peek(): عنصر انتهای جلوی صف را نمایش می‌دهد. اگر عنصری وجود نداشته باشد، null برمی‌گرداند.

پیاده‌سازی Queue و Deque

Collections Framework سه پیاده‌سازی از Queue و Deque (خارج از حوزه‌ی برنامه‌نویسی همزمان) ارائه می‌دهد:

• ArrayDeque: هر دو رابطه را پیاده‌سازی می‌کند. این پیاده‌سازی بر پایه‌ی یک آرایه است. ظرفیت این کلاس به‌صورت خودکار با اضافه شدن عناصر رشد می‌کند. بنابراین همیشه عناصر جدید را می‌پذیرد.
• LinkedList: هر دو رابطه را پیاده‌سازی می‌کند. این پیاده‌سازی بر پایه‌ی یک لیست پیوندی است و دسترسی به اولین و آخرین عنصر بسیار کارآمد است. LinkedList همیشه عناصر جدید را می‌پذیرد.
• PriorityQueue: فقط Queue را پیاده‌سازی می‌کند. این صف بر اساس یک Priority Heap استوار است و عناصرش را بر اساس ترتیب طبیعی یا ترتیب مشخص‌شده توسط Comparator مرتب نگه می‌دارد. سر صف همیشه کمینه‌ی صف نسبت به ترتیب مشخص‌شده است. ظرفیت این کلاس به‌صورت خودکار رشد می‌کند. اضافه کردن اشیایی که رابطه‌ی Comparable را پیاده‌سازی نکرده‌اند خطای ClassCastException پرتاب می‌کند.

دوری از کلاس Stack

شاید استفاده از کلاس Stack ارائه‌شده توسط JDK وسوسه‌انگیز باشد. این کلاس ساده و قابل فهم است و متدهای مورد انتظار push(element)، pop() و peek() را دارد.

اما این کلاس در واقع extends کلاس Vector است. در دوران قبل از معرفی Collections Framework، Vector بهترین انتخاب برای کار با لیست بود. اگرچه Vector deprecated نشده، استفاده از آن توصیه نمی‌شود. همین‌طور استفاده از کلاس Stack.

کلاس Vector Thread Safe است و Stack هم همین‌طور. اگر به Thread Safety نیاز ندارید، می‌توانید به‌راحتی آن را با Deque و ArrayDeque جایگزین کنید. اگر به یک پشته‌ی Thread-Safe نیاز دارید، پیاده‌سازی‌های رابطه‌ی BlockingQueue را بررسی کنید.