Unit III

Stack and Queue

Stack is a list of elements in which insertion and deletion of elements can be done only at one end called as top of stack.

To construct a stack we insert element from top of stack.

The operation of inserting an element to stack is called as push and the operation of deleting an element from a stack is called as pop.

Imagine stacking a set of books on top of each other, we can push a new book on top of the stack, and we can pop the book that is currently on the top of the stack.

We cannot add to or remove the book from middle of the stack.

Book can only be added to the top and the only book that can be taken out of the stack is the most recently added one; Thus stack is a "Last In First Out" (LIFO) data structure.

An ADT is a collection of data and associated operations for manipulating that data. Stack ADT contains following data members

and member functions.

Data members:   1. top: Index of top of stack.

   2. A[size]: Array to hold elements of stack:

Member Functions:

2.     What is Basic Operations on Stack?

There are three fundamental operations on stack.

Push: Insert element to the stack

Pop: Delete element from stack

Peek: Returns element at the top of stack

We will see these operations with respect to an example.

Here we assume stack size is 3.

Initially stack is empty. If pop operation is called on empty stack then stack underflow occurs.

----- (empty stack)

Push element ‘7’ to the stack. Then stack becomes

| 7 |     <-- top

-----

Push element ‘2’ to the stack. So new top of stack is 2.

| 2 | <-- top

| 7 |

     -----

Push element ‘10’ to the stack. Now top of stack becomes 10.

|10 | <-- top

| 2 |

| 7 |

-----

Now the stack becomes full as we are assuming stack size is 3. If we insert one more element onto stack then stack overflow occurs.

 Pop element from stack. Element 10 is popped out. Hence new top is 2.

| 2 | <-- top

| 7 |

-----

Since Stack is LIFO data structure element inserted most recently will be popped out first.

Pop element 2 from stack. Hence new top is 7.

| 7 | <-- top

-----

Pop element 7 from stack. Now stack becomes empty. 

----- (empty stack)

3.     What is insertion and removal element in stack?

Insert element in Stack: push()

Remove element from stack: pop()

4.     Check if the stack is empty and Check if the stack is full

Check if the stack is empty: isEmpty()

 Check if the stack is full: isFull()

#include<iostream.h>

# define int MAX 100

template< class TYPE > //class template

class Stack {

   int count;  //number of elements present in stack

   TYPE A[Max];  // Array of size MAX

   TYPE out;  

   int top;  // index of top of stack

public:

   Stack(int MAX); 

   ~Stack();

   bool push(TYPE);

   TYPE pop();

   bool isEmpty();

   bool isFull();

   int stackcount();

   void display();

};

template< class TYPE >  //constructor to create stack

Stack< TYPE >::Stack(int MAX)

{

   count=0;

   top = -1;

}

template< class TYPE >  //destructor to remove stack

Stack< TYPE >::~Stack()

{  delete[] A;

   count=0; 

   MAX=0; 

   top=-1;

 }

template< class TYPE>// function to push elements in stack

void Stack< TYPE >::push(TYPE in)

{

if(count>=MAX)

cout<<”stack overflow”

count++;

top++;

A[ top ] = in;   //copy data to top of stack

}

template< class TYPE >    // Function to pop elements from stack

TYPE Stack< TYPE >::pop()

{  return A[ top-- ];

   count--;

 }

template< class TYPE> //Function to check if stack is full

int Stack< TYPE>::isFull()

{ 

return (count == Max);

}

template< class TYPE> //Function to check if stack is empty

int Stack< TYPE>::isEmpty()

{ 

return (count == 0);

}

template< class TYPE>

int Stack< TYPE>::stackcount()

{ 

return count;

}

template< class TYPE>  //Function to display stack elements

void Stack<TYPE>::display()

{

if(top<0)

cout<<”stack empty”;

for(int i=top;i>=0;i--)

cout<<A[i]<<” ”;

}

void main()

