درآمدی بر ساختمان داده در زبان PHP و آشنایی با مفاهیم Stack و Queue

Data Structure به معنی «ساختمان داده» به روشی برای سازماندهی داده‌ها در حافظهٔ کامپیوتر گفته می‌شود تا در آینده به راحتی و به طور بهینه بتوان به بازیابی داده‌ها پرداخت که برای کسب اطلاعات بیشتر می‌توانید به مقالهٔ الگوریتم و ساختمان داده چیست؟ مراجعه نمایید.

در زبان برنامه‌نویسی پی‌اچ‌پی، بر خلاف برخی از دیگر زبان‌ها همچون جاوا یا سی‌شارپ، آرایه‌ها بسیار انعطاف‌پذیرند و کاربردهای فراوانی دارند که از آن جمله می‌توان به Array ،List ،Hash Table ،Dictionary ،Collection ،Stack ،Queue و حتی Tree اشاره کرد. به گفتهٔ وب‌سایت رسمی PHP، یک آرایه در این زبان در واقع اصطلاحاً یک Ordered Map است که Map در اینجا ساختاری است که داده‌ها را از طریق یکسری Key و Value به یکدیگر مرتبط می‌سازد.

آشنایی با مفهوم Stack
Stack (پُشته) نوعی دیتا استراکچر است و به مجموعه‌ای از چیزها گفته می‌شود که یکی پس از دیگری قرار می‌گیرند که اصطلاحاً به آن Last In, First Out یا LIFO هم گفته می‌شود. به عبارت دیگر، آخرین آیتمی که اضافه می‌شود همواره اولین آیتمی است که در دسترس خواهد بود.

وَجه‌تسمیهٔ پُشته به این خاطر است که این دیتا استراکچر همچون تعدادی بشقاب یا کتاب است که روی یکدیگر به صورت یک پُشته قرار گرفته‌اند و آخرین بشقاب یا کتابی که روی سایرین قرار می‌گیرد (Last In) همواره اولین بشقاب یا کتابی است که در دسترس است (First Out) و وقتی پای اِستک به میان می‌آید، باید با دو مفهوم Push و Pop نیز آشنا شویم. به طور کلی، منظور از Push افزودن یک آیتم روی اِستک مد نظر است و منظور از Pop هم حذف آخرین آیتم افزوده شده به مجموعهٔ آیتم‌ها است. همچنین در نظر داشته باشیم که برای هر اِستکی می‌توان یک ماگزیمم ظرفیت در نظر گرفت و این در حالی است که اگر اِستک دیگر جایی نداشته باشد، از اصطلاح Stack Overflow استفاده می‌شود و چنانچه قصد داشته باشیم آیتمی را از اِستکی حذف کنیم که خالی است، اصطلاحاً گفته می‌شود Stack Underflow صورت گرفته است.

آشنایی با مفهوم Queue
Queue (صَف) نوعی دیتا استراکچر است که اصطلاحاً First In, First Out یا FIFO است. به عبارت دیگر،‌ همچون صف نانوایی یا صف پمپ بنزین، اولین آیتمی (در دنیای واقعی اولین فرد یا خودرو) که به صَف افزوده می‌شود، همواره اولین آیتمی است که قابل دسترسی است.

حال برای روشن‌تر شدن مفهوم اِستک، اسکریپت زیر را که با زبان برنامه‌نویسی PHP نوشته شده است مد نظر قرار می‌دهیم:

<?php
ini_set('display_errors', true);
class FavoriteMovieList
{
    protected $stack;
    protected $limit;

    public function __construct($limit)
    {
        $this->stack = [];
        $this->limit = $limit;
    }

    public function isEmpty()
    {
        return empty($this->stack);
    }

    public function push(string $item)
    {
        if (count($this->stack) < $this->limit) {
            array_unshift($this->stack, $item);
        } else {
            throw new \RunTimeException('Stack is full!');
        }
    }

    public function pop()
    {
        if ($this->isEmpty()) {
            throw new \RunTimeException('Stack is empty!');
        } else {
            return array_shift($this->stack);
        }
    }

    public function top()
    {
        return current($this->stack);
    }
}

