Stack

Concept Of Stack

Introduction

   Let us learn the concept of Stack data structure in Computer Science. After that we will discuss about the implementation of Stack in Java and many problems that can be solved using Stack data structure. Finally we will discuss interview questions on Stack that will help you whenever you needed.
    Let us take a scenario. You and some of your nearest friends are hosting a party and you have invited all your friends in it. Every one of hosts have been given a task like welcoming guests, giving their drinks, foods etc.
    You are told to serve plates to every ones table and being an intelligent boy / girl you are doing it efficiently. If you have served all the plates to the guests then you just performed a Stack operation. Have you got the point? If yes then congratulation. If no then it's not a problem I will tell you.
    Say you are carrying plates in your hand and your hand can hold up to 10 plates at a time. So you are picking one plate from the top of the pile of 10 plates on your hand and placing it in front of a guest and so on. When you are out of plates then you are again taking another pile of 10 plates and serving the gusts and so till every one gets one. Notice the plate you are placing on your hand at the first time (i.e. the first plate in the pile) gets picked by you at the last time and the last plate of the pile is on the top of the pile so you will pick the last plate at the first time. So if you call the pile a Stack then no one is going to object you. Because that is correct.

Stack is an important data structure in Computer Science.

Properties

     So we can summarize some it's property from the above discussion.
1. It's a linear data structure.
2. We can add element to the top of the stack. This operation is called PUSH.

    Stack A (initially empty and size 4)
    Now perform push operation on A :       




3. We can remove element from the top of the stack. This operation is called POP.
    Stack A (contains 4 elements 1,2,3&4)

     Now perform POP operation on A

        

4. Element that is PUSHED at first can be POPED at last and that is PUSHED at last can be POPED at first. This property is called Last In First Out (LIFO).
5. You have to mention the size of a stack before declaring it. It's a static data structure.
6. If you try to PUSH more elements than it can hold (i.e. the size) then a situation will arise that is called STACK OVERFLOW.

        
7. If you try to POP an element when it has no element then a situation will arise that is called STACK UNDERFLOW.
   

                 
8. Stack is a recursive data structure. If it's not empty then it contains a Stack Top and the rest part which is a Stack.

Applications

    You must know the applications of Stack in Computer Science. Some innovative solution has been possible because of Stack's LIFO property.
1. It's used to validate mathematical expressions. Compiler's syntax check for matching braces is implemented using stack.
2. In editor undo operations are handled using Stack.
3. If you are solving any problem using Backtracking mechanism then you can use stack.
4. Recursion uses Stack.
5. Space for parameters and local variables is created internally using a stack.