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

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

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

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

وجه تسمیهٔ پُشته به این خاطر است که این دیتا استراکچر همچون تعدادی بشقاب یا کتاب است که روی یکدیگر به صورت یک پُشته قرار گرفته‌اند؛ آخرین بشقابی/کتابی که روی سایرین قرار می‌گیرد (Last In) همواره اولین بشقابی/کتابی است که در دسترس است (First Out).

وقتی پای استک به میان می‌آید، می‌بایست با دو مفهوم Push و Pop نیز آشنا شویم. به طور کلی، منظور از Push افزودن یک آیتم روی استک مد نظر است و منظور از Pop هم حذف آخرین آیتم افزوده شده به مجموعهٔ آیتم‌ها است.

همچنین در نظر داشته باشیم که برای هر استکی می‌توان یک ماگزیمم ظرفیت در نظر گرفت و این در حالی است که اگر استک دیگر جایی نداشته باشد، از اصطلاح Stack Overflow استفاده می‌شود و چنانچه قصد داشته باشیم آیتمی را از استکی حذف کنیم که خالی است، اصطلاحاً گفته می‌شود Stack Underflow صورت گرفته است. حال برای روشن‌تر شدن مفهوم استک، اسکریپت زیر را مد نظر قرار می‌دهیم:

<?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$ است که به محض ساخت یک آبجکت از روی کلاس، این دو پراپرتی توسط کانستراکتور مقداردهی می‌شوند (برای آشنایی بیشتر با مفهوم کانستراکتور در زبان PHP،‌ به مقالهٔ آشنایی با مفاهیم Constructor و Destructor در PHP به زبان ساده مراجعه نمایید).

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

سپس متدی نوشته‌ایم تحت عنوان ()isEmpty که این وظیفه را دارا است تا چک کند ببیند که آیا آرایهٔ stack$ خالی است یا خیر که این کار را با استفاده از فانکشن از پیش تعریف شدهٔ ()empty در زبان PHP انجام داده‌ایم (به این خاطر stack$ را آرایه خطاب کردیم زیرا از این پس این پراپرتی یک آرایه است).

فانکشن دیگری که در این اسکریپت نوشته‌ایم ()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 در زبان PHP،‌ جدیدترین آیتم افزوده شده به آرایهٔ stack$ را حذف کنیم (کاری که متد ()array_shift انجام می‌دهد این است که اولین آیتم آرایهٔ مد نظر را ابتدا حذف کرده سپس آن را return می‌کند).

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

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

$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('Daybaraye Eli');

همان‌طور که می‌بینیم، نام آبجکت مد نظر (movies$) را نوشته، متد ()push را فراخوانی کرده و به عنوان پارامتر ورودی این متد، استرینگی حاوی نام یک فیلم دلخواه را وارد کرده‌ایم (توجه داشته باشیم با توجه به اینکه Type پارامتر ورودی این متد string است، صرفاً اجازه داریم استرینگ وارد کنیم و در غیر این صورت، با اکسپشن مواجه خواهیم شد). باتوجه به اینکه اندازهٔ در نظر گرفته شده برای پراپرتی 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('Daybaraye 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('Daybaraye Eli');
//$movies->push('Vilayeeha');

echo $movies->pop();

می‌بینیم که مقدار Daybaraye 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('Daybaraye Eli');
//$movies->push('Vilayeeha');

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

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

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

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

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

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

class FavoriteMovieList extends SplStack {} 

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

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

به خاطر داشته باشیم نُودهایی که با علامت X مشخص شده‌اند اصطلاحاً 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('Daybaraye Eli');

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

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

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

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

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

<?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('Daybaraye 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)
    "Daybaraye 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)
    "Daybaraye Eli"
}

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

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

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

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