در تفسیر اسکریپت فوق می‌توان گفت که در خط دوم دستور داده‌ایم تا کلیهٔ ارورهای مرتبط با این اسکریپت نمایش داده شوند چرا که در حین کار با این اسکریپت، قصد داریم تا عمداً یکسری اِکسپشن ایجاد کنیم و در خط سوم کلاسی تحت عنوان FavoriteMovieList ایجاد کرده‌ایم که حاوی دو پراپرتی تحت عناوین stack$ و limit$ است که به محض ساخت یک آبجکت از روی این کلاس، این دو پراپرتی توسط کانستراکتور مقداردهی می‌شوند (برای آشنایی بیشتر با مفهوم کانستراکتور در زبان پی‌اچ‌پی،‌ به مقالهٔ آشنایی با مفاهیم Constructor و Destructor در PHP مراجعه نمایید.)

داخل کانستراکتور هم مقدار پراپرتی stack$ را برابر با [ ] قرار داده‌ایم که این علائم مترادف با کلیدواژهٔ ()array است که از این پراپرتی یک آرایه می‌سازد و همچنین مقدار پراپرتی limit$ را برابر با پارامتر ورودی کانستراکتور، و بالتبع پارامتر این کلاس در حین ساخت آبجکت، قرار داده‌ایم و سپس متدی نوشته‌ایم تحت عنوان ()isEmpty که این وظیفه را دارا است تا چک کند ببیند که آیا آرایهٔ stack$ خالی است یا خیر که این کار را با استفاده از فانکشن از پیش تعریف شدهٔ ()empty در زبان پی‌اچ‌پی انجام داده‌ایم.

فانکشن دیگری که در این اسکریپت نوشته‌ایم ()push نام دارد و همان‌طور که قبلاً توضیح داده شد، پوش این وظیفه را دارا است تا یک آیتم به آرایه اضافه کند. این فانکشن یک پارامتر ورودی می‌گیرد تحت عنوان item$ و همان‌طور که می‌بینیم، قبل از این پارامتر ورودی هم از کلیدواژهٔ string استفاده کرده‌ایم که به چنین کاری اصطلااحاً Type Hinting گفته می‌شود. در واقع، با آوردن string قبل از نام پارامتر ورودی، این دستور را داده‌ایم که پارامتر ورودی این فانکشن صرفاً باید از جنس اِسترینگ (رشته) باشد و در غیر این صورت با اِکسپشن مواجه خواهیم شد (برای آشنایی بیشتر با مفهوم Type Hinting،‌ به مقالهٔ آشنایی با مفهوم Type Hinting در زبان PHP مراجعه نمایید.)

در خط بیست‌ویکم شرط گذاشته‌ایم که اگر مقدار آرایهٔ stack$ کوچک‌تر از پراپرتی limit$ بود، آیتم مد نظر با استفاده از متد از پیش تعریف شدهٔ ()array_unshift به آرایهٔ stack$ اضافه شود و چنانچه ظرفیت این اِستک پُر بود، وارد دستور else شده و اِکسپشنی حاوی عبارت «!Stack is full» را در معرض دید کاربر قرار دهیم (کاری که متد ()array_unshift انجام می‌دهد این است که یک آیتم به ابتدای آرایهٔ مد نظر اضافه می‌کند.)

متد ()pop هم همان‌طور که از نامش پیدا است، این وظیفه را دارد تا آخرین آیتم افزوده شده به اِستک مد نظر را حذف کند اما برای این منظور در خط سی‌ام یک شرط گذاشته‌ایم که اگر متد ()isEmpty مقدار true را باز گرداند (به عبارت دیگر، چنانچه آرایهٔ stack$ خالی بود)، اِکسپشنی حاوی عبارت «!Stack is empty» نمایش داده شود و در غیر این صورت و با استفاده از متد از پیش تعریف شدهٔ ()array_shift در این زبان،‌ جدیدترین آیتم افزوده شده به آرایهٔ stack$ را حذف کنیم (کاری که متد ()array_shift انجام می‌دهد این است که اولین آیتم آرایهٔ مد نظر را ابتدا حذف کرده سپس آن را ریترن می‌کند.)

در ارتباط با دیتا استراکچر اِستک، منظور از اصطلاح Top این است که آیتمی که روی (بالای) دیگر آیتم‌ها قرار دارد نشان داده شود. برای همین منظور، در پایان هم متدی تعریف کرده‌ایم تحت عنوان ()top که این وظیفه را دارا است تا با استفاده از متد از پیش تعریف شدهٔ ()current در زبان پی‌اچ‌پی، آخرین مقدار افزوده شده به آرایهٔ stack$ را باز گرداند.

حال برای درک بهتر خروجی اسکریپت فوق، خارج از کروشه‌های مرتبط با کلاس FavoriteMovieList آبجکتی تحت عنوان movies$ از روی این کلاس ساخته و به عنوان پارامتر ورودی، عدد 7 را در نظر می‌گیریم:

