پیاده سازی پشته در جاوا اسکریپت — از صفر تا صد

ساختار داده «پشته» (Stack) یکی از رایج‌ترین و پرکاربردترین ساختمان داده‌ها در زبان‌های برنامه نویسی محسوب می‌شود. افرادی که به‌تازگی یادگیری زبان برنامه نویسی جاوا اسکریپت را شروع کرده‌اند، با ساختار داده پشته و نحوه پیاده‌سازی و استفاده از آن سروکار خواهند داشت. هدف مقاله حاضر این است که پس از معرفی مختصر ساختار داده پشته و ویژگی‌های آن، به ارائه مثال‌های کاربردی به منظور پیاده‌سازی عملیات مربوط به پشته در جاوا اسکریپت پرداخته شود.

ساختار داده پشته چیست ؟

پشته، ساختار داده‌ای است که مجموعه‌ای از آیتم‌ها را به ترتیب ذخیره می‌کند. پشته به منظور ذخیره‌سازی آیتم‌ها، از اصل «آخرین ورودی-اولین خروجی» (Last In, First Out | LIFO) پیروی می‌کند. به عبارتی، به آیتم آخری که در پشته ذخیره می‌شود، می‌توان زودتر از سایر آیتم‌ها دسترسی داشت و عملیات حذف و اضافه به پشته را فقط از یک سمت این ساختار داده، یعنی از بالای پشته، انجام داد. لغت پشته (Stack) از چیدمان اشیائی روی هم قرار گرفته مثل کتاب‌های روی هم قرار گرفته اقتباس شده است.

.

یکی از ویژگی‌های ساختار داده پشته این است که برخلاف ساختار داده آرایه در برنامه نویسی، در پشته می‌توان انواع مختلفی از داده‌ها را ذخیره کرد. علاوه‌براین، عملیات جستجو در پشته فقط به‌صورت خطی انجام می‌شود و به منظور یافتن مقداری خاص، نمی‌توان در این نوع ساختار داده از روش جستجوی دودویی (باینری) استفاده کرد. همچنین، از یک «اشاره‌گر» (Pointer) در بالای پشته استفاده می‌شود که به آدرس آخرین آیتم درون پشته اشاره دارد و با اضافه کردن یا حذف کردن داده از درون پشته، جایگاه این اشاره‌گر تغییر می‌کند.

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

همچنین، می‌توان از این ساختار داده در برنامه‌های کاربردی مانند ویرایشگرهای متنی، برای انجام عملیات «به حالت قبل برگرداندن» (Undo) استفاده کرد و آخرین تغییرات اعمال شده را یک به یک، به حالت قبل خود تغییر داد. در ادامه، پس از معرفی مجموعه فیلم‌های آموزش جاوا اسکریپت، به نحوه پیاده‌سازی پشته در جاوا اسکریپت به همراه مثال پرداخته می‌شود.

معرفی فیلم های آموزش جاوا اسکریپت

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

• برای دسترسی به همه آموزش های جاوا اسکریپت تم آف + اینجا کلیک کنید.

پیاده سازی پشته در جاوا اسکریپت با چه روشی انجام می‌شود ؟

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

با استفاده از تعریف کلاس یا تابع، می‌توان عملیاتی را برای ساختار داده پشته در جاوا اسکریپت تعریف کرد که در ادامه فهرست شده‌اند:

• عمل Push()‎
• عمل Pop()‎
• عمل Peek()‎
• عمل isFull()‎
• عمل isEmpty()‎
• عمل Clear()‎
• عمل Size()‎

در ادامه، به توضیح عملیات‌ پشته در جاوا اسکریپت به همراه مثال پرداخته می‌شود.

پیاده سازی عملکرد Push ساختار داده پشته در جاوا اسکریپت

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

به منظور پیاده‌سازی عملیات مربوط به پشته در جاوا اسکریپت می‌توان از کلاس استفاده کرد. در قطعه کد زیر، مثالی از تعریف کلاس و یک تابع «سازنده» (Constructor) به منظور تعریف اولیه آرایه مورد نیاز برای پیاده سازی پشته در جاوا اسکریپت آمده است. همچنین، می‌توان از دو متغیر maxlength

 و topIndex

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

// Stack class
class Stack {
  
    // Array is used to implement stack
    constructor()
    {
        this.items = [];
        this.maxlength = maxlength;
        this.topIndex = -1;
    }
  
    // Some Functions to be implemented
    // push(item)
    // pop()
    // peek()
    // isEmpty()
    // printStack()
}

به منظور تعریف متد Push برای پشته در جاوا اسکریپت می‌توان از قطعه کد زیر استفاده کرد. با دستور زیر، داده جدید element

 را می‌توان به بالای پشته اضافه کرد.

// Stack class
class Stack {
  
