Representation of Stack using Arrays

Representation of Stack using Arrays

 

Declaration 1:

#define size 100

int stack[size], top = ‒1;

• In the above declaration stack is nothing but an array of integers. And most recent index of that array will act as a top.

• The stack is of the size 100. As we insert the numbers, the top will get incremented. The elements will be placed from 0^th position in the stack. At the most we can store 100 elements in the stack, so at the most last element can be at (size ‒1) position, i.e., at index 99.

Declaration 2 :

#define size 10

struct stack

{

       int s[size];

       int top;

}st;

• In the above declaration stack is declared as a structure.

• Now compare declaration 1 and 2. Both are for stack declaration only. But the second declaration will always preferred. Why ? Because in the second declaration we have used a structure for stack elements and top. By this we are binding or co‒relating top variable with stack elements. Thus top and stack are associated with each other by putting them together in a structure. The stack can be passed to the function by simply passing the structure variable.

• We will make use of the second method of representing the stack in our program.

• The stack can also be used in the databases. For example if we want to store marks of all the students of fourth semester we can declare a structure of stack as follows.

#define size 60

typedef struct student

{

   int roll no;

   char name[30];

   float marks;                  

}stud;

stud s1[size];

int top = ‒1;

• The above stack will look like this.

• Thus we can store the data about whole class in our stack. The above declaration means creation of stack. Hence we will write only push and pop function to implement the stack. And before pushing or popping we should check whether stack is empty or full.

Key Point

If top = MAXSIZE means stack full.

 

1. Stack Empty Operation

• Initially stack is empty. At that time the top should be initialized to 1 or 0. If we set top to ‒ 1 initially then the stack will contain the elements from 0^th position and if we set top to 0 initially, the elements will be stored from 1^st position, in the stack. Elements may be pushed onto the stack and there may be a case that all the elements are removed from the stack. Then the stack becomes empty. Thus whenever top reaches to ‒1 we can say the stack is empty.

int stempty ()

{

   if(st.top = = ‒1)

      return 1;

   else

      return 0:

}

Key Point

If top = ‒ 1 means stack empty.

2. Stack Full Operation

• In the representation of stack using arrays, size of array means size of stack. As we go on inserting the elements the stack gets filled with the elements. So it is necessary before inserting the elements to check whether the stack is full or not. Stack full condition is achieved when stack reaches to maximum size of array.

int stfull()

{

   if(st.top > = size ‒1)

      return 1;

   else

      return 0;

}

Thus stfull is a Boolean function if stack is full it returns 1 otherwise it returns 0.

 

3. The 'Push' and 'Pop' Functions

• We will now discuss the two important functions which are carried out on a stack. Push is a function which inserts new element at the top of the stack. The function is as follows.

void push(int item)

{

   st.top++;

   st.s[st.top] =item;

}

• Note that the push function takes the parameter item which is actually the element which we want to insert into the stack ‒ means we are pushing the element onto the stack. In the function we have checked whether the stack is full or not, if the stack is not full then only the insertion of the element can be achieved by means of push operation.

• Now let us discuss the operation pop, which deletes the element at the top of the stack. The function pop is as given below.

• Note that always top element can be deleted.

int pop ()

}

   int item;

   item = st.s[st.top];

   st.top ‒ ‒;

   return (item);

}

• In the choice of pop‒ it invokes the function 'stempty' to determine whether the stack is empty or not. If it is empty, then the function generates an error as stack underflow! If not, then pop function returns the element which is at the top of the stack. The value at the top is stored in some variable as item and it then decrements the value of the top, which now points to the element which is just under the element being retrieved from the stack. Finally it returns the value of the element stored in the variable item. Note that this is what called as logical deletion and not a physical deletion, i.e. even when we decrement the top, the element just retrieved from the stack remains there itself, but it no longer belongs to the stack. Any subsequent push will overwrite this element.

• The push operation can be shown by following Fig. 4.2.5.

The pop operation can be shown by following Fig. 4.2.6.

Key Point

If stack is empty, then we cannot pop and if stack is full we cannot push.

 

4. Stack ADT

• The stack is a data structure which posses the LIFO property. When we declare the structure for stack at that time it gets created. There is no need to write separate function for creation of stack. We can perform push and pop operations on the stack. Before pushing the elements it is necessary to check whether stack is full or not. We cannot push the elements onto the stack if it is full. Similarly before popping the elements we should check whether the stack is empty or not.

AbstractDataType Stack

{

Instances : Stack is a collection of elements in which insertion and deletion of elements is done by one end called top.

Operations

1. Push : By this operation one can push elements onto the stack. Before performing push we should check whether stack is full or not.

2. Pop : By this operation one can remove the elements from stack. Before popping the elements from stack we should check whether stack is empty or not.

}

C++ Program

/**************************************************************************

Program for implementing a stack using arrays.It involves various operations such as push,pop,stack empty,stack full and display.

**************************************************************************/

#include<iostream>

#include<cstdlib>

using namespace std;

#define size 5

/* stack structure*/

class STACK_CLASS

{

private:

struct stack

{

   int s[size];

   int top;

}st;

public:

STACK _CLASS();

int stfull();

void push(int item);

int stempty();

int pop();

void display();

};

//constructor is used to initialise stack

STACK_CLASS::STACK_CLASS()

{

   st.top= ‒1;

   for(int i=0;i<size;i++)

   st.s[i]=0;

}

int STACK_CLASS::stfull()

{

if(st.top> = size‒1)

   return 1;

else

   return 0;

}

void STACK _CLASS::push(int item)

{

   st.top++;

   st.s[st.top] = item;

}

/*

The stempty Function

Input:none

Output:returns 1 or 0 for stack empty or not

Called By:main

Calls:none

*/

int STACK_CLASS::stempty()

{

   if(st.top= = ‒1)

   return 1;

   else

   return 0;

}

int STACK_CLASS::pop()

{

   int item;

   item=st.s[st.top];

   st.top ‒ ‒ ;

   return(item);

}

void STACK_CLASS::display()

{

   int i;

   if(stempty())

   cout<<"\n Stack Is Empty!";

   else

   {

      for(i=st.top;i>=0;i ‒ ‒)

      cout<<"\n"<<<st.s[i];

   }

}

/*

The main Function

Input:none

Output:none

Called By:O.S.

Calls:push,pop,stempty,stfull,display

*/

void main(void)

{

int item,choice;

char ans;

STACK CLASS obj;

clrscr();

cout<<"\n\t\t Implementation Of Stack";

do

{

   cout<<"\n Main Menu";

   cout<<"\n1.Push\n2.Pop\n3.Display\n4.exit";

   cout<<"\n Enter Your Choice: ";

   cin>>choice;

   switch(choice)

   {

      case 1:cout<<"\n Enter The item to be pushed":

            cin>>item;

            if(obj.stfull())

               cout<<"\n Stack is Full!";

            else

               obj.push(item);

            break;

      case 2:if(obj.stempty())

            cout<<"\n Empty stack/Underflow II";

            else

            {

            item=obj.pop();

            cout<<"\n The popped element is "<<item;

            }

            break;

      case 3:obj.display();

            break;

      case 4:exit(0);

}

cout<<"\n Do You want To Continue?";

ans=getche();

} while(ans = =Y ||ans = =y);

getch();

}

/**************** End Of Program *********************/

Output

Implementation Of Stack

Main Menu

1.Push

2.Pop

3.Display

4.exit

Enter Your Choice: 1

Enter The item to be pushed 10

Do You want To Continue?y

Main Menu

1.Push

2.Pop

3.Display

4.exit

Enter Your Choice: 1

Enter The item to be pushed 20

Do You want To Continue?y

Main Menu

1.Push

2.Pop

3.Display

4.exit

Enter Your Choice: 1

Enter The item to be pushed 30

Do You want To Continue?y

Main Menu

1.Push

2.Pop

3.Display

4.exit

Enter Your Choice: 2

The popped element is 30

Do You want To Continue?y

Main Menu

1.Push

2.Pop

3.Display

4.exit

Enter Your Choice: 3

20

10

 

Example: 1

Define an efficient representation of two STACKS in a given area of memory with n words and explain.

OR

Write a set of routines for implementing two stacks within a single array.

Solution :

The two stacks can be adjusted in a single array with n words as shown below ‒

One stack starts at the leftmost end of array and the other at the rightmost end of array. The insertion in stack1 moves top1 to right while insertion in stack2 moves top2 to left. When the stack is full both the top1 and top2 positions are adjacent to each other. The advantage of this location is that every location of the array can be utilized. The implementation routines are ‒

#define MAX 80

class STACK

{

private:

int stack[MAX];

int top1, top2,n,stackno;

public:

      void push(int,int);

      int pop(int);

      STACK();

};

STACK::STACK()//constructor defined for initialization

