في المدونة السابقة ، قدمت القائمة التالية. القائمة هي أبسط بنية ، ولكن إذا كنت ترغب في التعامل مع بعض الهياكل الأكثر تعقيدًا ، فإن القائمة تبدو بسيطة للغاية ، لذلك نحتاج إلى بعض بنية البيانات مماثلة للقائمة ولكن أكثر تعقيدًا - المكدس. المكدس عبارة عن بنية بيانات فعالة ، لأنه لا يمكن إضافة البيانات أو حذفها إلا في الجزء العلوي من المكدس ، لذلك هذه العملية سريعة للغاية وسهلة التنفيذ.
1: العملية على المكدس.
المكدس هو قائمة خاصة. لا يمكن الوصول إلى العناصر الموجودة في المكدس إلا من خلال نهاية واحدة من القائمة ، وهذه النهاية هي الجزء العلوي من المكدس. على سبيل المثال ، عند غسل الصحون في مطعم ، يمكنك فقط غسل اللوحة العلوية أولاً. بعد غسل الأطباق ، يمكنك فقط الحلزون الجزء العلوي من مجموعة الأطباق. يُطلق على المكدس هيكل بيانات "Late-In-First-Out" (LIFO).
نظرًا لأن المكدس يحتوي على خصائص الخلف ، لا يمكن الوصول إلى عنصر لا يوجد في الجزء العلوي من المكدس. من أجل الحصول على عناصر ذات مكدس منخفض ، يجب إزالة العنصر أعلاه أولاً. العمليتان الرئيسيتان الذي يمكننا القيام بهما مع المكدس هما دفع عنصر على المكدس وإطفاء عنصر على المكدس. عند إدخال المكدس ، يمكننا استخدام طريقة Push () ، وعندما نضعها ، يمكننا استخدام طريقة POP (). على الرغم من أن طريقة POP () يمكنها الوصول إلى العناصر الموجودة في الجزء العلوي من المكدس ، بعد استدعاء الطريقة ، يتم حذف العناصر الموجودة في الجزء العلوي من المكدس بشكل دائم من المكدس. هناك طريقة أخرى نستخدمها وهي PEEK () ، والتي تُرجع فقط العنصر العلوي من المكدس دون حذفه.
مخططات العمود الفعلية لإدخال المكدس وخروج المكدس هي كما يلي:
Push () و pop () و PEEK () هما الطرق الرئيسية الثلاثة للمكدس ، لكن المكدس له طرق وخصائص أخرى. على النحو التالي:
Clear (): مسح جميع العناصر في المكدس.
الطول (): سجل عدد العناصر في المكدس.
الثاني: تنفيذ المكدس كما يلي:
يمكننا أن نبدأ بتنفيذ طريقة فئة المكدس أولاً ؛ على النحو التالي:
نسخة الكود كما يلي:
دالة المكدس () {
this.datastore = [] ؛
this.top = 0 ؛
}
على النحو الوارد أعلاه: Datastore يحفظ جميع العناصر في المكدس. يسجل أعلى المتغير الموضع في الجزء العلوي من المكدس ويتم تهيئته إلى 0. وهذا يعني أن موضع البداية للمصفوفة المقابلة في الجزء العلوي من المكدس هو 0 ، إذا تم دفع أي عنصر إلى المكدس. سوف تتغير قيمة هذا المتغير وفقًا لذلك.
لدينا أيضًا الطرق التالية: push () ، pop () ، peek () ، clear () ، length () ؛
1. push () طريقة ؛ عند دفع عنصر جديد إلى المكدس ، يجب حفظه في الصفيف المقابل للقمة المتغيرة ، ثم يتم زيادة القيمة العلوية بمقدار 1 ، بحيث تشير إلى الموضع التالي في الصفيف. الرمز التالي:
نسخة الكود كما يلي:
وظيفة الضغط (العنصر) {
this.datastore [this.top ++] = element ؛
}
2. طريقة pop () هي عكس طريقة PUSH () - إنها تُرجع العنصر العلوي ويخصم القيمة العليا بمقدار 1. الرمز التالي:
نسخة الكود كما يلي:
وظيفة pop () {
إرجاع this.datastore [-this.top] ؛
}
3. طريقة PEEK () تُرجع العنصر في الموضع الأعلى 1 من الصفيف ، أي العنصر الأعلى 1 من المكدس ؛
نسخة الكود كما يلي:
وظيفة PEEK () {
إرجاع this.datastore [this.top - 1] ؛
}
4. الطول () طريقة في بعض الأحيان نحتاج إلى معرفة عدد العناصر الموجودة في المكدس. يمكننا إرجاع عدد العناصر الموجودة في المكدس عن طريق إرجاع القيمة العلوية المتغيرة ، كما هو موضح في الكود التالي:
نسخة الكود كما يلي:
طول الوظيفة () {
إرجاع هذا.
}
5. clear () ؛ في بعض الأحيان نريد مسح المكدس ، وقمنا بتعيين القيمة العليا للمتغير إلى 0 ؛ الرمز التالي:
نسخة الكود كما يلي:
وظيفة clear () {
this.top = 0 ؛
}
جميع الرموز أدناه:
نسخة الكود كما يلي:
دالة المكدس () {
this.datastore = [] ؛
this.top = 0 ؛
}
stack.prototype = {
// اضغط على عنصر جديد في المكدس
دفع: وظيفة (عنصر) {
this.datastore [this.top ++] = element ؛
} ،
// الوصول إلى العنصر العلوي من المكدس ، يتم حذف العنصر العلوي من المكدس بشكل دائم
البوب: وظيفة () {
إرجاع this.datastore [-this.top] ؛
} ،
// إرجاع العنصر في موقع Top-1 في الصفيف ، أي العنصر العلوي من المكدس
نظرة خاطفة: وظيفة () {
إرجاع this.datastore [this.top - 1] ؛
} ،
// كم عدد العناصر المخزنة في المكدس
الطول: وظيفة () {
إرجاع هذا.
} ،
// امسح المكدس
واضح: وظيفة () {
this.top = 0 ؛
}
} ؛
أمثلة العروض التوضيحية هي كما يلي:
stack var = stack () ؛
stack.push ("a") ؛
stack.push ("B") ؛
Stack.push ("C") ؛
console.log (stack.length ()) ؛ // 3
console.log (stack.peek ()) ؛ // ج
var proped = stack.pop () ؛
console.log (برزت) ؛ // ج
console.log (stack.peek ()) ؛ // ب
stack.push ("D") ؛
console.log (stack.peek ()) ؛ // د
stack.clear () ؛
console.log (stack.length ()) ؛ // 0
console.log (stack.peek ()) ؛ // غير محدد
أدناه يمكننا تنفيذ تعريف متكرر لوظيفة العامل ؛ على سبيل المثال ، 5! العامل 5! = 5 * 4 * 3 * 2 * 1 ؛
الرمز التالي:
نسخة الكود كما يلي:
وظيفة وظيفة (ن) {
var s = new stack () ؛
بينما (n> 1) {
S.Push (n--) ؛
}
منتج var = 1 ؛
بينما (S.Length ()> 0) {
المنتج *= s.pop () ؛
}
إرجاع المنتج ؛
}
console.log (حقيقة (5)) ؛
يعني الرمز أعلاه: أولاً تمرير الرقم 5 إلى الوظيفة ، واستخدم حلقة الوقت ، وقبل انخفاض 1 في كل مرة ، قم بدفع () من الوظيفة التي تستخدمها إلى المكدس حتى يكون المتغير N أقل من 1. ثم تحديد منتج متغير ؛ حدد ما إذا كان أكبر من 0 بواسطة طريقة الطول () للمكدس ، وفي كل مرة يتم تنفيذ المنتج* = S.POP () ، تقوم طريقة POP () بإرجاع العنصر العلوي من المكدس ويحذف العنصر من المكدس. لذلك في كل مرة تقوم فيها بتنفيذ عنصر حتى S.Length () <= 0. So Product = 5*4*3*2*1. إلخ.