{

int choice,data;

Stack<int> S;  //create stack of integers

while(1)

{

cout<<”Enter choice for operation”;

cout<<”\t 1.PUSH”<<endl;

cout<<”\t 2.POP”<<endl;

cout<<”\t 3.ISFULL”<<endl;

cout<<”\t 4.ISEMPTY”<<endl;

cout<<”\t 5.Stackcount”<<endl;

cout<<”\t 6.Display”<<endl;

cin>>choice;

switch(choice)

{

case 1:

cout<<”Enter element to be pushed”;

cin>>data

 S.push(data);

break;

case 2:

out=S.pop();

cout<<”Popped element is”<<out;

break;

case 3:

int flag=S.isFull();

if(flag=1)

cout<<”stack is full”;

else

cout<<”stack is not full”;

break;

case 4:

int flag=S.isEmpty();

if(flag=1)

cout<<”stack is empty”;

else

cout<<”stack is not empty”;

break;

case 5:int c=S.stackcount();

cout<<”Stack count is”<<c;

break;

case 6: S.display();

break;

} //end of switch

} //end of while

} //end of program

6.     What is reversing data?

Data reversing is a technique of reordering data elements  so that first element becomes last, second element becomes last but one and so on. Consider array A

A=

Fig. Original Array

After reversing array becomes

A=

Algorithm to reverse list of integers is as follows.

Another application of reversing data is conversion of decimal number to binary number. Algorithm for conversion of decimal to binary number is as follows.

7.     Write a Program to convert decimal number to binary number

#include <iostream>

#include <stdio.h>

#include <conio.h>

using namespace std;

struct Node  

{

    int value;

    Node *next;

}*top = NULL, *P = NULL, *temp = NULL;

int x;

void push(int P) 

{

    temp = new Node;

    temp->value = P;

    temp->next = NULL;

    if (top == NULL)

    {

        top = temp;

    }

    else

    {

        temp->next = top;

        top = temp;

    }

}

int pop()

{

    if (top == NULL)

    {

        cout<<"underflow\n";

    }

    else

    {

        P = top;

        top = top->next;

        x = P->value;

        delete(P);

        return(x);

    }

}

void main()

{

    int num, a;

    cout<<"enter the decimal number\n";

    cin>>num;

    while (num > 0)

    {

        a = num % 2;

        num = num / 2;

        push(a);

    }

    P = top;

    cout<<"resultant binary no:";

    while(1)

    {

        if (top != NULL)

     cout<<pop()<<"\t";

 else

     break;

    }

    getch();

}

Evaluate the following prefix expression using stack for A= 16, B= 2, C=3, D=10, and E=4.Prefix Expression is

-+/A^BC*DE*AC 

Hence final result is -6.

9.     Write a program for prefix expression evaluation.

#include <iostream.h>
#include <conio.h>
#include <stdio.h>
#include <math.h>
#include <string.h>
template <class TYPE>  //class template
class stack
{
private:
  TYPE *a;
   int top,max;

public:
  stack()
   {
    max = 50;
    a = new TYPE[max];
    top = 0;
   }

   stack(int n) 
   {
    max = n + 1;
    a = new TYPE[max];
    top= 0;
   }
~stack()
   {
    delete a;
   }
   friend void push(stack &,TYPE); // member functions for stack
   friend TYPE pop(stack &);
   friend int isEmpty(stack);
};

template <class TYPE>
void push(stack <TYPE> &s, TYPE x)
{
if(s.top != s.max)
  {
    s.top++;
    s.a[s.top] = x;
   }

else
cout << "\nStack Overflow.";
}

template <class TYPE>
TYPE pop(stack <TYPE> &s)
{
TYPE temp;
if(s.top != 0)
  {
   temp = s.a[s.top];
    s.top--;
    return temp;
   }

else
  {
temp = -999;
   return temp;
  }
}

template <class TYPE>
int isEmpty(stack <TYPE> s)
{
if(s.top == 0)
return 1;

else
  return 0;
}

