الـ Stack وكيفية بناءه بالـ LinkedList

السلام عليكم ورحمة الله وبركاته

وقت القراءة: ≈ 10 دقائق

المقدمة

حسنًا بعد ما انتهينا من فهم الـ 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

الآن سنقوم بوضع الكتاب رقم 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

المقال السابق:LinkedList كبديل مرن وقوي للـ Array

المقال التالي:الـ Queue وكيفية بناءه بالـ LinkedList