برنامه نویسی ۵۷ بازدید

ساختار داده «پشته» (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<=this.maxlength)
        {
            this.topIndex++;
            return this.items.push(element);
        }
        //otherwise return a warning message
        return 'the stack is full!'
    }
}

پیاده سازی عملکرد 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.'
    } 
}

پیاده سازی عملکرد 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 
    } 
}

جمع‌بندی

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

اگر این مطلب برای شما مفید بوده است، آموزش‌ها و مطالب زیر نیز به شما پیشنهاد می‌شوند:

بر اساس رای ۹ نفر
آیا این مطلب برای شما مفید بود؟
شما قبلا رای داده‌اید!
اگر بازخوردی درباره این مطلب دارید یا پرسشی دارید که بدون پاسخ مانده است، آن را از طریق بخش نظرات مطرح کنید.

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

نظر شما چیست؟

نشانی ایمیل شما منتشر نخواهد شد.