بناء الـ Stack عن طريق الـ LinkedList
السلام عليكم ورحمة الله وبركاته
الفهرس
المقدمة
حسنًا بعد ما انتهينا من فهم الـ LinkedList
وكيفية بناءه
سنقوم الآن ببناء الـ Stack
عن طريق الـ LinkedList
وصدقني سيكون الأمر سهلًا جدًا وكأنك تقوم بتنفيذ الـ push
والـ pop
على الـ LinkedList
لكن مع تغير بعض الأسماء والتعديل على بعض الأمور ليتناسب مع مفهوم الـ Stack
طبعًا ستجد بعض الأشخاص يقومون ببناء الـ Stack
عن طريق الـ Array
أو الـ Dynamic Array
بطرق معينة
وهي طرق صحيحة ولكن نحن هنا سنقوم ببناء الـ Stack
عن طريق الـ LinkedList
لنبدأ بالشرح
ما هو الـ Stack ؟
كيف نبني ما لا نعرفه ؟
لذا سنبدأ بتعريف الـ Stack
ومن ثم سنقوم ببناءه
مع العلم أنني قمت بشرح بعض التفاصيل عن الـ Stack
في مقالة كودك بـ Recursion نفسه ؟
وقلنا أن الذاكرة تستخدم الـ Stack
لتخزين وتتبع الدوال والمتغيرات والعمليات التي تتم في البرنامج ويسمى هذا الـ Stack
بـ Call Stack
في الذاكرة
لكن هنا سنقوم ببناء الـ Stack
بشكل عام وليس بشكل خاص للـ Call Stack
الـ Stack
هو يشبه الوعاء مفتوح من الاعلى ومغلق من الاسفل ويتم وضع فيه الاشياء فوق بعضها
ويتعامل بطريقة الـ LIFO
أي Last In First Out
بمعنى ما يدخل أخرًا يخرج أولًا
جرب احضار ثلاث كتب ورقم تلك الكتب الثلاثة من 1
الى 3
جرب ان تضع الكتب الثلاثة فوق بعضها ابتداءًا من رقم 1
الى رقم 3
ستلاحظ ان الكتاب الاول اصبح في القاع والكتاب الثالث وهو اخر ما وضعته في القمة
ان قلت لك اخرج اخر كتاب فستحضر لي الكتاب رقم ثلاثة لانه اخر كتاب وضعته
وهذا هو معنى ما يدخل أخرًا يخرج أولًا - Last In First Out
فتخيل الـ Stack
كما في الشكل التالي
حاليًا هو فارغ ولا يحتوي على شيء
| |
| |
| |
| |
| |
| |
----------
الآن سنقوم بوضع الكتاب رقم 1
في الـ Stack
| |
| |
| |
| |
| |
| Book 1 |
----------
الآن سنقوم بوضع الكتاب رقم 2
في الـ Stack
| |
| |
| |
| |
| Book 2 |
| Book 1 |
----------
الآن سنقوم بوضع الكتاب رقم 3
في الـ Stack
| |
| |
| |
| Book 3 |
| Book 2 |
| Book 1 |
----------
الآن عندما أقول لك أخرج لي الكتاب رقم 1
ستقول لي لا تستطيع أن تخرجه بشكل مباشر
بل يجب عليك أن تخرج الكتاب رقم 3
أولًا ثم الكتاب رقم 2
ثم الكتاب رقم 1
وهذا هو مفهوم الـ Stack
وكيفية عمله
فترتيب الخروج من الـ Stack
يكون عكس ترتيب الادخال
لذا قلت لك ما يدخل أخرًا يخرج أولًا وهو ما نسميه بـ LIFO
أو Last In First Out
المكونات الأساسية للـ Stack
الآن بعد أن فهمنا مفهوم الـ Stack
سنقوم بتحديد المكونات الأساسية للـ Stack
والتي سنقوم بإنشائها وهي كالتالي
push
: وهي الدالة التي تقوم بإضافة عنصر جديد الى الـStack
pop
: وهي الدالة التي تقوم بإخراج العنصر الأخير الذي تم إضافته الى الـStack
peek
: وهي الدالة التي تقوم بإظهار العنصر الأخير الذي تم إضافته الى الـStack
بدون إخراجه
وعليك أن تعلم أن الـ Stack
له جهة واحدة فقط لذا فهذه الدوال الثلاثة ستقوم باضافة واخراج العناصر من جهة واحدة فقط
وأخر شيء مثل ما كان لدينا head
و tail
في الـ LinkedList
فلدينا top
ويمكنك تخيله مثله مثل head
أو tail
وهو Node
يشير الى العنصر الأخير الذي تم إضافته الى الـ Stack
عندما تنظر لفكرة الـ push
والـ pop
في الـ Stack
ستجد انها تشبه الى حد كبير الـ unshift
والـ shift
في الـ LinkedList
لأن الـ unshift
تقوم بإضافة Node
جديد من البداية والـ shift
تقوم بإزالة Node
من البداية أيضًا
وكلاهما يعملان من ناحية واحدة فقط وهي البداية وأيضًا يستغرقان سرعة O(1)
فقط
لذا دالة push
ودالة pop
التي سنقوم بإنشائهما في الـ Stack
ليكونا هما نفسهما unshift
و shift
في الـ LinkedList
لكن مع تغير طفيف وهو أننا سنستخدم top
بدلاً من head
و tail
لأن الـ Stack
له جهة واحدة فقط ولا نحتاج لـ tail
لأننا لا نهتم بالجهة الأخرى
قد تقول لي لما لم نستخدم push
و pop
بدلًا من unshift
و shift
؟ أي نضيف ونحذف من الجهة الأخرى
حسنًا نعم نستطيع استخدامهما ولكن هناك مشكلة هنا
وهي دالة push
تأخذ O(1)
ولكن دالة pop
تأخذ O(n)
وهذا لأنها تحتاج للوصول الى الـ Node
الأخير لتقوم بإزالته
لذا الاعتماد على unshift
و shift
الموجودان في الـ LinkedList
سيكون أفضل لأنهما سيستغرقان O(1)
فقط
الآن بعد هذه النبذة البسيطة عن الـ Stack
ومكوناته لنقم ببناء الـ Stack
عن طريق الـ LinkedList
بناء الـ Stack عن طريق الـ LinkedList
قبل أن نبدأ ببناء الـ Stack
عن طريق الـ LinkedList
لما لا تقوم بمحاولة بناء الـ Stack
بنفسك ؟
أظنك بعد ما بنيت الـ LinkedList
ستكون قادرًا على بناء الـ Stack
بنفسك طالما فهمت مفهوم الـ Stack
أريدك أن تتوقف عن القراءة الآن وتحاول بناء الـ Stack
بنفسك
ثم عندما تنتهي تعود لتكملة القراءة
حسنًا الآن بعد أن قمت بمحاولة بناء الـ Stack
بنفسك (أتمنى أن تكون قد فعلت ...)
حسنًا الآن سنقوم ببناء الـ Stack
وأولًا سنقوم بإنشاء الـ Node
بالطبع
class Node {
public data: number;
public prev: Node | null;
constructor(data: number, prev: Node | null = null) {
this.data = data;
this.prev = prev;
}
public setPrev(prev: Node | null) {
this.prev = prev;
}
}
لاحظ أننا هنا نستخدم prev
بدلاً من next
لأنك إذا قمت بتخيل الـ Stack
كـ LinkedList
فستلاحظ أن كل Node
يشير الى الـ Node
الذي قبله
وبالطبع لدينا دالة setPrev
التي تقوم بتغيير قيمة الـ prev
تتذكر مثال الكتب الثلاثة ؟
| |
| |
| |
| Book 3 |
| Book 2 |
| Book 1 |
----------
تخيله كـ LinkedList
ستجد ان الكتاب رقم 3
يشير الى الكتاب رقم 2
والكتاب رقم 2
يشير الى الكتاب رقم 1
والكتاب رقم 1
لا يشير الى شيء لأنه هو الأول
لذا تأمل الشكل التالي لتفهم ما أقصده
+--------+
| Book 3 | <--- top
+--------+
|
v
+--------+
| Book 2 |
+--------+
|
v
+--------+
| Book 1 |
+--------+
لاحظ أن كل Node
كأنها يتم تكديسها فوق بعضها وكل Node
تشير الى الـ Node
الذي قبلها
لذا نستخدم prev
بدلاً من next
لأننا نريد ان نشير الى الـ Node
الذي قبلنا وليس الذي بعدنا
الأمر فرق مسميات فقط لا أكثر
الآن بعد أن قمنا بإنشاء الـ Node
سنقوم بإنشاء الـ Stack
class Stack {
private top: Node | null;
private length: number;
constructor() {
this.top = null;
this.length = 0;
}
public isEmpty(): boolean {
return this.length === 0;
}
}
الآن لدينا الـ Stack
وهو يحتوي على top
و length
والـ top
كما قلنا ستشير الى الـ Node
الأخير في الـ Stack
والـ length
سيحتوي على عدد العناصر في الـ Stack
وهنا أضفنا دالة isEmpty
التي تقوم بالتحقق إذا كان الـ Stack
فارغًا أم لا
الآن سنقوم بإضافة الدوال الأساسية للـ Stack
وهي push
و pop
و peek
إضافة Node الى الـ Stack
سنقوم بإضافة Node
جديد الى الـ Stack
وكما تعودنا سنشرها بشكل توضيحي ثم نقوم بتنفيذها ككود
أولًا حاليًا الـ Stack
فارغ ولا يحتوي على شيء
top = NULL
الآن سنقوم بإضافة Node
بقيمة 10
الى الـ Stack
هنا سنقوم بإنشاء Node
جديد new Node(10)
top = null
new Node(10)
0x100
+--------+
| 10 |
+--------+
| NULL |
+--------+
هنا أضفنا Node
جديد بقيمة 10
ولاحظ أن prev
يشير الى NULL
لأنه لا يوجد Node
قبله بعد لأنه الأول
ثم لاحظ أن top
حاليًا يشير الى NULL
الآن نحتاج لتغيير top
ليشير الى الـ Node
الجديد الذي أضفناه this.top = node
0x100 <--- top
+--------+
| 10 |
+--------+
| NULL |
+--------+
وهكذا تمت عملية الـ push
بنجاح وتم أول Node
الى الـ Stack
لكن لنحاول إضافة Node
جديد بقيمة 20
عندما ننشيء Node
جديد new Node(20)
سيكون الشكل كالتالي
new Node(20)
0x200
+--------+
| 20 |
+--------+
| NULL |
+--------+
0x100 <--- top
+--------+
| 20 |
+--------+
| NULL |
+--------+
أضفنا Node
جديد بقيمة 20
لكنها ليست ضمن الـ Stack
بعد نحتاج لربطها
أول شيء طالما أضفنا Node
جديدة فقيمة الـ prev
الخاصة بها ستشير للـ Node
الذي كانت قبلها
وهي نفس الـ Node
التي يشير اليها top
لذا سنقوم بتغيير prev
للـ Node
الجديدة لتشير الى الـ Node
الذي يشير اليه top
حاليًا node.prev = this.top
0x200
+--------+
| 20 |
+--------+
| 0x100 |
+--------+
|
|
v
0x100 <--- top
+--------+
| 20 |
+--------+
| NULL |
+--------+
الآن تم ربط الـ Node
الجديدة بالـ Stack
والآن نحتاج فقط لتغيير top
ليشير الى الـ Node
الجديدة this.top = node
0x200 <--- top
+--------+
| 20 |
+--------+
| 0x100 |
+--------+
|
|
v
0x100
+--------+
| 10 |
+--------+
| NULL |
+--------+
وهكذا تمت إضافة Node
جديدة الى الـ Stack
بنجاح
الآن سنقوم بتنفيذ الكود وترى أن الكود يكاد يكون اسهل وابسط من الشرح التوضيحي
class Stack {
// ...
public push(value: number) {
const node = new Node(value);
node.prev = this.top;
this.top = node;
this.length++;
return this;
}
}
لاحظ أننا هنا نقوم بنفس الخطوات التي شرحناها سابقًا
- ننشئ
Node
جديدة - نربط الـ
prev
الخاصة بالـNode
الجديدة بالـNode
الذي يشير اليهtop
حاليًا - نغير
top
ليشير الى الـNode
الجديدة - نزيد الطول بواحد
وهكذا تمت عملية الـ push
بنجاح
وتتذكر الـ constructor
الخاص بالـ Node
؟
كنا جعلناه يستقبل prev
لذا يمكننا الاستفادة منه وتبسط الكود قليلاً
class Stack {
// ...
public push(value: number) {
this.top = new Node(value, this.top);
this.length++;
return this;
}
}
هذا كل شيء ! ... اا .. سطرين فقط !
هنا نحن اختصرنا هذه الأسطر الثلاثة
const node = new Node(value);
node.prev = this.top;
this.top = node;
الى سطر واحد فقط
this.top = new Node(value, this.top);
وهذا بفضل الـ constructor
الذي في الـ Node
لكن أنتظر لحظة ! هذا أبسط من دالة unshift
الخاصة بالـ LinkedList
التي كانت تقوم بإضافة Node
جديد من بداية الـ LinkedList
لكن الفرق هنا أننا نستخدم top
أما في الـ LinkedList
كنا نستخدم head
و tail
فكانت تحتاج لبعض الخطوات الإضافية
لكن بسبب أن الـ Stack
له جهة واحدة فقط فالأمر أبسط بكثير ولا نحتاج للـ tail
والعمليات الإضافية الخاصة بالجهة الأخرى
لنرى استخدام الـ push
في الـ Stack
const stack = new Stack();
stack.push(10).push(20).push(30);
// 30 -> 20 -> 10
وهكذا بكل بساطة أنشأنا دالة push
الخاصة بالـ Stack
واستخدمناها
إزالة Node من الـ Stack
الآن سنقوم بإزالة Node
من الـ Stack
وهي عملية الـ pop
والـ pop
في الـ Stack
تقوم بإزالة الـ Node
من ناحية الـ top
فقط كما قلنا سابقًا
عملية الـ pop
في الـ Stack
تكون أبسط بكثير من الـ shift
في الـ LinkedList
عندما كانت تقوم بإزالة الـ Node
من ناحية الـ head
الآن نشرح عملية الـ pop
بشكل توضيحي ثم نقوم بتنفيذها ككود
لنفترض أن لدينا الـ Stack
التالي
0x300 <--- top
+--------+
| 30 |
+--------+
| 0x200 |
+--------+
|
|
v
0x200
+--------+
| 20 |
+--------+
| 0x100 |
+--------+
|
|
v
0x100
+--------+
| 10 |
+--------+
| NULL |
+--------+
الآن سنقوم بإزالة الـ Node
من الـ Stack
وهو الـ Node
الذي يشير اليه top
حاليًا
لأنه في الـ Stack
نقوم بالاضافة والازالة من ناحية الـ top
فقط
الآن لكي نزيل الـ Node
فقط نقوم بتغيير الـ top
ليشير الى الـ Node
السابقة له this.top = this.top.prev
0x300 <--- temp
+--------+
| 30 |
+--------+
| 0x200 |
+--------+
|
|
v
0x200 <--- top
+--------+
| 20 |
+--------+
| 0x100 |
+--------+
|
|
v
0x100
+--------+
| 10 |
+--------+
| NULL |
+--------+
لاحظ كيف أنتقل top
من الـ Node
الأخير الى الـ Node
الذي قبله وهكذا تمت عملية الـ pop
بنجاح
بالطبع كما قلنا الـ Node
السابقة تحتاج لازالتها يدويًا في اللغات التي لا تدعم الـ Garbage Collection
وللقيام بهذا عليك أن تنشيء متغير مؤقت يدعى temp
وتجعله يشير الى الـ Node
الذي تم إزالته ثم تقوم بإزالته يدويًا كما فعلنا سابقًا بغرض توضيح الأمور
0x300 <--- temp
+--------+
| 30 | temp.prev = NULL
+--------+ delete temp
| NULL |
+--------+
0x200 <--- top
+--------+
| 20 |
+--------+
| 0x100 |
+--------+
|
|
v
0x100
+--------+
| 10 |
+--------+
| NULL |
+--------+
الآن سنقوم بتنفيذ الكود وسترى أنه بسيط جدًا
class Stack {
// ...
public pop() {
if (this.isEmpty()) {
throw new Error('Stack is empty');
}
let temp = this.top;
this.top = this.top.prev;
temp.setPrev(null);
this.length--;
return temp.data;
}
}
لاحظ أننا هنا نقوم بالخطوات التالية:
- نتحقق أولًا إذا كان الـ
Stack
فارغًا أم لا ونقوم برميException
إذا كان فارغًا - نقوم بإنشاء متغير مؤقت يسمى
temp
يشير الى الـNode
الذي سنقوم بإزالته - نقوم بتغيير
top
ليشير الى الـNode
الذي قبل الـNode
- نقوم بجعل
prev
للـNode
الذي تم إزالته يشير الىNULL
- نقوم بإنقاص الطول بواحد
بالطبع أذكر مرة أخرى مرارًا وتكرارًا في اللغات التي لا تدعم الـ Garbage Collection
عليك أن تقوم بإزالة الـ Node
يدويًا كما فعلنا
كما نفعل في الـ C++
باستخدام delete
وهكذا تمت عملية الـ pop
بنجاح وقمنا بإزالة الـ Node
من الـ Stack
لنرى استخدام الـ pop
في الـ Stack
const stack = new Stack();
stack.push(10).push(20).push(30);
// 30 -> 20 -> 10
console.log(stack.pop()); // 30
console.log(stack.pop()); // 20
console.log(stack.pop()); // 10
console.log(stack.pop()); // Error: Stack is empty
عرض آخر عنصر في الـ Stack
الآن سنقوم بإضافة دالة peek
التي تقوم بعرض آخر عنصر في الـ Stack
دون إزالته
وهي دالة بسيطة جدًا ولا تحتاج لشرح توضيحي من الأساس
class Stack {
// ...
public peek(): number | null {
if (this.isEmpty()) {
return null;
}
return this.top.data;
}
}
هنا نحن نتحقق إذا كان الـ Stack
فارغًا أم لا
فإذا كان فارغًا نقوم بارجاع null
وإذا لم يكن فارغًا فهذا يعني أن هناك Node
واحد على الأقل في الـ Stack
لذا نقوم بإرجاع قيمة الـ Node
الذي يشير اليه top
حاليًا
لنرى استخدام الـ peek
في الـ Stack
const stack = new Stack();
stack.push(10).push(20).push(30);
// 30 -> 20 -> 10
console.log(stack.peek()); // 30
stack.pop();
console.log(stack.peek()); // 20
وهكذا أكملنا بناء الـ Stack
الأساسي باستخدام الـ LinkedList
يمكننا إضافة بعض الدوال الإضافية مثل clear
و print
و search
وغيرها
هذه الدوال يمكنك إضافتها بنفسك كتمرين
فائدة الـ Stack
الـ Stack
هو مجرد Data Structure
لها طريقتها الخاصة في التعامل مع البيانات
فكما تعرف أن هياكل البيانات هي مجرد أدوات تساعدنا في تنظيم البيانات والتعامل معها بشكل معين
فالـ Stack
يستخدم في الأمور التي تحتاج إلى أن يكون ترتيب الدخول عكس ترتيب الخروج
أي كما قلنا ما يدخل أخرًا يخرج أولًا وهو ما يسمى بـ LIFO
مثل عملية الـ Undo
في البرامج حيث يتم تخزين العمليات التي تمت في البرنامج في الـ Stack
وعند الضغط على زر الـ Undo
يتم إزالة العملية الأخيرة التي تمت في البرنامج
وكذلك في الـ Call Stack
في الذاكرة حيث يتم تخزين الدوال التي تنادي بعضها البعض في البرنامج
لذا تحتاج لتنفيذ الدوال بشكل عكسي من أخر دالة تم استدعائها
ويمكنك معرفة المزيد عن الـ Call Stack
في مقالة كودك بـ Recursion نفسه ؟
وتستخدم بشكل ضمني في العديد من الخوارزميات الي سنتعرض لها في المقالات القادمة
مثل الـ DFS
في الـ Graph
والـ Backtracking
وغيرها
وهناك العديد من الاستخدامات الأخرى للـ Stack
والتي ستكتشفها بنفسك مع الوقت
خاتمة
في هذه المقالة القصيرة قمنا ببناء الـ Stack
عن طريق الـ LinkedList
ولاحظ أنك بمجرد فهمك للـ LinkedList
وكيفية بنائه فإنك ستكون قادرًا على بناء الـ Stack
بكل سهولة
وهذا ما قلته لك في مقالة الـ LinkedList
أنها تعتبر الأساس للعديد من الهياكل البيانية الأخرى
فبمجرد فهمك لمفهوم الـ Stack
وكيفية عمله فإنك ستكون قادرًا على بناءه بكل سهولة
وكما لاحظت أن طريقة عمل الـ Stack
تشبه الـ LinkedList
بشكل كبير مع بعض التعديلات على الأسماء والدوال لتتناسب مع مفهوم الـ Stack
في المقالة القادمة سنقوم ببناء الـ Queue
عن طريق الـ LinkedList
وستكون العملية سهلة جدًا ولن تحتاج للكثير من الوقت لبناءها
بل سيكون بناءها سهل مثل الـ Stack