هياكل البيانات في لغة (c++ , java , c ,python) ربط المكدس
المكدس او التكديس هو عبارة عن هيكلة بيانية تتبع خطوات خاصة اثناء العمليات الحوسبية لتنفيذ برنامج . ويكون الأمر عبارة عن الاول يخرج والاخير يدخل
lifo (last in first out )
او يكون العكس الاول يدخل والاخير يخرج
filo(first in last out)
ولتنفيذ هذه العملية يحتاج الى اربع خطوات اساسية تاذي هذا غرض التكديس:
- عملية الدفع push ان كانت هذه الحالة التكديس ممتلئ فانه يخضع لخواص overflow فوق التحميل الزائد
- عملية التفرقع pop وهي عملية ازالة احد العناصر من المكدس وفي هذه الحالة تظهل العناصر عكس عملية الدفع push في حالة كان التكدس فارغ empty فانه يعالج بطريقة Underflow تجاوز الحد الادنى
- الاختلاس او التوب peek يقوم باعادة القيم للاعلى العناصر في التكديس
- فراغ isEmpty يعيد قيمة فارغة للتكديس وتكون في حالة صح true وعكسها تكون القيمة خطأ false
مثال للتكديس في ارض الواقع :
هناك الكثير من الأمثلة للتكديس في ارض الواقع لناخذ على سبيل المثال لوحات الرسام عندما تكون مكدسة في سندوق واحدة فوق الاخرى فان اخر لوحة وضعة في الصندوق هي اول من يتم اخراجها واخر لوحة يتم اخراجها من الصندوق تكون هي اول من تم وضعها وهذا هو مفهوم (lifo/filo).
مثال برمجي :
استخدام المصفوفات array
c++ language:
/* C++ program to implement basic stack
operations */
#include<bits/stdc++.h>
using namespace std;
#define MAX 1000
class Stack
{
int top;
public:
int a[MAX]; //Maximum size of Stack
Stack() { top = -1; }
bool push(int x);
int pop();
bool isEmpty();
};
bool Stack::push(int x)
{
if (top >= MAX)
{
cout << "Stack Overflow";
return false;
}
else
{
a[++top] = x;
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);
}
// Driver program to test above functions
int main()
{
struct Stack s;
s.push(10);
s.push(20);
s.push(30);
cout << s.pop() << " Popped from stack\n";
return 0;
}
======
Java Language:
/* Java program to implement basic stack
operations */
class Stack
{
static final int MAX = 1000;
int top;
int a[] = new int[MAX]; // Maximum size of Stack
boolean isEmpty()
{
return (top < 0);
}
Stack()
{
top = -1;
}
boolean push(int x)
{
if (top >= MAX)
{
System.out.println("Stack Overflow");
return false;
}
else
{
a[++top] = x;
return true;
}
}
int pop()
{
if (top < 0)
{
System.out.println("Stack Underflow");
return 0;
}
else
{
int x = a[top--];
return x;
}
}
}
// Driver code
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");
}
}
======
C programing language :
// C program for array implementation of stack
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
// A structure to represent a stack
struct Stack
{
int top;
unsigned capacity;
int* array;
};
// function to create a stack of given capacity. It initializes size of
// stack as 0
struct Stack* createStack(unsigned capacity)
{
struct Stack* stack = (struct Stack*) malloc(sizeof(struct Stack));
stack->capacity = capacity;
stack->top = -1;
stack->array = (int*) malloc(stack->capacity * sizeof(int));
return stack;
}
// Stack is full when top is equal to the last index
int isFull(struct Stack* stack)
{ return stack->top == stack->capacity - 1; }
// Stack is empty when top is equal to -1
int isEmpty(struct Stack* stack)
{ return stack->top == -1; }
// Function to add an item to stack. It increases top by 1
void push(struct Stack* stack, int item)
{
if (isFull(stack))
return;
stack->array[++stack->top] = item;
printf("%d pushed to stack\n", item);
}
// Function to remove an item from stack. It decreases top by 1
int pop(struct Stack* stack)
{
if (isEmpty(stack))
return INT_MIN;
return stack->array[stack->top--];
}
// Driver program to test above functions
int main()
{
struct Stack* stack = createStack(100);
push(stack, 10);
push(stack, 20);
push(stack, 30);
printf("%d popped from stack\n", pop(stack));
return 0;
}
=======
Python language :
# Python program for implementation of stack
# import maxsize from sys module
# Used to return -infinite when stack is empty
from sys import maxsize
# Function to create a stack. It initializes size of stack as 0
def createStack():
stack = []
return stack
# Stack is empty when stack size is 0
def isEmpty(stack):
return len(stack) == 0
# Function to add an item to stack. It increases size by 1
def push(stack, item):
stack.append(item)
print("pushed to stack " + item)
# Function to remove an item from stack. It decreases size by 1
def pop(stack):
if (isEmpty(stack)):
return str(-maxsize -1) #return minus infinite
return stack.pop()
# Driver program to test above functions
stack = createStack()
push(stack, str(10))
push(stack, str(20))
push(stack, str(30))
print(pop(stack) + " popped from stack")
بطبيعة الحال ستكون النتيجة كالتالية
10 pushed to stack
20 pushed to stack
30 pushed to stack
30 popped from stack
Top element is 20
مثال باستخدام القوائم المرتبطة:
لغة السي :
// C program for linked list implementation of stack
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
// A structure to represent a stack
struct StackNode
{
int data;
struct StackNode* next;
};
struct StackNode* newNode(int data)
{
struct StackNode* stackNode =
(struct StackNode*) malloc(sizeof(struct StackNode));
stackNode->data = data;
stackNode->next = NULL;
return stackNode;
}
int isEmpty(struct StackNode *root)
{
return !root;
}
void push(struct StackNode** root, int data)
{
struct StackNode* stackNode = newNode(data);
stackNode->next = *root;
*root = stackNode;
printf("%d pushed to stack\n", data);
}
int pop(struct StackNode** root)
{
if (isEmpty(*root))
return INT_MIN;
struct StackNode* temp = *root;
*root = (*root)->next;
int popped = temp->data;
free(temp);
return popped;
}
int peek(struct StackNode* root)
{
if (isEmpty(root))
return INT_MIN;
return root->data;
}
int main()
{
struct StackNode* root = NULL;
push(&root, 10);
push(&root, 20);
push(&root, 30);
printf("%d popped from stack\n", pop(&root));
printf("Top element is %d\n", peek(root));
return 0;
}
لغة البايثون :
# Python program for linked list implementation of stack
# Class to represent a node
class StackNode:
# Constructor to initialize a node
def __init__(self, data):
self.data = data
self.next = None
class Stack:
# Constructor to initialize the root of linked list
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
# Driver program to test above class
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())
بطبيعة الحال ستكون النتيجة كالتالي :
10 pushed to stack
20 pushed to stack
30 pushed to stack
30 popped from stack
Top element is 20
0 تعليقات