    // Array is used to implement stack
    constructor()
    {
        this.items = [];
        this.maxlength = maxlength;
        this.topIndex = -1;
    }

    // push function
    push(element)
    {
        // push element into the items
        // if the stack is not full, add a new element to the top of the stack
        if (this.items.length

فیلم آموزش جاوا اسکریپت JavaScript در تم آف

کلیک کنید

پیاده سازی عملکرد Pop ساختار داده پشته در زبان جاوا اسکریپت

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

 شرطی در نظر گرفته شده است که اگر پشته تهی باشد و متد pop()

فراخوانی شود، مقدار Underflow

 را در خروجی برگرداند تا نشان دهد در پشته، آیتمی برای حذف وجود ندارد.

// Stack class
class Stack {
  
    // Array is used to implement stack
    constructor()
    {
        this.items = [];
        this.maxlength = maxlength;
        this.topIndex = -1;
    }

    // pop function
    pop()
    {
        // return top most element in the stack if stack is not empty
        // and removes it from the stack
        // Underflow if stack is empty
        if (this.items.length == 0)
        {
            return "Underflow";
        }
        topIndex--;
        this.maxlength = this.maxlength - 1;
        return this.items.pop();
      
    }
}

پیاده سازی عملکرد Peek ساختار داده پشته در جاوا اسکریپت

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

// Stack class
class Stack {
  
    // Array is used to implement stack
    constructor()
    {
        this.items = [];
        this.maxlength = maxlength;
        this.topIndex = -1;
    }

    // peek function
    peek()
    {
        // return the top most element from the stack
        // but does'nt delete it.
        return this.items[this.items.length - 1];
    }
}

پیاده سازی عملکرد isFull‌ در ساختار داده پشته در زبان جاوا اسکریپت

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

// Stack class 
class Stack {
    // Array is used to implement stack 
    constructor() 
    {
        this.items = [];
        this.maxlength = maxlength; 
        this.topIndex = -1; 
    } 

    // isFull function 
    isFull() 
    { 
        // check whether the stack is full or not
        if (this.items.length==this.maxlength)
        {
             return 'the stack is full!'
        }
        return 'the stack is not full.'
    } 
}

فیلم آموزش رایگان جاوا اسکریپت JavaScript – سریع و آسان در ۱۵۰ دقیقه در تم آف

کلیک کنید

پیاده سازی عملکرد isEmpty ساختار داده پشته در جاوا اسکریپت

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

// Stack class 
class Stack { 
    // Array is used to implement stack 
    constructor() 
    { 
        this.items = [];
        this.maxlength = maxlength; 
        this.topIndex = -1; 
    } 
    // isEmpty function 
    isEmpty() 
    { 
        // return the top most element from the stack // but does'nt delete it. 
        if (this.items.length==0) 
        { 
            return 'the stack is Empty!'
        } 
        return 'the stack is not Empty.' 
    } 
}

پیاده سازی عملکرد Clear ساختار داده پشته در زبان جاوا اسکریپت

با استفاده از تعریف متدی با عنوان Clear‌ می‌توان تمامی آیتم‌های درون پشته را حذف کرد. ساده‌ترین روش برای پاک کردن آیتم‌های درون پشته این است که اشاره‌گر پشته، که به بالاترین آیتم پشته اشاره دارد، با عدد 1- مقداردهی شود. در قطعه کد زیر، نمونه‌ای از این متد در جاوا اسکریپت ملاحظه می‌شود.

// Stack class 
class Stack {
    // Array is used to implement stack 
    constructor() 
    { 
        this.items = [];
        this.maxlength = maxlength; 
        this.topIndex = -1; 
    } 
    
    // Clear function 
    Clear() 
    { 
        // Clear all items. 
        this.topIndex = -1
    } 
}

پیاده سازی عملکرد Size ساختار داده پشته در جاوا اسکریپت

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

// Stack class 
class Stack { 
    // Array is used to implement stack 
    constructor() 
    { 
        this.items = [];
        this.maxlength = maxlength; 
        this.topIndex = -1;  
    } 
    // Size function 
    Size() 
    { 
        // Return the size of the stack
        return this.topIndex 
    } 
}

فیلم آموزش JavaScript ES6 جاوا اسکریپت در تم آف

کلیک کنید

جمع‌بندی

پشته به عنوان یکی از ساختارهای داده رایج در زبان‌های برنامه نویسی به شمار می‌رود که می‌توان آن را با استفاده از ساختار داده‌هایی نظیر آرایه و صف پیاده‌سازی کرد. در مقاله حاضر با عنوان «پیاده سازی پشته در جاوا اسکریپت — از صفر تا صد» به معرفی ویژگی‌ها و کاربرد این ساختار داده و نحوه پیاده‌سازی آن در جاوا اسکریپت با استفاده از آرایه پرداخته شد.