المكادس

من موسوعة حسوب


المكدس هو من بنى المعطيات الخطية والذي يتبع طريقتين في ترتيب أداء العمليات هما LIFO (يدخل آخرًا ويخرج أولًا Last In First Out) أو FILO (يدخل أولًا ويخرج آخرًا First In Last Out).

يمكن تأدية العمليات التالية بصورة رئيسية على المكادس:

  • الإضافة Push: إضافة عنصر إلى المكدس، وإن كان المكدس ممتلئًا، فتُسمى الحالة حينئذٍ بالفيض أو تجاوز السعة overflow.
  • الحذف Pop: تحذف العناصر من المكدس بعكس الترتيب الذي دخلت فيه إلى المكدس، وإن كان المكدس فارغًا فتُسمّى الحالة حينئذٍ بالغيض underflow.
  • القمة Peek or Top: تعيد هذه العملية العنصر الموجود في قمّة المكدس.
  • isEmpty: تعيد هذه العملية قيمة صحيحة إن كان المكدس فارغًا، وتعيد قيمة خاطئة فيما عدا ذلك.

مثال عملي على المكادس

هناك الكثير من الأمثلة العملية في الحياة اليومية والتي يمكن الاستفادة منها في فهم آلية عمل الأكداس. فعلى سبيل المثال يمكن وضع مجموعة من الأطباق فوق بعضها البعض لتشكّل بذلك مكدسًا يكون فيه الطبق الأعلى أوّل طبق يمكن إزالته من المكدس، وهذا يعني أن الطبق الأخير (الأسفل) في هذا المكدس سيبقى فيه لأطول فترة من الوقت، ويمكن القول أنّ هذه الأطباق تتبع الترتيب LIFO/FILO.

التعقيد الزمني الخاصّ بهذه العمليات

تستغرق العمليات push()‎ و pop()‎ و isEmpty()‎ و peek()‎ الوقت O(1)‎ وذلك لعدم استخدام أيّ حلقة تكرارية في هذه العمليات.

تطبيقات على الأكداس

  • موازنة الرموز Balancing of symbols
  • تحويل Infix إلى Postfix / تحويل Prefix
  • عمليات الإعادة والتراجع في الكثير من البرامج مثل محررات النصوص والفوتوشوب.
  • خاصية عرض الصفحات اللاحقة والسابقة في متصفحات الويب.
  • تستخدم الأكداس في كثير من الخوارزميات مثل برج هانوي  Tower of Hanoi، والتنقل في الشجرة Tree Traversals، وفي مسألة المدرج التكراري histogram.
  • تطبيقات أخرى مثل التعقب الخلفي backtracking، ومسألة جولة الفارس Knight tour، والفأر في المتاهة rat in a maze، وحل لعبة السودوكو sudoku.
  • في خوارزميات الصور مثل الفرز الطوبولوجي والمكونات المرتبطة بفعالية Strongly Connected Components.

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

يمكن تنفيذ المكادس بطريقتين:

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

تعرض الأمثلة التالية طرق إنشاء الأكداس باستخدام المصفوفات وفي عدد من لغات البرمجة:

  • C++‎:
#include<bits/stdc++.h> 
  
using namespace std; 
  
#define MAX 1000 
  
class Stack 
{ 
    int top; 
public: 
    int a[MAX];    //تعيين الحد الأعلى للكدس 
  
    Stack()  { top = -1; } 
    bool push(int x); 
    int pop(); 
    bool isEmpty(); 
}; 
  
bool Stack::push(int x) 
{ 
    if (top >= (MAX-1)) 
    { 
        cout << "Stack Overflow"; 
        return false; 
    } 
    else
    { 
        a[++top] = x; 
        cout<<x <<" pushed into stack\n"; 
        return true; 
    } 
} 
  
int Stack::pop() 
{ 
    if (top < 0) 
    { 
        cout << "Stack Underflow"; 
        return 0; 
    } 
    else
    { 
        int x = a[top--]; 
        return x; 
    } 
} 
  
bool Stack::isEmpty() 
{ 
    return (top < 0); 
} 
  
// اختبار الدوال السابقة 
int main() 
{ 
    class Stack s; 
    s.push(10); 
    s.push(20); 
    s.push(30); 
    cout<<s.pop() << " Popped from stack\n"; 
  
    return 0; 
}
  • بايثون:

تحتاج الشيفرة إلى استيراد المتغير maxsize من الوحدة sys وذلك لإعادة القيمة ‎-infinite‎ إن كان المكدس فارغًا: 

from sys import maxsize 

# دالة لإنشاء المكدس وتهيئته ليكون بحجم 0
def createStack(): 
	stack = [] 
	return stack 

# يكون المكدس فارغًا عندما يكون حجمه صفرًا
def isEmpty(stack): 
	return len(stack) == 0

# دالة لإضافة عنصر إلى المكدس، وزيادة حجم المكدس بمقدار 1
def push(stack, item): 
	stack.append(item) 
	print(item + " pushed to stack ") 
	
# دالة لحذف عنصر من المكدس، وإنقاص حجم المكدس بمقدار 1
def pop(stack): 
	if (isEmpty(stack)): 
		return str(-maxsize -1) #تعيد القيمة سالب ما لا نهاية
	
	return stack.pop() 

# اختبار الدوال السابقة
stack = createStack() 
push(stack, str(10)) 
push(stack, str(20)) 
push(stack, str(30)) 
print(pop(stack) + " popped from stack")
  • جافا:
class Stack 
{ 
	static final int MAX = 1000; 
	int top; 
	int a[] = new int[MAX]; // تعيين الحد الأعلى للكدس
    
	boolean isEmpty() 
	{ 
		return (top < 0); 
	} 
	Stack() 
	{ 
		top = -1; 
	} 

	boolean push(int x) 
	{ 
		if (top >= (MAX-1)) 
		{ 
			System.out.println("Stack Overflow"); 
			return false; 
		} 
		else
		{ 
			a[++top] = x; 
			System.out.println(x + " pushed into stack"); 
			return true; 
		} 
	} 

	int pop() 
	{ 
		if (top < 0) 
		{ 
			System.out.println("Stack Underflow"); 
			return 0; 
		} 
		else
		{ 
			int x = a[top--]; 
			return x; 
		} 
	} 
} 

// اختبار الدوال السابقة
class Main 
{ 
	public static void main(String args[]) 
	{ 
		Stack s = new Stack(); 
		s.push(10); 
		s.push(20); 
		s.push(30); 
		System.out.println(s.pop() + " Popped from stack"); 
	} 
}

تعطي الشيفرات السابقة المخرجات التالية:

10 pushed into stack
20 pushed into stack
30 pushed into stack
30 popped from stack

محاسن هذه الطريقة: سهلة التطبيق، ولا تستهلك الكثير من الذاكرة نظرًا لعدم استخدام المؤشرات.

مساوئ هذه الطريقة: غير ديناميكية، ولا تنمو أو تتقلص حسب الحاجة في وقت التشغيل.

تنفيذ المكادس باستخدام القوائم المترابطة

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

  • C++‎:
#include <bits/stdc++.h> 
using namespace std; 

// إنشاء بنية لتمثيل المكدس
class StackNode 
{ 
	public: 
	int data; 
	StackNode* next; 
}; 

StackNode* newNode(int data) 
{ 
	StackNode* stackNode = new StackNode(); 
	stackNode->data = data; 
	stackNode->next = NULL; 
	return stackNode; 
} 

int isEmpty(StackNode *root) 
{ 
	return !root; 
} 

void push(StackNode** root, int data) 
{ 
	StackNode* stackNode = newNode(data); 
	stackNode->next = *root; 
	*root = stackNode; 
	cout<<data<<" pushed to stack\n"; 
} 

int pop(StackNode** root) 
{ 
	if (isEmpty(*root)) 
		return INT_MIN; 
	StackNode* temp = *root; 
	*root = (*root)->next; 
	int popped = temp->data; 
	free(temp); 

	return popped; 
} 

int peek(StackNode* root) 
{ 
	if (isEmpty(root)) 
		return INT_MIN; 
	return root->data; 
} 

int main() 
{ 
	StackNode* root = NULL; 

	push(&root, 10); 
	push(&root, 20); 
	push(&root, 30); 

	cout<<pop(&root)<<" popped from stack\n"; 

	cout<<"Top element is "<<peek(root)<<endl; 

	return 0; 
}
  • بايثون:
# صنف لتمثيل العقدة
class StackNode: 

	# دالة بانية لتهيئة العقدة
	def __init__(self, data): 
		self.data = data 
		self.next = None

class Stack: 
	
	# دالة بانية لتهيئة الجذر الخاص بالقائمة المترابطة 
	def __init__(self): 
		self.root = None

	def isEmpty(self): 
		return True if self.root is None else False

	def push(self, data): 
		newNode = StackNode(data) 
		newNode.next = self.root 
		self.root = newNode 
		print "%d pushed to stack" %(data) 
	
	def pop(self): 
		if (self.isEmpty()): 
			return float("-inf") 
		temp = self.root 
		self.root = self.root.next
		popped = temp.data 
		return popped 
	
	def peek(self): 
		if self.isEmpty(): 
			return float("-inf") 
		return self.root.data 

# اختبار الدوال السابقة
stack = Stack() 
stack.push(10)		 
stack.push(20) 
stack.push(30) 

print "%d popped from stack" %(stack.pop()) 
print "Top element is %d " %(stack.peek())
  • جافا:
public class StackAsLinkedList { 

	StackNode root; 

	static class StackNode { 
		int data; 
		StackNode next; 

		StackNode(int data) { 
			this.data = data; 
		} 
	} 
	
	public boolean isEmpty() { 
		if (root == null) { 
			return true; 
		} else return false; 
	} 
	
	public void push(int data) { 
		StackNode newNode = new StackNode(data); 

		if (root == null) { 
			root = newNode; 
		} else { 
			StackNode temp = root; 
			root = newNode; 
			newNode.next = temp; 
		} 
		System.out.println(data + " pushed to stack"); 
	} 

	public int pop() { 
		int popped = Integer.MIN_VALUE; 
		if (root == null) { 
			System.out.println("Stack is Empty"); 
		} else { 
			popped = root.data; 
			root = root.next; 
		} 
		return popped; 
	} 

	public int peek() { 
		if (root == null) { 
			System.out.println("Stack is empty"); 
			return Integer.MIN_VALUE; 
		} else { 
			return root.data; 
		} 
		
	} 

	public static void main(String[] args) { 
		
		StackAsLinkedList sll = new StackAsLinkedList(); 

		sll.push(10); 
		sll.push(20); 
		sll.push(30); 

		System.out.println(sll.pop() + " popped from stack"); 
	
		System.out.println("Top element is " + sll.peek()); 


	} 

}

تعطي الشيفرات السابقة المخرجات التالية:

10 pushed to stack
20 pushed to stack
30 pushed to stack
30 popped from stack
Top element is 20

محاسن هذه الطريقة: يمكن لهذه الطريقة أن تنمو أو تتقلص حسب الحاجة في وقت التشغيل.

مساوئ هذه الطريقة: تحتاج إلى استخدام جزء أكبر من الذاكرة نظرًا لاستخدام المؤشرات.

إنشاء المكادس باستخدام الأرتال

يمكن استخدام الرتل Queue الذي يدعم عمليات مثل enqueue()‎ و dequeue()‎ لإنشاء المكدس Stack. وتتطلب هذه العملية استخدام طابورين (سنعطيهما الاسمين 'q1' و 'q2') ويمكن تنفيذها بطريقتين:

الطريقة الأولى: الاعتماد على عملية push

تحرص هذه العملية على أن يكون يضاف العنصر الجديد إلى مقدمة الرتل 'q1' وبهذا تزيل عملية pop العناصر من الرتل 'q1'، ويستخدم الرتل 'q2' لوضع كل عنصر جديد في مقدمة الرتل 'q1'.

يمكن تلخيص هذه الطريقة بالخطوات التالية:

  1. العملية push(s, x)‎ حيث تمثل x العنصر المراد إضافته و s المكدس الذي سيضاف العنصر إليه.
    1. إضافة x إلى الرتل q2.
    2. إزالة كل العناصر من الرتل q1 واحدًا تلو الآخر وإضافتها إلى الرتل q2.
    3. تبديل أسماء الرتلين q1 و q2، والهدف من ذلك هو تجنب تحريك جميع العناصر من الرتل q2 إلى q1.
  2. العملية pop(s)‎:
    1. إزالة العنصر من q1 وإعادته.

