كيفية تنفيذ مكدس في Vanilla JavaScript و ES6

A كومة هو مجموعة مرتبة من العناصر التي تتبع آخر في الخروج أولا مبدأ (LIFO). تتم إضافة العناصر وإزالتها في نفس النهاية ، أي في الجزء العلوي. توجد أحدث العناصر في الأعلى ، بينما توجد العناصر الأقدم في الأسفل.

لدينا العديد من الأمثلة على الأكوام من حولنا مثل كومة من الكتب أو كومة من الصواني أو الأطباق ، إلخ.

A المكدس يستخدم من قبل المجمعين في لغات البرمجة، من خلال ذاكرة الكمبيوتر إلى متغيرات مخزن والمكالمات وظيفة، وفي برامج تحرير النصوص لأداء التراجع وعمليات إعادة.

قائمة العمليات التي أجريت على Stack

  • push () : إضافة عنصر واحد أو عدة عناصر إلى الجزء العلوي من Stack.
  • pop () : يزيل ويعيد العنصر العلوي للمكدس.
  • نظرة خاطفة () : إرجاع العنصر الأعلى في المكدس.
  • isEmpty () : يعود Trueإذا كان Stack فارغًا ، Falseوإلا.
  • مسح () : يزيل كل العناصر من المكدس.
  • size () : إرجاع طول الحزمة.

إنشاء كومة

نهج كلاسيكي

سنقوم بتنفيذ مكدس مثل كيفية تنفيذه بلغات أخرى بصرف النظر عن JavaScript.

سوف نستخدم مجموعة و متغير إضافي لتتبع العناصر.