$movies = new FavoriteMovieList(7);
$movies->push('Gav');
$movies->push('Bemani');
$movies->push('Jodayee Nader Az Simin');
$movies->push('Foroshandeh');
$movies->push('Abado Yek Roz');
$movies->push('Khob, Bad, Jelf');
$movies->push('Darbaraye Eli');

همان‌طور که می‌بینیم، نام آبجکت مد نظر یا به عبارتی movies$ را نوشته، متد ()push را فراخوانی کرده و به عنوان پارامتر ورودی این متد، اِسترینگی حاوی نام یک فیلم دلخواه را وارد کرده‌ایم (توجه داشته باشیم با توجه به اینکه تایپ پارامتر ورودی این متد اِسترینگ است، صرفاً اجازه داریم رشته وارد کنیم و در غیر این صورت، با اِکسپشن مواجه خواهیم شد.) با توجه به اینکه اندازهٔ در نظر گرفته شده برای پراپرتی stack$ برابر با هفت است و در اینجا هم صرفاً هفت بار آیتمی جدید را داخل این آرایه ذخیره کرده‌ایم، اِسکریپت بدون هیچ مشکلی اجرا می‌شود. در ادامه، یک مقدار جدید دیگر به آرایهٔ مد نظر می‌افزاییم:

$movies = new FavoriteMovieList(7);
$movies->push('Gav');
$movies->push('Bemani');
$movies->push('Jodayee Nader Az Simin');
$movies->push('Foroshandeh');
$movies->push('Abado Yek Roz');
$movies->push('Khob, Bad, Jelf');
$movies->push('Darbaraye Eli');
$movies->push('Vilayeeha');

اکنون یک بار اسکریپت را اجرا می‌کنیم:

Uncaught RuntimeException: Stack is full! in /var/www/spl/index.php:25

می‌بینیم با توجه به اینکه ظرفیت آرایهٔ stack$ برابر با هفت است اما قصد داریم تا هشت آیتم را داخل آن جای دهیم، با اِکسپشن نوشته شده داخل متد ()push مواجه می‌شویم. برای ادامهٔ تست این اسکریپت، آخرین خطی که اضافه کردیم را کامنت کرده و کدهای زیر را اضافه می‌نماییم:

$movies = new FavoriteMovieList(7);
$movies->push('Gav');
$movies->push('Bemani');
$movies->push('Jodayee Nader Az Simin');
$movies->push('Foroshandeh');
$movies->push('Abado Yek Roz');
$movies->push('Khob, Bad, Jelf');
$movies->push('Darbaraye Eli');
//$movies->push('Vilayeeha');

echo $movies->pop();

می‌بینیم که مقدار «Darbaraye Eli» نمایش داده می‌شود اما باید توجه داشت که این آیتم از آرایه حذف شده است و برای اثبات صحت این ادعا، اسکریپت زیر را مد نظر قرار می‌دهیم:

$movies = new FavoriteMovieList(7);
$movies->push('Gav');
$movies->push('Bemani');
$movies->push('Jodayee Nader Az Simin');
$movies->push('Foroshandeh');
$movies->push('Abado Yek Roz');
$movies->push('Khob, Bad, Jelf');
$movies->push('Darbaraye Eli');
//$movies->push('Vilayeeha');

$movies->pop();
echo $movies->top();

همان‌طور که می‌بینیم، در خط یازدهم با استفاده از متد ()pop آخرین آیتم قرار گرفته در اِستک را حذف کرده سپس متد ()top را فراخوانی‌ کرده‌ایم که مقدار «Khob, Bad, Jelf» را چاپ می‌کند زیرا پس از «Darbaraye Eli» که در بالاترین جایگاه پُشته قرار داشت و اکنون حذف شده است، اکنون «Khob, Bad, Jelf» در بالاترین جایگاه قرار دارد (در واقع، کاری که فانکشن ()current قرار گرفته داخل ()top انجام می‌دهد این است که مقدار اولین خانهٔ آرایه را باز می‌گرداند.) 

آنچه در بالا دیدیم، ایجاد اِستک به صورت دستی بود و این در حالی است که با استفاده از اِکستنشن SPL زبان پی‌اچ‌پی، به راحتی می‌توان دست به ساخت اِستک زد اما پیش از هر چیز، باید بیشتر با مفهوم این اصطلاح آشنا شویم.

آشنایی با مفهوم SPL
Standard PHP Library یا به اختصار SPL به مجموعه‌ای از کلاس‌ها و اینترفیس‌های توسعه‌یافته برای کار با دیتا استراکچرها در زبان پی‌اچ‌پی گفته می‌شود که به منظور تسهیل فرایند کدنویسی چیزهایی که دولوپرها به صورت روزمره با آن‌ها سروکار دارند مورد استفاده قرار می‌گیرند و به منظور استفاده از SPL نیاز به هیچ‌گونه اِکستنش یا لایبرری خاصی نبوده و از نسخهٔ ۵ زبان پی‌اچ‌پی به بعد، به صورت پیش‌فرض کامپایل شده و در دسترس دولوپرها است (برای کسب اطلاعات بیشتر، به مستندات SPL در سایت رسمی پی‌اچ‌پی مراجعه نمایید.)

اگر بخواهیم اسکریپت فوق را ریفکتور کنیم و ساخت استک را با استفاده از SPL انجام دهیم، خواهیم داشت:

class FavoriteMovieList extends SplStack {} 

همان‌طور که ملاحظه می‌شود، کلیهٔ کدهای داخل این کلاس را پاک کرده و صرفاً دستور داده‌ایم تا کلاس‌مان از کلاس دیفالت در اِکستنشن SPL تحت عنوان SplStack ارث‌بری کند به طوری که دست ما در این نسخه به مراتب بازتر خواهد بود چرا که کلاس SplStack حاوی متدها و به طور کلی قابلیت‌های به مراتب بیش از آن چیزی است که ما برای اِستک خود تعریف کرده بودیم (برای آشنایی بیشتر با قابلیت‌های این کلاس، به صفحهٔ The SplStack Class در وب‌سایت رسمی پی‌اچ‌پی مراجعه نمایید.)

آنچه در کلاس SplStack حائز اهمیت می‌باشد این است که این کلاس خود از کلاس دیگری تحت عنوان SplDoublyLinkedList ارث‌بری می‌کند. به طور کلی، Linked List نوع دیگری از دیتا استراکچرها است که در آن مجموعه‌ای از داده‌ها (نُود) به صورت خطی یکی پس از دیگری قرار گرفته و در آن هر نُود حاوی پوینتر (اشاره‌گر) به نُود بعدی است اما در یک دیتا استراکچر به اصطلاح Doubly-linked List، هر نُود حاوی دو پوینتر است که یکی برای اشاره به نُود قبلی و دیگری برای اشاره به نُود بعدی مورد استفاده قرار می‌گیرد و این نوع دیتا استراکچر به ما امکان گشت‌زنی در هر دو سمت راست و چپ را می‌دهد:

به خاطر داشته باشیم نُودهایی که با علامت ضربدر مشخص شده‌اند اصطلاحاً Null هستند که به نوعی انتهای مسیری که می‌توان به گشت‌زنی در داده‌ها پرداخت را مشخص می‌سازند.

مجدد باز گردیم به کلاس FavoriteMovieList که از کلاس SplStack ارث‌بری کرده است به طوری که ما از این پس امکان این را خواهیم داشت تا این اِستک را از بالا به پایین و از پایین به بالا جستجو کنیم اما در نظر داشته باشیم که رفتار پیش‌فرض کلاس SplStack اصطلاحاً LIFO است که پیش از این با مفهوم آن آشنا شدیم. حال شروع می‌کنیم به افزودن آیتم به اِستک خود:

<?php
ini_set('display_errors', true);

class FavoriteMovieList extends SplStack {} 

$movies = new FavoriteMovieList();
$movies->push('Gav');
$movies->push('Bemani');
$movies->push('Jodayee Nader Az Simin');
$movies->push('Foroshandeh');
$movies->push('Abado Yek Roz');
$movies->push('Khob, Bad, Jelf');
$movies->push('Darbaraye Eli');

همان‌طور که می‌بینیم مجدد آبجکتی تحت عنوان movies$ از روی کلاس FavoriteMovieList ساخته سپس با استفاده از متد از پیش تعریف شدهٔ ()push در کلاس SplStack، اقدام به افزودن نام فیلم‌های مد نظر خود به پُشته می‌کنیم. حال اگر بخواهیم به آیتمی که بالاتر از همه قرار دارد دسترسی پیدا کنیم، صرفاً نیاز است تا متد از پیش تعریف شدهٔ ()top را فراخوانی کنیم:

echo $movies->top(); // prints Darbaraye Eli

می‌بینیم همان‌طور که از رفتار یک اِستک انتظار می‌رود (LIFO)، فیلم «Darbaraye Eli» ریترن می‌شود.

