المكدس في مثال C ++ | برنامج C ++ Stack والخوارزمية

١

المكدس في مثال C ++ | برنامج C ++ Stack هو موضوع اليوم. المكدس هو بنية بيانات تعمل على مبدأ LIFO (Last in first out). في المداخن ، نقوم بإدراج عنصر من جانب واحد كما نقوم بإزالة العناصر من هذا الجانب فقط. المكدس هو محول حاويات عبارة عن فئات تستخدم كائنًا مغلفًا لفئة حاوية معينة ، والتي توفر مجموعة معينة من وظائف الأعضاء للوصول إلى عناصره.

التكديس في C ++

المكدس هو نوع من محولات الحاويات مع نوع عمل LIFO (Last In First Out) ، حيث يتم إضافة العنصر الجديد في نهاية واحدة و (أعلى) تتم إزالة عنصر من هذه النهاية فقط.

في المداخن ، يتم إخراج العناصر التي تم إدخالها في البداية من المكدس في النهاية.

يمكننا استخدام مكدسات في PDA (Push Automata).

 

مطلوب ملف الرأس لاستخدام المكدس في C ++ -

#include<stack>

مع هذا يمكننا استخدام المكدس STL.

وظائف مختلفة مرتبطة بالكومة

empty()

تُرجع الدالة empty() ما إذا كان المكدس فارغًا أم لا.

بناء الجملة

stack_name.empty ()

في هذا ، لا نقوم بتمرير أي معلمة ، وترجع true إذا كانت الحزمة مكتملة أو خاطئة.

Example
stack1 = 1,2,3

stack1.empty();
Output
False

size()

تقوم بإرجاع عدد من العناصر في المكدس.

بناء الجملة

stack_name.size ()

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

Example

stack_1 = 1,2,3,4,5
stack_1.size();

Output

5

top()

تقوم بإرجاع مرجع إلى العنصر الأعلى من المكدس.

بناء الجملة

stack_name.top () ،

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

Example

stack_name.push(5);
stack_name.push(6);
stack_name.top();

Output

6

push(k)

يتم استخدام وظيفة push () لإدخال العناصر في المكدس.

يضيف العنصر 'k' في الجزء العلوي من المكدس.

بناء الجملة

stack_name.push (القيمة)

في هذا ، نقوم بتمرير القيمة كمعلمة ، ونتيجة لذلك ، إضافة العنصر إلى المكدس.

Example

stack1.push(77)
stack1.push(88)

Output

77, 88

 pop()

يقوم بحذف العنصر الأعلى من المكدس.

بناء الجملة

stack_name.pop ()

في هذا ، لا نقوم بتمرير أي معلمة تبرز هذه الوظيفة العنصر الأعلى من المكدس.

Example

stack1 = 10,20,30;  
stack1.pop();

Output

10, 20

الأخطاء والاستثناءات

1. يظهر خطأ إذا تم تمرير معلمة.
2. يظهر أي استثناء رمي الضمان.

C ++ خوارزمية المكدس

في الخوارزميات المتعلقة بالكومة ، تبدأ النقطة TOP في البداية 0 ، ويبدأ فهرس العناصر في الرصة من 1 ، وفهرس العنصر الأخير هو MAX

.INIT_STACK (STACK, TOP)

    Algorithm to initialize a stack using array. 
    TOP points to the top-most element of stack.

    1) TOP: = 0;
    2) Exit

تُستخدم عملية push() لإدراج عنصر في المكدس.

    PUSH_STACK(STACK,TOP,MAX,ITEM)

    Algorithm to push an item into stack.
            
    1) IF TOP = MAX   then
    Print “Stack is full”;
    Exit;
    2) Otherwise
    TOP: = TOP + 1;        /*increment TOP*/
    STACK (TOP):= ITEM;
    3) End of IF
    4) Exit

تُستخدم عملية pop () لحذف العنصر من المكدس ، والحصول أولاً على عنصر ثم تقليل المؤشر TOP.

    POP_STACK(STACK,TOP,ITEM)

    Algorithm to pop an element from stack.

    1) IF TOP = 0 then
        Print “Stack is empty”;
        Exit;
    2) Otherwise
        ITEM: =STACK (TOP);
        TOP:=TOP – 1;
    3) End of IF
    4) Exit

    IS_FULL(STACK,TOP,MAX,STATUS)

    Algorithm to check stack is full or not. 
    STATUS contains the result status.

    1) IF TOP = MAX then
        STATUS:=true;
    2) Otherwise
        STATUS:=false;
    3)  End of IF
    4)  Exit

    IS_EMPTY(STACK,TOP,MAX,STATUS)

    Algorithm to check stack is empty or not.
    STATUS contains the result status.

            
    1) IF TOP = 0 then
        STATUS:=true;
    2) Otherwise
        STATUS:=false;
    3)  End of IF
    4)  Exit

برنامج C ++ Stack

Q1- اكتب برنامجًا لإدراج خمسة عناصر في المكدس واطبع العنصر العلوي باستخدام top () واطبع حجم المكدس وتحقق مما إذا كان المكدس فارغًا أم لا.

#include <iostream>
#include <stack>

using namespace std;

int main()
{
  stack<int> stack1; //empty stack of integer type
  stack1.push(100);
  stack1.push(200);
  stack1.push(300);
  stack1.push(400);
  stack1.push(500);

  cout << "The topmost element of the stack is:" << stack1.top() << endl;
  cout << "The size of the stack is=" << stack1.size() << endl;

  if (stack1.empty())
  {
    cout << "Stack is empty" << endl;
  }
  else
  {
    cout << "Stack is not empty" << endl;
  }
}

انظر الإخراج.

 

Q2- كتابة برنامج لإدراج 5 عناصر في المكدس وحذف عنصرين ثم طباعة المكدس.

#include <iostream>
#include <stack>

using namespace std;

int main()
{
  stack<int> stack1; //empty stack of integer type
  stack1.push(100);
  stack1.push(200);
  stack1.push(300);
  stack1.push(400);
  stack1.push(500);

  stack1.pop();
  stack1.pop();

  while (!stack1.empty())
  {
    cout << "Element =" << stack1.top() << endl;
    stack1.pop();
  }
}

انظر الإخراج.

 

تطبيقات المكدس

1. تحويل تدوينات البولندية
   هناك ثلاثة أنواع من الترميزات:
   1) Infix notation  - عامل بين المعاملات: x + y
   2) Prefix notation - عامل قبل المعاملات: + xy
   3) Postfix notation  - عامل بعد المعاملات: xy +
   
2. لعكس  : سلسلة يمكن عكس سلسلة باستخدام المكدس. تم دفع أحرف السلسلة إلى المكدس حتى نهاية السلسلة. برزت الشخصيات وعرضها. نظرًا لأنه يتم دفع الحرف النهائي للسلسلة ، فسيتم طباعته أولاً.
3. عندما يتم استدعاء وظيفة (البرنامج الفرعي) عند استدعاء
   الوظيفة ، تسمى الوظيفة الأخيرة سيتم إكمالها أولاً. إنها خاصية المكدس. توجد منطقة ذاكرة محجوزة خصيصًا للمكدس.

استنتاج

المكدس هو بنية بيانات مجردة تحتوي على مجموعة من العناصر.

يقوم المكدس بتطبيق آلية LIFO ، أي أن العنصر الذي يتم دفعه في النهاية يتم بروزه أولاً. 

أخيرًا ، المكدس في مثال C ++ | C ++ Stack Program And Algorithm قد انتهى.