int main()
{
char prefix[30],b[2];  
int i = 0;
float e;
cout << "Enter a Prefix Expression,\n";
prefix[i - 1] ='\0';
while(prefix[i-1] != '\n')
  prefix[i++] = getchar(); // prefix expression

stack <float> O(50); //call constructor to create stack
float value,operand1,operand2;

int j = i - 2,pos,k;
while(j >= 0)
  {
    pos = 0;
    if(prefix[j] >= '0' && prefix[j] <= '9')
     {
       b[0] = prefix[j]; // Save Prefix[j] to b
       i = j - 1;
       k = 1;
       if(prefix[j-1] != ' ') //Check for next character, If not Space
        {
         while(prefix[i] != ' ') //While space is not found
          {
       b[k++] = prefix[i--]; //Save Prefix[i] to b
           pos++; //Increase Position
          }
         pos += 2;//At Last Increase Position by 2 to Skip Space
        }

       else //If a Single Character
        pos = 2; //Skip Space

       b[k] = '\0'; //End String temp
       strrev(b);
       x = atof(b); //Convert string b to float and store to x
       push(O,x); //Push to stack
      }

   else if(prefix[j] == '+' || prefix[j] == '-' || prefix[j] == '*' || prefix[j] == '/' || prefix[j] == '^' )              // check for operators
     {
       operand1 = pop(O);
       if(operand1 == -999)
        break;

       if(prefix[j] == '+' || prefix[j] == '-' || prefix[j] == '*' || prefix[j] == '/' || prefix[j] == '^')
        {
          operand2 = pop(O);
          if(operand2 == -999)
         break;
          }

       if(prefix[j] == '+')
         value = operand1 + operand2;

       if(prefix[j] == '-')
        value = operand1 - operand2;

       if(prefix[j] == '*')
        value = operand1 * operand2;

       if(prefix[j] == '/')
        {
        if(operand2 != 0)
         value = operand1 / float(operand2); //Cast one operand to float
         else
          {
           cout << "\nError ! Cannot Divide by Zero";
             getch();
             return 0;
            }
        }

       if(prefix[j] == '^')
         value = pow(operand1,operand2);

      push(O,value);
       pos = 2;
    }

   else
     {
    cout << "\nError : Illegal Character";
      getch();
      return 0;
     }

   j -= pos;
  }

float output = pop(O);
if(output == -999 || !isEmpty(O)) //If Underflow Condition or stack is not empty,
  {
   cout << "\nError : The Given Prefix Expression is Not Valid.";
   getch();
   return 0;
  }

else
  cout << "\nOutput = " << Output;

getch();
return 0;
}

10.  What is ADT of Queue?

A Queue is a linear list in which data is inserted at one end called as rear and deleted from other end called as front. Queue removes elements in the same order in which they were inserted i.e. element inserted first is removed first. Hence they are called as First-in-First out( FIFO) data structure.

Imagine a queue of people waiting for a bus. The person in the front of queue will get a first chance to board a bus. The person at the rear will be last one to board a bus. Same case is of check out line in a grocery store or a cafeteria, list of jobs to be processed by computer or a list of calls on mobile phone.Fig.1 shows queue of alphabets. Alphabets are added at rear and removed from front end.

       Fig 1. Queue of alphabets

We will see queue with respect to an example. Imagine queue of alphabets with size of three. Initially queue is empty.

Now let us add an element in a queue. So queue becomes

Add one more element ’B’ in a queue. Since element can only be inserted at rear, A progresses through queue and B is inserted at rear. Now queue becomes

Adding one more element ‘C’ in queue

Now queue is full. If we try to insert one more element in queue then queue overflow occurs.

Now remove elements from queue. Element in queue is always removed from front end. Currently ‘A’ is at front end and hence will be removed first.

Removing ‘B’ and ‘C’ we get

Now queue is empty. If we try to remove elements from queue, queue underflow occurs.

Operations on Queue:

bool enqueue(TYPE in): Insert elements at rear of queue.

bool dequeue(TYPE  & out): Remove elements from front of queue.

bool Front(TYPE& out): Determines element at the front of queue.

bool Rear(TYPE& in): Determines element at the rear of queue.

int Count():Determines total number of elements present in queue.

bool isEmpty():Determines if queue is empty.

bool isFull():Determines if queue is full.