Wednesday, October 20, 2010

Array implementation of stack

Here will discuss the array implementation of stack.

Problems with array implementation
Underflow - Array may be empty but people may try to pop the element
Overflow - Array is full. To over come we have to use re-szing of array. We can see how we can solve this problem here - http://k2code.blogspot.com/2013/09/resizing-array-implementation-of-stack.html
Null items - Can nulls be added - Yes in this case, nulls can be added in stack
Loitering (java specific) - Holding a reference to an object wen it is no longer needed. To over come this we should explicitly set array index to null. For eg.
public string pop() //stack of string
{
  String item = stackArray[--top];
  stackArray[top] = null;
  return item;
}
Doing so, makes your program less of memory consumer.

Stack in java
Following is the implementation of stack in java:
public class MyStack {
   private int maxSize;
   private long[] stackArray;
   private int top;
   public MyStack(int s) {
      maxSize = s;
      stackArray = new long[maxSize];
      top = -1;
   }
   public void push(long j) {
      stackArray[++top] = j;
   }
   public long pop() {
      return stackArray[top--];
   }
   public long peek() {
      return stackArray[top];
   }
   public boolean isEmpty() {
      return (top == -1);
   }
   public boolean isFull() {
      return (top == maxSize - 1);
   }
   public static void main(String[] args) {
      MyStack theStack = new MyStack(10); 
      theStack.push(10);
      theStack.push(20);
      theStack.push(30);
      theStack.push(40);
      theStack.push(50);
      while (!theStack.isEmpty()) {
         long value = theStack.pop();
         System.out.print(value);
         System.out.print(" ");
      }
      System.out.println("");
   }
}
CPP implementation (without classes)
Following is the implementation in cpp:
#include <stdio .h>  
 #include <conio .h>  
 #define MAX 20  
 int top=-1,ch;  
 int a[MAX];  
 int main(){  
   void menu();  
   void push();  
   void pop();  
   void display();  
   menu();  
   while(ch!=3){  
      switch(ch){  
           case 1:  
               push();  
               display();  
               break;  
           case 2:  
               pop();  
               display();  
               break;  
           }  
      menu();       
      }  
 }  
 void push()  
 {  
    if(top==MAX-1)  
     printf("Stack is full\nStack overflow\n");  
    else  
    {  
     printf("Enter element:");  
     scanf("%d",&a[++top]);  
    }  
 }  
 void pop()  
 {  
    if(top==-1)  
    printf("Stack is emplty\nSTACK UNDERFLOW\n");  
    else  
    {  
      top--;  
      printf("Deleted %d\n",a[top+1]);  
    }  
 }  
 void display()  
 {  
    int i=0;  
    printf("\nStack is :\n");  
    for(i=top;i>=0;i--)  
    printf("%d\n",a[i]);  
 }  
 void menu()  
 {  
    printf("\n1.Push\n2.Pop\n3.Exit\n");  
    scanf("%d",&ch);  
    while(ch < 1 ch=>3)  
    {  
     printf("Enter valid choice 1,2 or 3\n");  
     scanf("%d",&ch);  
    }  
 }  


Stack Implementation in CPP (using classes)
#include <iostream>
using namespace std;
#define STACKSIZE 10
class stack
{
        private:
                int arr[STACKSIZE+1];
                int tos;
        public:
                stack();
                void push(int x);
                int  pop();
                bool is_empty();
                bool is_full();
                int  size();
                void display();
};
stack::stack()
{
        tos = 0;
}
void stack::push(int x)
{
        if(!is_full())
                arr[tos++] = x;
        else
                cout << "Stack is full, Can not push " << x << endl;
}
int stack::pop()
{
        if(!is_empty())
                return arr[--tos];
        else
                cout << "Stack is empty, cannot pop" << endl;
        return -1;
}
bool stack::is_empty()
{
        if(tos == 0)
                return true;
        else
                return false;
}
bool stack::is_full()
{
        if(tos == STACKSIZE)
                return true;
        else
                return false;
}
int stack::size()
{
        return tos;
}
void stack::display()
{
        if(tos == 0)
        {
                cout << "No elements to display" << endl;
                return;
        }
        for(int i=0;i
                cout << arr[i] << " ";
        cout << endl;
}
int main()
{
        stack mystack;
        cout << mystack.size() << endl;
        mystack.push(1);
        if(mystack.is_full())
                cout << "stack is full" << endl;
        mystack.pop();
        if(mystack.is_empty())
                cout << "stack is empty" << endl;
}


Thanks.

0 comments:

Post a Comment