هياكل البيانات: Stacks

Abatherمنذ 7 سنوات

بسم الله الرحمن الرحيم

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

استكمال لما بدأته من شرح هياكل البيانات القوائم أحادية الرابط

كذلك قام الأخ @Hana Alalwi بشرح القوائم ثنائية الرابط هنا:

https://3alam.pro/articles/algorithms/doubly-linked-list/

في هذا الشرح سوف نتطرق للـ stacks.

ماذا نعني بـ Stack؟

هي عبارة عن خط انتظار لمجموعة من البيانات، ما يميز هذا الخط بأنه مفتوح من اتجاه واحد فقط

أي أن البيانات تدخل وتخرج من بوابة واحدة. يطلق على stack بـ LIFO وهذا الرمز يعني بأن آخر عنصر

دخل إلى stack هو أول عنصر يقادرها، وهذا بديهي بما أنه لا يوجد لدينا الى فتحة واحدة لإدخال وإخراج العناصر.

stack يمكننا أن نشبهها بحاملة الأقراص المدمجة فآخر قرص تقوم بوضعه هو أول قرص تقوم بإخراجه، أو كمجموعة

كتب متراصة فوق بعضها البعض:

صورة1.png

لماذا نستخدم stack؟

يمكننا استخدام stack في عدة مواقف هذه بعض منها:

- في حالة وجود بيانات ونريد عرضهم بالمعكوس، فعندها ندفع هذه العناصر الى stack وعند إخراجهم فإن آخر عنصر سوف يخرج أولاً.

- تستخدم في لغات البرمجة لتتحقق من وجود تطابق بين الرموز المدخلة (مثلاً للتأكد بأن كل { لديها } ).

- تستخدم لإضافة الأعداد الكبيرة باستخدام بعض الخوارزميات.

ماهي الوظائف التي نحتاجها في stack ؟

push: وهذه العملية تستخدم لإضافة عناصر إلى الـ stack.

pop: تستخدم لإخراج أول عنصر (آخر عنصر اضيف) من stack.

isEmpty: تستخدم لفحص اذا ما كانت stack خالية أو لا.

clear: تستخدم لحذف جميع العناصر في stack.

topEl: تستخدم للاستعلام عن أول عنصر (آخر عنصر مضاف) في stack.

ملاحظة: من الممكن أن تختلف المسميات للـ functions لكن هذه العناصر الأساسية لإنشاء stack

كذلك سنستعين بالقوائم (القائمة أحادية الرابط) لإنشاء stack (يمكننا أن نقوم بإنشائها عن طريق المصفوفات).

مثال على push و pop*:

صورة1.png

الأكواد:


import java.util.LinkedList;
public class Stack {
	private LinkedList<Integer> stackList = new LinkedList<Integer>();
      }

هذا السطر لإنشاء قائمة ونوع البيانات التي تحتويها integer (بالإمكان تغير نوع البيانات إلى أي نوع آخر)

كما نلاحظة فإن القائمة خاصة (private) وذلك لمنع أي أوبجكت من خارج الـ class من التغير عليها.


public Stack(){
	}

هذه كونستركتر يستخدم لإنشاء stack .


	public void clear(){
		stackList.clear();
	}

تستخدم لحذف جميع العناصر الموجودة في stack.


public boolean isEmpty(){
		return stackList.isEmpty();
	}

تستخدم للإستعلام اذا ما كانت الـ stack خالية أو لا،

في حال كانت خالية تقوم بإرسال (False) الى المنادي.

في حال كانت غير خالية ترسل (True) للمنادي.


public Integer topEl(){
		if(!isEmpty())
			return stackList.getLast();
		else
			throw new java.util.EmptyStackException();
	}

تستخدم للإستعلام عن أول عنصر (آخر عنصر مضاف) موجود في stack وتقوم بإعادة قيمة العنصر

الموجود في الأعلى للمنادي .

كما نلاحظ فإننا قمنا بوضع شرط لتفادي الحصول على خطأ ففي حال عدم وجود عناصر نقوم بإرسال

خطأ من أنفسنا.


public void push(int i){
		stackList.add(i);
	}

اضافة عنصر جديد الى أعلى الـ stack.


public Integer pop(){
		if(!isEmpty())
		{	
			return stackList.removeLast();
		}else
			throw new java.util.EmptyStackException();
	}

نستخدم هذه الـ function لإخراج أعلى عنصر موجود في stack وحذفه منها.

كما في السابق ولتجنب الوقوع في stack خاليها فإننا سنتأكد من وجود عناصر ومن ثم نقوم بالعملية.

ملاحظة: لقد استعنا بالكثير من وظائف القوائم لذلك يجب أن تلم بها لتتضح الصورة أكثر.

لماذا لا نستخدم المصفوفات بدل القوائم؟

للوهلة الأولى يخيل إلينا بأنه لا يوجد أي فرق في استخدام المصفوفات بدل القوائم

لكن في الحقيقة هناك الكثير من الفروقات الجوهدية والتي يتضح أثرها مع البيانات الكثيرة

فكلما زاد حجم البيانات اتضح لدينا الفرق بينهما وهذه بعض الفروق:

- هدر مساحة في الذاكرة: فعندما نقوم بانشاء مصفوفة حتى وإن كانت ArrayList فإن النظام يقوم

بحجز مساحة (هذه المساحة ثابته لا تزيد ولا تنقص) لها وقد نكون لسنا بحاجة لهذه المساحة وبهذا

نكون قد اهدرنا مكان في الذاكرة، علىالعكس من ذلك فإن القوائم لا تشغل من الذاكرة سوى المساحة

التي تحتاجة بدون الحاجة للحجز بتاتاً.

- الحاجة لإعادة نسخ البيانات: كما اشرنا سابقاً فإن حجم المصفوفة ثابت لا يتغيرفي حال امتلائ المصفوفة

والحاجة الى مساحة أكبر سيقوم النظام بعمل مصفوفة جديدة ذات حجم أكبر وينسخالبيانات السابقة اليها وفي

هذا هدر للوقت حيث أن نسخ البيانات لو كانت كثيرة يحتاجة، وكما اشرنا سابقا فإن القوائم لا تحتاج الى هذا الأمر.

هذا مثال بسيط سنستخدم فيه stack التي قمنا بإنشائها لنعسك مجموعة من الأرقام المعطاه:


public static void main(String[] args) {
		Stack myStack = new Stack();
		int[] a = {1, 2, 3, 4, 5, 6, 7, 8, 9};
		
		
		System.out.println("العنصار بترتيبها في المصفوفة:");
		for(int i =0; i < 9; i++){
			myStack.push(a[i]);
			System.out.print(myStack.topEl() + " ");
		}

		System.out.println("\n"+"العناصر بعد وضعها في stack:");
		for(int i = 0; i < 9; i++)
			System.out.print(myStack.pop() + " ");
	}