تعرض الأمثلة التالية طرق إنشاء المكادس باستخدام الأرتال وفي عدد من لغات البرمجة:

  • C++‎:
#include<bits/stdc++.h> 

using namespace std; 

class Stack 
{ 
	// رتلان داخليان 
	queue<int> q1, q2; 
	
	// لمتابعة العدد الحالي للعناصر 
	 curr_size; 

	public: 
	Stack() 
	{ 
		curr_size = 0; 
	} 

	void push(int x) 
	{ 
		curr_size++; 

		// إضافة x إلى الرتل الثاني 
		q2.push(x); 

		// إضافة العناصر الباقية إلى الرتلين
		while (!q1.empty()) 
		{ 
			q2.push(q1.front()); 
			q1.pop(); 
		} 

		// تبديل أسماء الرتلين
		queue<int> q = q1; 
		q1 = q2; 
		q2 = q; 
	} 

	void pop(){ 

		// إن لم يكن هناك أي عنصر في الرتل الأول 
		if (q1.empty()) 
			return ; 
		q1.pop(); 
		curr_size--; 
	} 

	int top() 
	{ 
		if (q1.empty()) 
			return -1; 
		return q1.front(); 
	} 

	int size() 
	{ 
		return curr_size; 
	} 
}; 

// اختبار الدوال السابقة 
int main() 
{ 
	Stack s; 
	s.push(1); 
	s.push(2); 
	s.push(3); 

	cout << "current size: " << s.size() 
		<< endl; 
	cout << s.top() << endl; 
	s.pop(); 
	cout << s.top() << endl; 
	s.pop(); 
	cout << s.top() << endl; 

	cout << "current size: " << s.size() 
		<< endl; 
	return 0; 
}
  • بايثون (ملاحظة: لتعمل هذه الشيفرة في الإصدار 2 من بايثون يجب استخدام الوحدة Queue عوضًا عن queue):
from queue import Queue

class Stack:

    def __init__(self):

        # رتلان داخليان
        self.q1 = Queue()
        self.q2 = Queue()

        # متابعة العدد الحالي من العناصر
        self.curr_size = 0

    def push(self, x):
        self.curr_size += 1

        # إضافة العنصر x إلى الرتل الثاني
        self.q2.put(x)

        # نقل جميع العناصر المتبقية من الرتل الأول إلى الثاني
        while (not self.q1.empty()):
            self.q2.put(self.q1.queue[0])
            self.q1.get()

        # تبديل اسمي الرتلين
        self.q = self.q1
        self.q1 = self.q2
        self.q2 = self.q

    def pop(self):

        # إن لم يكن هناك عناصر في الرتل الأول
        if (self.q1.empty()):
            return
        self.q1.get()
        self.curr_size -= 1

    def top(self):
        if (self.q1.empty()):
            return -1
        return self.q1.queue[0]

    def size(self):
        return self.curr_size

# اختبار الدوال السابقة
if __name__ == '__main__':
    s = Stack()
    s.push(1)
    s.push(2)
    s.push(3)

    print("current size: ", s.size())
    print(s.top())
    s.pop()
    print(s.top())
    s.pop()
    print(s.top())

    print("current size: ", s.size())
  • Java:
import java.util.*; 

class GfG { 

static class Stack 
{ 
	// رتلان داخليان
	static Queue<Integer> q1 = new LinkedList<Integer>(); 
	static Queue<Integer> q2 = new LinkedList<Integer>(); 
	
	// الهدف من هذا المتغير هو متابعة العدد الحالي للعناصر
	static int curr_size; 

	Stack() 
	{ 
		curr_size = 0; 
	} 

	static void push(int x) 
	{ 
		curr_size++; 

		// إضافة العنصر x إلى الرتل الثاني 
		q2.add(x); 

		// نقل بقية العناصر من الرتل الأول إلى الثاني
		while (!q1.isEmpty()) 
		{ 
			q2.add(q1.peek()); 
			q1.remove(); 
		} 

		// تبديل أسماء الرتلين 
		Queue<Integer> q = q1; 
		q1 = q2; 
		q2 = q; 
	} 

	static void pop(){ 

		// إن لم يكن هناك عناصر في الرتل الأول 
		if (q1.isEmpty()) 
			return ; 
		q1.remove(); 
		curr_size--; 
	} 