function Stack(){ var items = []; var top = 0; //other methods go here }

ادفع عنصرًا في المكدس

//Push an item in the Stackthis.push = function(element){ items[top++] = element } //top++, first performs the operation then increment's the value

انبثق عنصرًا من Stack

//Pop an item from the Stackthis.pop = function(){ return items[--top]; } //--top, first decrements the value then performs the operation

نظرة خاطفة على العنصر العلوي من المكدس

//peek an item in the Stackthis.peek = function(){ return items[top - 1]; }

تحقق مما إذا كان Stack فارغًا

//Is stack emptythis.isEmpty = function(){ return top === 0; }

امسح المكدس

//clear the stackthis.clear= function(){ top = 0; }

حجم المكدس

//Size of the Stackthis.size = function(){ return top; }

التنفيذ الكامل للمكدس

function Stack(){ var items = []; var top = 0; //other methods go here 
 //Push an item in the Stack this.push = function(element){ items[top++] = element } //top++, first performs the operation then increment's the value 
 //Pop an item from the Stack this.pop = function(){ return items[--top]; } //--top, first decrements the value then performs the operation 
 //Peek top item of the Stack this.peek = function(){ return items[top - 1]; } 
 //Is Stack empty this.isEmpty = function(){ return top === 0; } 
 //Clear the Stack this.clear = function(){ top = 0; } 
 //Size of the Stack this.size = function(){ return top; }
}

مثال

سنقوم الآن بإنشاء مثيل جديد لما قمنا بتنفيذه والتحقق مما إذا كان يعمل بشكل صحيح.

var stack = new Stack(); //creating new instance of Stack stack.push(1); stack.push(2); stack.push(3); console.log(stack.peek()); console.log(stack.isEmpty()); console.log(stack.size()); console.log(stack.pop()); console.log(stack.size()); stack.clear(); console.log(stack.isEmpty()); 
Output: 3 false 3 3 2 true

تنفيذ المكدس باستخدام JavaScript

سنقوم بتنفيذ مكدس باستخدام مصفوفة JavaScript تحتوي على طرق مضمنة مثل push and pop.

function Stack(){ var items = []; //other methods go here }

ادفع عنصرًا في المكدس

//push an item in the Stackthis.push = function(element){ items.push(element); }

انبثق عنصرًا من Stack

//Pop an item from the Stackthis.pop = function(){ return items.pop(); }

نظرة خاطفة على العنصر العلوي من المكدس

//Peek top item of the Stackthis.peek = function(){ return items[items.length - 1]; }

تحقق مما إذا كان Stack فارغًا

//Is Stack emptythis.isEmpty = function(){ return items.length === 0; }

امسح المكدس

//Clear the Stackthis.clear = function(){ items.length = 0; }

حجم المكدس

//Size of the Stackthis.size = function(){ return items.length; }

التنفيذ الكامل لـ Stack

function Stack(){ var items = []; //other methods go here 
 //Push a item in the Stack this.push = function(element){ items.push(element); } 
 //Pop a item from the Stack this.pop = function(){ return items.pop(); } 
 //Peek top item of the Stack this.peek = function(){ return items[items.length - 1]; }
 //Is Stack empty this.isEmpty = function(){ return items.length === 0; } 
 //Clear the Stack this.clear = function(){ items.length = 0; } 
 //Size of the Stack this.size = function(){ return items.length; } 
}

جعل الخصائص والأساليب خاصة من خلال الإغلاق و IIFE (استدعاء التعبير الوظيفي فورًا).

var Stack = (function () { return function Stack(){ var items = []; //other methods go here 
 //Push an item in the Stack this.push = function(element){ items.push(element); } 
 //Pop an item from the Stack this.pop = function(){ return items.pop(); } 
 //Peek top item from the Stack this.peek = function(){ return items[items.length - 1]; } 
 //Is Stack empty this.isEmpty = function(){ return items.length === 0; } 
 //Clear the Stack this.clear = function(){ items.length = 0; } //Size of the Stack this.size = function(){ return items.length; } }})();

تكديس باستخدام ES6.

class Stack{ constructor(){ this.items = []; } //other methods go here //Push an item in the Stack push = function(element){ this.items.push(element); }
//Pop an item from the Stack pop = function(){ return this.items.pop(); } //Peek top item from the Stack peek = function(){ return this.items[this.items.length - 1]; }
//Is Stack empty isEmpty = function(){ return this.items.length === 0; }
//Clear the Stack clear = function(){ this.items.length = 0; } //Size of the Stack size = function(){ return this.items.length; }}

تكديس باستخدام ES6 WeakMap.

const items = new WeakMap();class Stack{ constructor(){ items.set(this, []); } //other methods go here //Push an item in the Stack push = function(element){ let temp = items.get(this); temp.push(element); }
//Pop an item from the Stack pop = function(){ let temp = items.get(this); return temp.pop(); } //Peek top item from the Stack peek = function(){ let temp = items.get(this); return temp[temp.length - 1]; }
//Is Stack empty isEmpty = function(){ let temp = items.get(this); return temp.length === 0; }
//Clear the Stack clear = function(){ let temp = items.get(this); temp.length = 0; } //Size of the Stack size = function(){ let temp = items.get(this); return temp.length; }}

جعل الخصائص والطرق خاصة من خلال الإغلاق و IIFE (استدعاء التعبير عن الوظيفة فورًا) للمكدس باستخدام ES6 WeakMap.

let Stack = (() => { const items = new WeakMap(); return class Stack{ constructor(){ items.set(this, []); }
//other methods go here //Push an item in the Stack push = function(element){ let temp = items.get(this); temp.push(element); }
//Pop an item from the Stack pop = function(){ let temp = items.get(this); return temp.pop(); }
//Peek top item from the Stack peek = function(){ let temp = items.get(this); return temp[temp.length - 1]; }
//Is Stack empty isEmpty = function(){ let temp = items.get(this); return temp.length === 0; }
//Clear the Stack clear = function(){ let temp = items.get(this); temp.length = 0; }
//Size of the Stack size = function(){ let temp = items.get(this); return temp.length; } }})();

تعقيد الوقت

# معدل

الوصول: Θ (N)

بحث: Θ (N)

إدراج: Θ (1)

حذف: Θ (1)

# الأسوأ

الوصول: O (N)

البحث: O (N)

إدراج: O (1)

حذف: O (1)

تعقيد الفضاء

# الأسوأ : O (N)

هناك الكثير من المشاكل حيث يمكن أن يكون Stack هو بنية البيانات المثالية اللازمة للحل.

  • خوارزمية المحول الأساسي
  • أقواس متوازنة

إذا أعجبك هذا المقال ، يرجى إعطائه بعض؟ ومشاركته! إذا كان لديك أي أسئلة تتعلق بهذا فلا تتردد في طرحها علي.

لمزيد من مثل هذا والحلول الحسابية في Javascript ، تابعوني على Twitter . أنا أكتب عن ES6، رد فعل، Nodejs، وهياكل البيانات، والخوارزميات على learnersbucket.com .