ساختارهای داده برای توسعه‌دهندگان PHP: پشته و صف

ساختار داده‌ یا نوع داده‌ی انتزاعی (ADT)، مدلی است که با مجموعه‌ای از عملگرها با قابلیت انجام عملیات روی همان ساختار و داده‌های ذخیره شده در ساختار (با محدودیت‌هایی که آن عملیات‌ها ایجاد می‌کنند) تعریف شده است. ساختار‌، یک دیوار بین آنچه می‌تواند با داده‌های اصلی انجام دهد و چگونگی انجام آن‌ها می‌کشد. بیشتر ما در زندگی روزمره با مفهوم پشته و صف آشنا هستیم. اما چه چیز سوپرمارکت‌ها، نانوایی‌ها و دستگاه‌های فروش سکه‌ای را مجبور به استفاده از این نوع ساختار داده می‌کند؟ بیایید پیدا کنیم! در این نوشته به شما دو نوع داده‌ی انتزاعی اساسی (صف و پشته) را معرفی می‌کنم که هرکدام از آن‌ها منشأ استفاده‌ی خود را در زندگی روزمره‌ی ما دارند.

پشته (stack)

در زنگی روزمره،‌ یک پشته، توده‌ای از اشیا است که معمولاً به صورت لایه‌لایه چیده شده‌اند. برای مثال،‌ یک پشته از کتاب‌ها روی میز شما، یا بشقاب‌های روی هم گذاشته شده در کابینت آشپزخانه. در علم کامپیوتر، پشته مجموعه‌ای ترتیبی با‌ یک ویژگی خاص است که در آن، آخرین شئ قرارداده شده در پشته، اولین شئ خواهد بود که از آن برداشته می‌شود. این ویژگی معمولاً LIFO (آخرین موردِ افزوده شده، اولین موردی است که خارج می‌شود) نامیده می‌شود.

به‌طور خلاصه،‌ یک پشته‌ یا stack (بخوانید اِستک)، یک لیست خطی از آیتم‌ها است که همه‌ی اضافه کردن‌ها (push) و حذف کردن‌ها (pop) از لیست، به‌ یک سر از لیست محدود شده است. این سر از لیست را بالای پشته (top of stack) می‌نامند. به‌طور مثال در تصویر زیر تعدادی کتاب را مشاهده می‌کنید، اگر این کتاب‌ها را یک پشته درنظر بگیریم، برای رسیدن به کتاب قرمز رنگ، باید از بالا، ابتدا دو کتاب زردرنگ و سپس کتاب نارنجی‌رنگ را برداریم.

پشته‌ای از کتاب‌ها

عملگر‌های اساسی که‌ در یک پشته را تعریف شده است عبارتند از:

init – پشته را می‌سازد.
push –‌یک آیتم را به بالای پشته اضافه می‌کند.
pop – آخرین آیتمی‌ که به پشته اضافه شده باشد را حذف می‌کند.
isEmpty – مشخص می‌کند که آیا پشته دارای آیتم دیگری هست‌ یا خیر.

همچنین‌ یک پشته می‌تواند طوری پیاده‌سازی شود که ظرفیتش محدود باشد. اگر پشته پر شود، و جای کافی برای پذیرش آیتم جدید نداشته باشد، حالتی رخ می‌دهد که به آن سرریز‌ یا overflow گفته می‌شود.

دانستن این‌که پشته با ویژگی LIFO و تعدادی از عملگرهای پایه بخصوصِ push و pop تعریف می‌شود، می‌توانیم به سادگی با استفاده از‌ یک آرایه و توابع آن (array_shift ،array_unshift و empty)‌ یک پشته را پیاده‌سازی کنیم.

مثال زیر‌ یک نمونه‌ی ساده از پشته است:

<?php
class ReadingList
{
    protected $stack;
    protected $limit;
    public function __construct($limit = 10) {
        // initialize the stack
        $this->stack = array();
        // گذاشتن محدودیت در تعداد آیتمها
        $this->limit = $limit;
    }
    public function push($item) {
        // بررسی stack overflow
        if (count($this->stack) < $this->limit) {
            // اضافه کردن آیتم به ابتدای آرایه
            array_unshift($this->stack, $item);
        } else {
            throw new RunTimeException('Stack is full!');
        }
    }
    public function pop() {
        if ($this->isEmpty()) {
            // بررسی stack underflow
          throw new RunTimeException('Stack is empty!');
      } else {
            // برداشتن آیتم از انتهای آرایه
            return array_shift($this->stack);
        }
    }
    public function top() {
        return current($this->stack);
    }
    public function isEmpty() {
        return empty($this->stack);
    }
}

۱۰

۱۱

۱۲

۱۳

۱۴

۱۵

۱۶

۱۷

۱۸

۱۹

۲۰

۲۱

۲۲

۲۳

۲۴

۲۵

۲۶

۲۷

۲۸

۲۹

۳۰

۳۱

۳۲

۳۳

۳۴

۳۵

۳۶

۳۷

۳۸

۳۹

۴۰

۴۱

<?php

class ReadingList

{

protected $stack;

protected $limit;

public function __construct($limit = ۱۰) {

// initialize the stack

$this->stack = array();

// گذاشتن محدودیت در تعداد آیتمها

$this->limit = $limit;

}

public function push($item) {

// بررسی stack overflow

if (count($this->stack) < $this->limit) {

// اضافه کردن آیتم به ابتدای آرایه

array_unshift($this->stack, $item);

} else {

throw new RunTimeException('Stack is full!');

}

public function pop() {

if ($this->isEmpty()) {

// بررسی stack underflow

throw new RunTimeException('Stack is empty!');

} else {

// برداشتن آیتم از انتهای آرایه

return array_shift($this->stack);

}

public function top() {

return current($this->stack);

}

public function isEmpty() {

return empty($this->stack);

}

دراین مثال من از تابع array_shift و array_unshift به‌جای array_push و array_pop طوری استفاده کردم که همیشه نخستین المانِ پشته بالا قرار گیرد. شما می‌توانید برای حفظ انسجامّ معنایی، از array_push و array_pop استفاده کنید که در این صورت n-امین المانِ پشته، المانِ top می‌شود. این مورد تفاوتی در مفهوم و استفاده از پشته ایجاد نمی‌کند.

حال چند آیتم به پشته اضافه می‌کنیم:

<?php
$myBooks = new ReadingList();
$myBooks->push('PHP and MongoDB Web Development');
$myBooks->push('Pro PHP Application Performance');
$myBooks->push('Tomcat The Definitive Guide');
$myBooks->push('Professional Web APIs with PHP');
$myBooks->push('HTML5 Enterprise Application Development');
$myBooks->push('iCloud for Developers');
$myBooks->push('Pro PHP Security');
?>

۱۰

۱۱

<?php

$myBooks = new ReadingList();

$myBooks->push('PHP and MongoDB Web Development');

$myBooks->push('Pro PHP Application Performance');

$myBooks->push('Tomcat The Definitive Guide');

$myBooks->push('Professional Web APIs with PHP');

$myBooks->push('HTML5 Enterprise Application Development');

$myBooks->push('iCloud for Developers');

$myBooks->push('Pro PHP Security');

برای برداشتن آیتم‌ها از پشته به این صورت عمل می‌کنیم:

<?php
echo $myBooks->pop(); //خروجی: Pro PHP Security
echo $myBooks->pop(); //خروجی: iCloud for Developers
echo $myBooks->pop(); //خروجی: HTML5 Enterprise Application Development
?>

<?php

echo $myBooks->pop(); //خروجی: Pro PHP Security

echo $myBooks->pop(); //خروجی: iCloud for Developers

echo $myBooks->pop(); //خروجی: HTML5 Enterprise Application Development

آیتمِ top پشته را اینطور می‌بینیم:

<?php
echo $myBooks->top(); // خروجی:  Professional Web APIs with PHP
?>

<?php

echo $myBooks->top(); // خروجی: Professional Web APIs with PHP

در مثال بالا آیتم top فقط دیده می‌شود و از پشته برداشته نمی‌شود. برای برداشتن آن از پشته به این صورت عمل می‌کنیم:

<?php
echo $myBooks->pop(); //خروجی: Professional Web APIs with PHP
?>

<?php

echo $myBooks->pop(); //خروجی: Professional Web APIs with PHP

اگر pop کردن را تا وقتی که پشته خالی شود ادامه دهیم، با خطای underflow runtime exception روبرو خواهیم شد.، برای رفع این مشکل، به کمک متد empty، عملیات pop کردن از پشته را تا زمانی‌که پشته خالی نشده است ادامه می دهیم.

 <code>PHP Fatal error: Uncaught exception 'RuntimeException' with message 'Stack is empty!' in /home/wdm/Data Structures/code/array_stack.php:33
 Stack trace:
 #۰ /home/wdm/Data Structures/code/example.php(31): ReadingList-&gt;pop()
 #۱ /home/wdm/Data Structures/code/array_stack.php(54): include('/home/wdm/...')
 #۲ {main}
 thrown in /home/wdm/Data Structures/code/array_stack.php on line 33

<code>PHP Fatal error: Uncaught exception 'RuntimeException' with message 'Stack is empty!' in /home/wdm/Data Structures/code/array_stack.php:۳۳

Stack trace:

#۰ /home/wdm/Data Structures/code/example.php(31): ReadingList->pop()

#۱ /home/wdm/Data Structures/code/array_stack.php(54): include('/home/wdm/...')

#۲ {main}

thrown in /home/wdm/Data Structures/code/array_stack.php on line ۳۳

SPLStack

افزونه‌ی SPL مجموعه‌ای از ساختار‌های داده‌ی استاندارد را ارائه می‌دهد که شامل کلاس SplStack (در PHP نسخه ۵.۳.۰ و بالاتر) می‌شود. ما می‌توانیم‌ یک شئ مشابه را، خیلی مختصر و مفیدتر، با استفاده از SplStack پیاده‌سازی کنیم. به مثال زیر دقت کنید:

<?php
class ReadingList extends SplStack
{
}
?>

<?php

class ReadingList extends SplStack

{

}

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

لیست پیوندی که خود‌ یکی دیگر از انواع داده‌ی انتزاعی‌ یا همان ساختار‌های داده است،‌ یک مجموعه‌ی خطی از اشیا (گره‌ها) است که برای نمایش‌ یک دنباله‌ی خاص استفاده شده است. طوری که هر گره‌ یک اشاره‌گر به گره‌ی بعد از خود در مجموعه فراهم کرده است. در ساده‌ترین حالت آن، لیست پیوندی مانند شکل زیر به نظر می‌رسد:

لیست پیوندی

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

لیست پیوندی دوطرفه

گره‌هایی که با علامت ضربدر (x)‌ مشخص شده‌اند، یگ گره‌ی خالی‌ یا نقطه‌ی پایان مسیر عبور را مشخص می‌کنند. هنگامی‌که ReadingList با SplStack پیاده‌سازی شود، می‌توانیم هم رو به جلو (top-down) و هم رو به عقب (bottom-up) از آن عبور کنیم. مسیر پیش‌فرض در SplStack همان LIFO است.

<?php
// top-down traversal
// default traversal mode is SplDoublyLinkedList::IT_MODE_LIFO|SplDoublyLinkedList::IT_MODE_KEEP
foreach ($myBooks as $book) {
    echo $book. "\n"; // prints last item first!
}
?>

<?php

// top-down traversal

// default traversal mode is SplDoublyLinkedList::IT_MODE_LIFO|SplDoublyLinkedList::IT_MODE_KEEP

foreach ($myBooks as $book) {

echo $book. "\n"; // prints last item first!

}

برای عبور از پشته در مسیر برعکس، به سادگی مقدار iterator mode را FIFO ست می‌کنیم.

<?php
// bottom-up traversal
$myBooks->setIteratorMode(
    SplDoublyLinkedList::IT_MODE_FIFO|SplDoublyLinkedList::IT_MODE_KEEP
);
foreach ($myBooks as $book) {
    echo $book. "\n";  // prints first added item first
}
?>

<?php

// bottom-up traversal

$myBooks->setIteratorMode(

SplDoublyLinkedList::IT_MODE_FIFO|SplDoublyLinkedList::IT_MODE_KEEP

);

foreach ($myBooks as $book) {

echo $book. "\n"; // prints first added item first

}

صف‌ها

صف!!!

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

عملگر‌های اساسی که‌ یک صف را تعریف می‌کنند عبارتند از:

Init – صف را می‌سازد
Enqueue –‌ یک آیتم را به انتهای صف (tail) اضافه می‌کند.
Dequeue –‌ یک آیتم را از جلوی صف (head) برمی‌دارد.
isEmpty – نشان می‌دهد که صف آیتمی‌ دارد‌ یا خیر.

از آن‌جایی که SplQueue نیز با‌ یک لیست‌پیوندی دوطرفه پیاده‌سازی شده است، معنای تحت الفظی top و pop برعکس می‌شوند. بیایید ReadingList-مان را این‌بار با صف تعریف کنیم.

همچنین SplDoublyLinkedList اینترفیس ArrayAccess را پیاده‌سازی می‌کند. بنابراین می‌توانید مانند آرایه‌ها آیتم‌هایی را به SplQueue و SplStack اضافه کنید. به مثال زیر دقت کنید:

<?php
$myBooks[] = 'Professional Web APIs with PHP;
$myBooks[] = 'HTML5 Enterprise Application Development';
?>

<?php

$myBooks[] = 'Professional Web APIs with PHP;

$myBooks[] = 'HTML5 Enterprise Application Development';

برای حذف آیتم از ابتدای صف این‌گونه عمل می‌کنیم:

<?php
echo $myBooks->dequeue() . "\n"; // خروجی: 'Professional Web APIs with PHP'
echo $myBooks->dequeue() . "\n"; // خروجی: 'HTML5 Enterprise Application Development'
?>

<?php

echo $myBooks->dequeue() . "\n"; // خروجی: 'Professional Web APIs with PHP'

echo $myBooks->dequeue() . "\n"; // خروجی: 'HTML5 Enterprise Application Development'

متد ()‌enqueue یک نام مستعار برای متد ()push است اما توجه داشته باشید که ()dequeue نام مستعار برای متد ()pop نیست. متد ()pop معنی و عمل‌کرد متفاوتی در مفهوم صف دارد. اگر این‌جا از ()pop استفاده کنیم، ممکن است آیتم انتهای صف را حذف کند که این حالت قانون FIFO را نقض خواهد کرد.

برای اینکه ببینیم چه چیز در ابتدای صف قرار دارد از متد ()buttom بجای ()top استفاده می‌کنیم:

<?php
echo $myBooks->bottom() . "\n";
?>

<?php

echo $myBooks->bottom() . "\n";

خلاصه

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

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

منبع: مجله طراحی وب

ساختارهای داده برای توسعه‌دهندگان PHP: پشته و صف

ترندهای طراحی در وب

آموزش جاوا، بخش ۱۰: نام‌گذاری صحیح متغیرها+برنامه ظرفیت مجاز آسانسور

آموزش جاوا، بخش ۹: پروژه‌ای عملی با عملگرها

مقایسه‌ی SQL و NoSQL- کدام گزینه‌ی بهتری است؟

آموزش جاوا، بخش ۸: عملگرها در زبان برنامه‌نویسی

آموزش جاوا، بخش ۷: یکی از ویژگی‌های کلیدی محیط برنامه‌نویسی

ساختارهای داده برای توسعه‌دهندگان PHP: پشته و صف

پشته (stack)

SPLStack

صف‌ها

خلاصه

دیدگاه خود را بیان کنید لغو پاسخ

پشته (stack)

SPLStack

صف‌ها

خلاصه

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

دیدگاه خود را بیان کنید لغو پاسخ