	static int top() 
	{ 
		if (q1.isEmpty()) 
			return -1; 
		return q1.peek(); 
	} 

	static int size() 
	{ 
		return curr_size; 
	} 
}; 

// تجربة الدوال السابقة 
public static void main(String[] args) 
{ 
	Stack s = new Stack(); 
	s.push(1); 
	s.push(2); 
	s.push(3); 

	System.out.println("current size: " + s.size()); 
	System.out.println(s.top()); 
	s.pop(); 
	System.out.println(s.top()); 
	s.pop(); 
	System.out.println(s.top()); 

	System.out.println("current size: " + s.size()); 
} 
}

تعطي الشيفرات السابقة المخرجات التالية: 

current size: 3
3
2
1
current size: 1

الطريقة الثانية: الاعتماد على عملية pop

يضاف العنصر الجديد دائمًا إلى الرتل q1 في عملية push، وفي العملية pop()‎ إن كان الرتل q2 فارغًا فإنّ جميع العناصر باستثناء العنصر الأخير ستُنقل إلى الرتل q2، ثم يزال العنصر الأخير من الرتل q1 ويعاد.

يمكن تلخيص هذه العملية بالخطوات التالية:

  1. العملية push(s, x)‎:
    1. إضافة x إلى الرتل q1 (على فرض أنّ حجم الرتل q1 غير محدد).
  2. العملية pop(s)‎:
    1. إزالة العناصر واحدًا تلو الآخر باستثناء العنصر الأخير من الرتل q1 وإضافتها غلى الرتل q2.
    2. إزالة العنصر الأخير من الرتل q1 وتخزينه.
    3. تبديل اسمي الرتلين q1 و q2، والهدف من ذلك هو تجنب إجراء عملية نقل جميع العناصر من الرتل q2 إلى q1.
    4. إعادة العنصر المخزن في الخطوة الثانية.

تعرض الأمثلة التالية طرق إنشاء المكادس باستخدام الأرتال وفي عدد من لغات البرمجة:

  • C++‎:
#include<bits/stdc++.h> 
using namespace std; 

class Stack 
{ 
	queue<int> q1, q2; 
	int curr_size; 

	public: 
	Stack() 
	{ 
		curr_size = 0; 
	} 

	void pop() 
	{ 
		if (q1.empty()) 
			return; 
		// ترك عنصر واحد في الرتل الأول ونقل العناصر الباقية إلى الرتل الثاني
		while (q1.size() != 1) 
		{ 
			q2.push(q1.front()); 
			q1.pop(); 
		} 
		
        // حذف العنصر المتبقي من الرتل الأول
		q1.pop(); 
		curr_size--; 

		// تبديل اسمي الرتلين
		queue<int> q = q1; 
		q1 = q2; 
		q2 = q; 
	} 

	void push(int x) 
	{ 
		q1.push(x); 
		curr_size++; 
	} 

	int top() 
	{ 
		if (q1.empty()) 
			return -1; 

		while( q1.size() != 1 ) 
		{ 
		q2.push(q1.front()); 
		q1.pop(); 
		} 
		
		// العنصر المضاف الأخير 
		int temp = q1.front(); 
		
		// إفراغ الرتل الإضافي بعد إجراء آخر عملية
        q1.pop(); 
	
		// إضافة آخر عنصر إلى الرتل الثاني 
		q2.push(temp); 

		// تبديل اسمي الرتلين 
		queue<int> q = q1; 
		q1 = q2; 
		q2 = q; 
		return temp; 
	} 

	int size() 
	{ 
		return curr_size; 
	} 
}; 

// تجربة التوابع السابقة
int main() 
{ 
	Stack s; 
	s.push(1); 
	s.push(2); 
	s.push(3); 
	s.push(4); 

	cout << "current size: " << s.size() 
		<< endl; 
	cout << s.top() << endl; 
	s.pop(); 
	cout << s.top() << endl; 
	s.pop(); 
	cout << s.top() << endl; 
	cout << "current size: " << s.size() 
		<< endl; 
	return 0; 
}

تعطي الشيفرة السابقة المخرجات التالية: 

current size: 4
4
3
2
current size: 2

المصادر

مجلوبة من «https://wiki.hsoub.com/index.php?title=Algorithms/stacks&oldid=28600»