Wednesday, 24 February 2016

Stack

What is Stack ?
According to an English dictionary it means: 
A pile of objects, typically one that is neatly arranged.

Same is the case in Computer programming.
What Is Stack In Computer Science perspective?
Stack is an abstract data that contains set of elements, it follows two principles PUSH to add an element and POP to remove an element.

Operation Of Stack In Real Life:
Assume a box open from the top. We take some books and stack them one on the other inside the box until the box is having no space left. The closed end is your front end and opening is your rear end. Just as a cargo plane, you load things up in the rear of the plane. Got it? It is easy right? You just have to think of stacking in this box like you do in a cargo plane. 
Cockpit of cargo plane = Front end of box

Back door of cargo plane = Rear end of the box
In naive words, you are filling the box from the rear end.

Now when you put the first book, it will be near to the cockpit of a plane, or the front end of the box. If you want to remove the stacked books, there is always a way. If you have already guessed it, call yourself a genius!
This is how books will be Inside the Box
This is the Box Filled with books
         
The book near the back door of the cargo plane will be the first one to get removed. Moreover, the book close to the cockpit will be the last one to get removed. If we think in a box, the book near to the front end will be the last one to get removed, however, the book near to the rear end will be the first one to get removed.

This is known as: First in Last Out or Last In First Out. This is what happens in Stack ,it follows these two which is in fact one phenomenon.

Operation Of Stack In Programming :
Consider an Array and and start placing elements in it, now Imagine it like the box now at initial position when we first enter an element it will go to 0 index then 1 ,then 2 and so on, you can see that the first one that we input was placed was placed in the bottom of array . When it comes time to remove the element which was placed in the end will be the first one to be removed and element placed first will be the last one to be removed i.e. " First in Last Out" or "Last In First Out".






Now here you  see some new things "TOP" ,"PUSH" and"POP". What are these ?
These are the functions that are made to control input and output of stack .

PUSH
PUSH is the Function from which element will be added.

POP
POP is the Function at which element will be removed.

TOP
TOP is the last element inserted.

At Initial stage POP,PUSH and TOP will be on the same index "0" when we first insert an element through PUSH ,it will be inserted at 0 and an increment in index will be done and position of TOP will be "0" then the next element will be inserted at Index "1" and position of TOP will be "1".
Now its turn to remove,we will call POP function it will remove the element in the end or you may say element at the TOP and decrements in the index will be done Now after decremented Position Of TOP will be index "0" and position to input new element will be "1", So here we can see a relation that what ever element we enter is inserted at TOP+1.

Visualization of Stack operation
Now Lets Have A look At its Code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include<iostream>
using namespace std;

#define size 5  

int array[size];

int TOP=-1; //Top is set to -1 because at initial stage no element is present so it is kept -1 
            //so that on insertion of first element it become 0 and so on
            
void PUSH(int x)
{
      if(TOP+1==size)     //this condion will check if stack is FULL or not in case it is Full it will display the error 
         cout<<"Stack Is FULL No More Input Possible";
         else 
        {   array[TOP+1]=x;
          TOP++;  //TOP=TOP+1;
        }
 
}
void POP()
{
 cout<<"ELEMENT REMOVED: "<<array[TOP]<<endl<<endl;
 
 TOP--;  //TOP=TOP-1;
 
}
void top()
{
 
 cout<<"Element in The End : "<<array[TOP]<<endl<<endl;
}
void Display()
{
 cout<<"Elements In The Array : "<<endl<<endl;
 
 for(int i=0;i<=TOP;i++)
 {
  cout<<array[i]<<"  ";
 }
 cout<<endl<<endl;
 
}

int main()
{
 Display();  //Display called to see how many elements are there definatly at this stage there will be no elements
 
 PUSH(3);    // 3 will be inserted at 0 index
 
 Display;    // now on this Time Call of display one element will be shown as only one element is inserted

 PUSH(5); //  5 will be inserted at 1 index
 
 Display();  // now on this Time Call of display two element will be shown 
 
 PUSH(6);   // 6 will be inserted at 2 index
 
 Display();   // now on this Time Call of display three element will be shown 
 
 top();       // 6 will be displayed as the last element inserted was 6
 
 POP();        // 6 will be removes as the element in the last will be 6
 
 Display();    // now on this Time Call of display twp element will be shown as one element has been removed
 
 top();         // 5 will be removes as the element in the last will be 6
 
  
}

Now lets Implement this with Class (Only for those who know about Classes):

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include<iostream>
using namespace std;

class stack
{ private:
  int size;    
  int *array;
  int TOP; //Top is set to -1 because at initial stage no element is present so it is kept -1 
            //so that on insertion of first element it become 0 and so on
  public:
     stack(int tempsize) //constructor
  {
   size=tempsize;    //size will be assigned at the time of construction of object
   array=new int [size]; //we use "New" when we have to determine the array size on runtime
   TOP=-1;
   
  }         
   void PUSH(int x)
  {
      if(TOP+1==size)     //this condion will check if stack is FULL or not in case it is Full it will display the error 
         cout<<"Stack Is FULL No More Input Possible";
         else 
        {   array[TOP+1]=x;
          TOP++;  //TOP=TOP+1;
        }
 
  }
  
   void POP()
  {
     cout<<"ELEMENT REMOVED: "<<array[TOP]<<endl<<endl;
 
     TOP--;  //TOP=TOP-1;
 
  }
  
   void top()
   {
 
 cout<<"Element in The End : "<<array[TOP]<<endl<<endl;
   }
   void Display()
  {
 cout<<"Elements In The Array : "<<endl<<endl;
 
 for(int i=0;i<=TOP;i++)
 {
  cout<<array[i]<<"  ";
 }
 cout<<endl<<endl;
 
  }
};

int main()
{
 stack obj(5);//argument is passed to the constructor as the size of array
 
    obj.Display();  //Display called to see how many elements are there definatly at this stage there will be no elements
 
 obj.PUSH(3);    // 3 will be inserted at 0 index
 
 obj.Display();    // now on this Time Call of display one element will be shown as only one element is inserted

 obj.PUSH(5); //  5 will be inserted at 1 index
 
 obj.Display();  // now on this Time Call of display two element will be shown 
 
 obj.PUSH(6);   // 6 will be inserted at 2 index
 
 obj.Display();   // now on this Time Call of display three element will be shown 
 
 obj.top();       // 6 will be displayed as the last element inserted was 6
 
 obj.POP();        // 6 will be removes as the element in the last will be 6
 
 obj.Display();    // now on this Time Call of display twp element will be shown as one element has been removed
 
 obj.top();         // 5 will be removes as the element in the last will be 6
 
  
}



Edited by Zain Ul Mustafa on 26 Febuary 2016 at 11:45 pm
Written by at
Labels: , , , ,

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)