Algorithms/stacks

المكدس هو من بنى المعطيات الخطية والذي يتبع طريقتين في ترتيب أداء العمليات هما 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

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

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

مصادر

• https://www.geeksforgeeks.org/stack-data-structure-introduction-program/