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

۳۸۳ بازدید
آخرین به‌روزرسانی: ۲۷ اردیبهشت ۱۴۰۲
زمان مطالعه: ۶ دقیقه
پیاده سازی پشته در جاوا اسکریپت — از صفر تا صد

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

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

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

.

مثال ساختار داده پشته در جاوا اسکریپت

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

اشاره گر در پشته

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

پشته در جاوا اسکریپت

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

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

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

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

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

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

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

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

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

 

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

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

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

1// Stack class
2class Stack {
3  
4    // Array is used to implement stack
5    constructor()
6    {
7        this.items = [];
8        this.maxlength = maxlength;
9        this.topIndex = -1;
10    }
11  
12    // Some Functions to be implemented
13    // push(item)
14    // pop()
15    // peek()
16    // isEmpty()
17    // printStack()
18}

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

1// Stack class
2class Stack {
3  
4    // Array is used to implement stack
5    constructor()
6    {
7        this.items = [];
8        this.maxlength = maxlength;
9        this.topIndex = -1;
10    }
11
12    // push function
13    push(element)
14    {
15        // push element into the items
16        // if the stack is not full, add a new element to the top of the stack
17        if (this.items.length<=this.maxlength)
18        {
19            this.topIndex++;
20            return this.items.push(element);
21        }
22        //otherwise return a warning message
23        return 'the stack is full!'
24    }
25}

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

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

1// Stack class
2class Stack {
3  
4    // Array is used to implement stack
5    constructor()
6    {
7        this.items = [];
8        this.maxlength = maxlength;
9        this.topIndex = -1;
10    }
11
12    // pop function
13    pop()
14    {
15        // return top most element in the stack if stack is not empty
16        // and removes it from the stack
17        // Underflow if stack is empty
18        if (this.items.length == 0)
19        {
20            return "Underflow";
21        }
22        topIndex--;
23        this.maxlength = this.maxlength - 1;
24        return this.items.pop();
25      
26    }
27}

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

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

1// Stack class
2class Stack {
3  
4    // Array is used to implement stack
5    constructor()
6    {
7        this.items = [];
8        this.maxlength = maxlength;
9        this.topIndex = -1;
10    }
11
12    // peek function
13    peek()
14    {
15        // return the top most element from the stack
16        // but does'nt delete it.
17        return this.items[this.items.length - 1];
18    }
19}

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

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

1// Stack class 
2class Stack {
3    // Array is used to implement stack 
4    constructor() 
5    {
6        this.items = [];
7        this.maxlength = maxlength; 
8        this.topIndex = -1; 
9    } 
10
11    // isFull function 
12    isFull() 
13    { 
14        // check whether the stack is full or not
15        if (this.items.length==this.maxlength)
16        {
17             return 'the stack is full!'
18        }
19        return 'the stack is not full.'
20    } 
21}

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

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

1// Stack class 
2class Stack { 
3    // Array is used to implement stack 
4    constructor() 
5    { 
6        this.items = [];
7        this.maxlength = maxlength; 
8        this.topIndex = -1; 
9    } 
10    // isEmpty function 
11    isEmpty() 
12    { 
13        // return the top most element from the stack // but does'nt delete it. 
14        if (this.items.length==0) 
15        { 
16            return 'the stack is Empty!'
17        } 
18        return 'the stack is not Empty.' 
19    } 
20}

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

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

1// Stack class 
2class Stack {
3    // Array is used to implement stack 
4    constructor() 
5    { 
6        this.items = [];
7        this.maxlength = maxlength; 
8        this.topIndex = -1; 
9    } 
10    
11    // Clear function 
12    Clear() 
13    { 
14        // Clear all items. 
15        this.topIndex = -1
16    } 
17}

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

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

1// Stack class 
2class Stack { 
3    // Array is used to implement stack 
4    constructor() 
5    { 
6        this.items = [];
7        this.maxlength = maxlength; 
8        this.topIndex = -1;  
9    } 
10    // Size function 
11    Size() 
12    { 
13        // Return the size of the stack
14        return this.topIndex 
15    } 
16}

جمع‌بندی

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

بر اساس رای ۱۱ نفر
آیا این مطلب برای شما مفید بود؟
اگر بازخوردی درباره این مطلب دارید یا پرسشی دارید که بدون پاسخ مانده است، آن را از طریق بخش نظرات مطرح کنید.
منابع:
javascripttutorialdevfreecodecampgeeksforgeeks
نظر شما چیست؟

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *