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.

Read More

Stack implementation using linked list

We will be understanding the stack implementation using linked list. So, please understand the link list before proceeding.

Lets understand how we can implement the different operation using linked list.

CPP implementation
Here is how we use linked list to implement stack in cpp:

#include <iostream>

using namespace std;

struct node
{
       int info;
       struct node *next;

};

struct node *top;

int empty()
{
    return((top == NULL)? 1:0);
}

void push(int n)
{
     struct node *p;
     p=new node;
     if(p!=NULL)
     {
                p->info=n;
                p->next=top;
                top=p;
     }
     else
         cout<<"Not inserted,No memory available";
}

int pop()
{
    struct node *temp;
    int x;
    x=top->info;
    temp=top;
    top=top->next;
    free(temp);
    return(x);
}

void print()
{

     int i =0;
     struct node * temp;
     temp = top;
     cout<<"\n\t\t";
     if(temp==NULL)
          cout<<"\n\t\tNo elements\n";
     else
     {
         while(temp!=NULL)
         {
              int info = temp->info;
              cout<info<<"  ";
              temp=temp->next;
         }

         cout<<"End of List<<"\n";
      }
}

Implementation in java

Here is the implementation in java

class ListNode<E>
{
    E data;
    ListNode<E> next;
}
public class Stack<E>
{
    private ListNode<E> m_head;
 
    public Stack () {
        m_head = null;
    }
 
    public void push (E n) {
        ListNode<E> tmp = getNewNode();
        tmp.data = n;
 
        ListNode<E> oHead = m_head;
        m_head = tmp;
        m_head.next = oHead;
    }
 
    public void pop () {
        if (isEmpty()) throw new NoSuchElementException("Stack is Empty");
        m_head = m_head.next;
    }
 
    public E top () {
        return m_head.data;
    }
 
    public boolean isEmpty () {
        return m_head == null;
    }
 
    private ListNode<E> getNewNode () {
        return new ListNode<E>();
    }
}

Now testing the class above

import junit.framework.Assert;
 
import org.junit.After;
import org.junit.Before;
import org.junit.Test;
 
public class StackTest
{
    private String[] elems = new String[] { "A", "B", "C" };
    private Stack<String> stack = new Stack<String>();
 
    @Before
    public void setup () {
        for (String str : elems)
        {
            stack.push(str);
        }
    }
 
    @After
    public void destroy () {
        while (stack.isEmpty() == false)
        {
            stack.pop();
        }
    }
 
    @Test
    public void testTop () {
        Assert.assertEquals(stack.top(), "C");
    }
 
    @Test
    public void testPush () {
        Assert.assertEquals(stack.top(), "C");
        stack.pop();
        Assert.assertEquals(stack.top(), "B");
        stack.pop();
        Assert.assertEquals(stack.top(), "A");
    }
}

Please let us know the feedback.

Read More