المكدس عبارة عن بنية بيانات خطية تتبع LIFO (آخر ما يدخل أولاً يخرج) مبدأ. المكدس له نهاية واحدة، في حين أن قائمة الانتظار لها طرفان ( الأمامي والخلفي ). أنه يحتوي على مؤشر واحد فقط المؤشر العلوي مشيرا إلى العنصر العلوي من المكدس. كلما تمت إضافة عنصر إلى المكدس، تتم إضافته في الجزء العلوي من المكدس، ولا يمكن حذف العنصر إلا من المكدس. وبعبارة أخرى، أ يمكن تعريف المكدس على أنه حاوية يمكن إجراء الإدراج والحذف فيها من طرف واحد يعرف بالجزء العلوي من المكدس.
بعض النقاط الرئيسية المتعلقة بالمكدس
- يطلق عليه اسم المكدس لأنه يتصرف مثل المكدس في العالم الحقيقي، وأكوام الكتب، وما إلى ذلك.
- المكدس هو نوع بيانات مجردة ذو سعة محددة مسبقًا، مما يعني أنه يمكنه تخزين عناصر ذات حجم محدود.
- إنها بنية بيانات تتبع بعض الترتيبات لإدراج العناصر وحذفها، ويمكن أن يكون هذا الترتيب LIFO أو FILO.
عمل المكدس
يعمل المكدس على نمط LIFO. كما يمكننا أن نلاحظ في الشكل أدناه هناك خمس كتل ذاكرة في المكدس؛ وبالتالي فإن حجم المكدس هو 5.
جافا Localdatetime
لنفترض أننا نريد تخزين العناصر في مكدس ولنفترض أن المكدس فارغ. لقد أخذنا الرصة ذات الحجم 5 كما هو موضح أدناه حيث نقوم بدفع العناصر واحدًا تلو الآخر حتى تمتلئ الكومة.
بما أن مجموعتنا ممتلئة حيث أن حجم المكدس هو 5. في الحالات المذكورة أعلاه، يمكننا أن نلاحظ أنه ينتقل من الأعلى إلى الأسفل عندما كنا ندخل العنصر الجديد في المكدس. يتم ملء المكدس من الأسفل إلى الأعلى.
عندما نقوم بعملية الحذف على المكدس، هناك طريقة واحدة فقط للدخول والخروج حيث أن الطرف الآخر مغلق. وهو يتبع نمط LIFO، مما يعني أن القيمة التي تم إدخالها أولاً ستتم إزالتها أخيرًا. في الحالة المذكورة أعلاه، يتم إدخال القيمة 5 أولاً، لذا لن تتم إزالتها إلا بعد حذف جميع العناصر الأخرى.
عمليات المكدس القياسية
فيما يلي بعض العمليات الشائعة التي يتم تنفيذها على المكدس:
عملية الدفع
الخطوات المتبعة في عملية PUSH موضحة أدناه:
scan.nextstring java
- قبل إدراج عنصر في المكدس، نتحقق مما إذا كانت المكدس ممتلئة.
- إذا حاولنا إدراج العنصر في مكدس، وكانت المكدس ممتلئة، فإن تجاوز تحدث الحالة.
- عندما نقوم بتهيئة المكدس، نقوم بتعيين قيمة الجزء العلوي على -1 للتأكد من أن المكدس فارغ.
- عندما يتم دفع العنصر الجديد في المكدس، أولاً، تتم زيادة قيمة الجزء العلوي، أي: أعلى = أعلى + 1، وسيتم وضع العنصر في الموضع الجديد لل قمة .
- سيتم إدراج العناصر حتى نصل إلى الأعلى حجم المكدس.
عملية البوب
الخطوات المتبعة في عملية POP موضحة أدناه:
- قبل حذف العنصر من المكدس، نتحقق مما إذا كان المكدس فارغًا.
- إذا حاولنا حذف العنصر من المكدس الفارغ، فإن التدفق السفلي تحدث الحالة.
- إذا لم تكن المكدس فارغة، فإننا نصل أولاً إلى العنصر الذي يشير إليه قمة
- بمجرد تنفيذ عملية البوب، يتم تقليل الجزء العلوي بمقدار 1، أي، أعلى = أعلى-1 .
تطبيقات المكدس
فيما يلي تطبيقات المكدس:
int main() { cout<<'hello'; cout<<'javatpoint'; } < pre> <p>As we know, each program has <em>an opening</em> and <em>closing</em> braces; when the opening braces come, we push the braces in a stack, and when the closing braces appear, we pop the opening braces from the stack. Therefore, the net value comes out to be zero. If any symbol is left in the stack, it means that some syntax occurs in a program.</p> <ul> <tr><td>String reversal:</td> Stack is also used for reversing a string. For example, we want to reverse a ' <strong>javaTpoint</strong> ' string, so we can achieve this with the help of a stack. <br> First, we push all the characters of the string in a stack until we reach the null character. <br> After pushing all the characters, we start taking out the character one by one until we reach the bottom of the stack. </tr><tr><td>UNDO/REDO:</td> It can also be used for performing UNDO/REDO operations. For example, we have an editor in which we write 'a', then 'b', and then 'c'; therefore, the text written in an editor is abc. So, there are three states, a, ab, and abc, which are stored in a stack. There would be two stacks in which one stack shows UNDO state, and the other shows REDO state. <br> If we want to perform UNDO operation, and want to achieve 'ab' state, then we implement pop operation. </tr><tr><td>Recursion:</td> The recursion means that the function is calling itself again. To maintain the previous states, the compiler creates a system stack in which all the previous records of the function are maintained. </tr><tr><td>DFS(Depth First Search):</td> This search is implemented on a Graph, and Graph uses the stack data structure. </tr><tr><td>Backtracking:</td> Suppose we have to create a path to solve a maze problem. If we are moving in a particular path, and we realize that we come on the wrong way. In order to come at the beginning of the path to create a new path, we have to use the stack data structure. </tr><tr><td>Expression conversion:</td> Stack can also be used for expression conversion. This is one of the most important applications of stack. The list of the expression conversion is given below: <pre>Infix to prefix Infix to postfix Prefix to infix Prefix to postfix Postfix to infix</pre> </tr><tr><td>Memory management:</td> The stack manages the memory. The memory is assigned in the contiguous memory blocks. The memory is known as stack memory as all the variables are assigned in a function call stack memory. The memory size assigned to the program is known to the compiler. When the function is created, all its variables are assigned in the stack memory. When the function completed its execution, all the variables assigned in the stack are released. </tr></ul> <hr></'hello';>