شرح هياكل البيانات _ المكدس stack


هياكل  البيانات في لغة (c++ , java , c ,python)  ربط المكدس

المكدس او التكديس هو عبارة عن هيكلة بيانية تتبع خطوات خاصة اثناء العمليات الحوسبية لتنفيذ برنامج .  ويكون الأمر عبارة  عن الاول يخرج والاخير  يدخل
lifo (last in first out )
 او يكون العكس الاول يدخل  والاخير يخرج
 filo(first  in  last out)
ولتنفيذ هذه العملية يحتاج الى  اربع  خطوات اساسية  تاذي هذا  غرض  التكديس:

  1. عملية الدفع push  ان كانت هذه الحالة التكديس ممتلئ فانه يخضع لخواص overflow فوق التحميل  الزائد 
  2. عملية التفرقع pop  وهي عملية ازالة احد العناصر من المكدس وفي هذه الحالة  تظهل  العناصر عكس عملية الدفع push  في حالة كان التكدس  فارغ empty  فانه يعالج بطريقة Underflow تجاوز الحد الادنى 
  3.   الاختلاس او التوب peek  يقوم باعادة القيم للاعلى العناصر  في التكديس
  4. فراغ 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

Post a Comment

0 Comments