در SPL، کلاس دیگری تعبیه شده تحت عنوان SplQueue که خود این کلاس هم همچون SplStack از کلاس SplDoublyLinkedList ارث‌بری کرده است و به طور کلی این امکان را در اختیار ما قرار می‌دهد تا دست به ایجاد صف بزنیم که برای این منظور، مجدد اسکریپت فوق را ریفکتور کرده و این بار اقدام به ایجاد یک صف می‌کنیم:

<?php
ini_set('display_errors', true);

class FavoriteMovieList extends SplQueue {} 

$movies = new FavoriteMovieList();
$movies->enqueue('Gav');
$movies->enqueue('Bemani');
$movies->enqueue('Jodayee Nader Az Simin');
$movies->enqueue('Foroshandeh');
$movies->enqueue('Abado Yek Roz');
$movies->enqueue('Khob, Bad, Jelf');
$movies->enqueue('Darbaraye Eli');

همان‌طور که می‌بینیم، این بار کلاس FavoriteMovieList از کلاس SplQueue اصطلاحاً extends شده یا «ارث‌بری» کرده است. وقتی هم که پای صَف به میان می‌آید، باید با مفاهیمی همچون Enqueue و Dequeue آشنا شویم که به ترتیب به معنی «افزودن به صَف» و «حذف کردن از صَف» می‌باشند.

در اسکریپت فوق، ما نام هفت فیلم را به صَف مد نظر خود افزوده‌ایم. برای تست کردن ماهیت صَف، ابتدا با استفاده از ()var_dump یک بار آیتم‌های آبجکت movies$ را پرینت کرده،‌ سپس با استفاده از متد از پیش تعریف شدهٔ ()dequeue در کلاس SplQueue اقدام به حذف یک آیتم می‌کنیم و در نهایت مجدد محتویات آرایه را پرینت می‌کنیم (دقت داشته باشیم که با توجه به ماهیت FIFO،‌ وقتی که متد ()dequeue را فراخوانی می‌کنیم، به صورت پیش‌فرض اولین آیتم افزوده شده به صَف که در این مثال فیلم «Gav» است، حذف می‌گردد):

var_dump($movies);
echo $movies->dequeue();
var_dump($movies);

به عنوان خروجی فوق خواهیم داشت:

array(7) {
    [0] =>
    string(3)
    "Gav"[1] =>
    string(6)
    "Bemani"[2] =>
    string(22)
    "Jodayee Nader Az Simin"[3] =>
    string(11)
    "Foroshandeh"[4] =>
    string(13)
    "Abado Yek Roz"[5] =>
    string(15)
    "Khob, Bad, Jelf"[6] =>
    string(13)
    "Darbaraye Eli"
}
Gav
array(6) {
    [0] =>
    string(6)
    "Bemani"[1] =>
    string(22)
    "Jodayee Nader Az Simin"[2] =>
    string(11)
    "Foroshandeh"[3] =>
    string(13)
    "Abado Yek Roz"[4] =>
    string(15)
    "Khob, Bad, Jelf"[5] =>
    string(13)
    "Darbaraye Eli"
}

همان‌طور که می‌بینیم، با دستور ()var_dump اول ابتدا کلیهٔ مقادیر صَف را پرینت کرده‌ایم سپس با استفاده از متد ()dequeue اولین آیتم را حذف کرده سپس مجدداً با دستور ()var_dump دوم مقادیر را پرینت کرده و می‌بینیم که اولین آیتم حذف شده و جای خود را به آیتم دوم داده است و این همان کاری است که قانون FIFO انجام می‌دهد.

جمع‌بندی
انعطاف‌پذیری آرایه‌ها به عنوان یکی از انواع دیتا استراکچرها در زبان PHP این امکان را در اختیار دولوپرها گذاشته که تا حد زیادی بی‌نیاز از دیگر انواع دیتا استراکچر شوند. همچنین ساختمان داده (دیتا استراکچر) در اِکستنشن SPL زبان برنامه‌نویسی پی‌اچ‌پی به مراتب گسترده‌تر از آن چیزی است که در این پست مطرح شد به طوری که در این مجموعه کلاس‌ها ما به دیتا استراکچرهای زیر دسترسی خواهیم داشت:

- SplDoublyLinkedList 
- SplStack
- SplQueue
- SplHeap
- SplMaxHeap
- SplMinHeap
- SplPriorityQueue
- SplFixedArray
- SplObjectStorage

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

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