{

   top1=‒1;

   top2=n;

   stackno=1;

}

void STACK::push(int item, int stackno)

{

if(stackno= =1)

{

   //pushing in stack1/

   if(top1+1==top2)

   cout<<"stack1 is full";

   top++;

   stack[top1] = item; / pushing element /

}

else

{

   if(top2‒1= = top1)

   cout<<"stack2 is full":

   top1‒ ‒; / pushing element in stack2/

   stack[top2]=item;

}

int STACK::pop(int stackno)

{

   int item;

   if(stackno= =1)

   {

      if (top1= = ‒1)

      cout<<"stack1 is empty";

      item=stack[top1];

      top1++;

      return(item);

}

else

{

   if(top2= =MAX)

   cout<<"stack2 is empty";

   item=stack/top2];

   top2‒‒;

   return(item);

}

}

 

Example: 2

Split a stack into two. The first contains bottom half elements and the second contains the remaining elements.

Solution :

#include<iostream>

#include<cstdlib>

using namespace std;

#define size 5

/* stack structure*/

class STACK _CLASS

{

public:

struct stack

{

   int s[size];

   int top;

}st;

STACK CLASS();

int stfull();

void push(int item);

int stempty();

void display();

void split();

};

//constructor is used to initialise stack

STACK_ CLASS::STACK_CLASS()

{

   st.top= ‒1;

   for(int i=0;i<size;i++)

   {

      st.s[i]=0;

   }

}

int STACK_ CLASS::stfull()

{

   if(st.top>=size‒1)

      return 1;

   else

      return 0;

}

void STACK_CLASS::push(int item)

{

   st.top++;

   st.s[st.top] = item;

}

int STACK CLASS::stempty()

{

   if(st.top = = ‒1)

      return 1;

   else

      return 0;

}

void STACK_CLASS::display()

{

   int i;

   if(stempty())

   cout<<"\n Stack Is Empty!";

   else

   {

      for(i=st.top;i>=0;i‒‒)

      cout<<"\n"<<st.s[i];

   }

}

void STACK_CLASS::split()

{

   int i,j,top1,top2;

   int s1[size],s2[size];

   top1=0;

   top2‒st.top/2;

   for(i=0;i<=top2;i++)

   s1[i]=st.s[i];

   int k=0;

   for(j=top2+1;j<=st.top;j++)

   {

      s2[k]=st.s[j];

      k++;

   }

   cout<<"\n\t Content of stack1 are...\n";

   for(i=top1;i<=top2;i++)

   cout<<" "<<s1[i];

   cout<<"\n\t Content of stack2 are...\n";

   for(i=0;i<=k‒1;i++)

      cout<<"  "<<s2[i];

}

void main(void)

{

STACK CLASS obj;

int item,choice;

char ans;

cout<<"\n\t\t Implementation Of Stack";

do

{

   cout<<"\n Main Menu";

   cout<<"\n1.Push\n2.Display\n3.Split\n4.exit";

   cout<<"\n Enter Your Choice: ";

   cin>>choice;

   switch(choice)

   {

      case 1:cout<<"\n Enter The item to be pushed ";

           cin>>item;

           if(obj.stfull())

              cout<<"\n Stack is Fulll";

           else

              obj.push(item);

                break;

   case 2:obj.display();

        break;

   case 3:obj.split();

        break;

   case 4:exit(0);

}

cout<<"\n Do You want To Continue?";

cin>>ans;

}while(ans = ='Y' || ans = ='y');

getch();

}

Output

Implementation Of Stack

Main Menu

1.Push

2.Display

3.Split

4.exit

Enter Your Choice: 1

Enter The item to be pushed 11

Do You want To Continue?y

Main Menu

1.Push

2.Display

3.Split

4.exit

Enter Your Choice: 1

Enter The item to be pushed 22

Do You want To Continue?y

Main Menu

1.Push

2.Display

3.Split

4.exit

Enter Your Choice: 1

Enter The item to be pushed 33

Do You want To Continue?y

Main Menu

1.Push

2.Display

3.Split

4.exit

Enter Your Choice: 3

Content of stack1 are...

11 22

Content of stack2 are...

33

Do You want To Continue?

 

Review Questions

1. Explain the ADT operations for array implementation of stack.

2. Write C++ program to implement stack and its operations PUSH and POP.

3. Explain the operations preformed by stack in detail. Write a C++ program to implement these operations.

4. Write the ADT operation for insertion and deletion routine in stack.