[Data structure] Implementation of stack—array method and linked list method

stack:

A first-in-last-out [data structure]

Basic operation:

  • Push: push an element to the bottom of the stack
  • pop: pop the top element of the stack
  • Full: Whether the stack is full, no more elements can be added when it is full
  • Empty: Whether the stack is empty, if it is empty, no more elements can be popped

Implementation: ( [Array] implementation)

public  class  ArrayStack  {
     int top = - 1 ;    // mark the top position of the stack 
    int ArrayStack[];

    ArrayStack()
    {
        this .ArrayStack = new  int [ 10 ];     //The default stack space is 10
    }
    ArrayStack(int n)
    {
        this.ArrayStack = new int[n];     
    }
    //Push into the stack 
    boolean  push ( int a)
     {
         //Automatic expansion, and copy the old stack to the new stack 
        if ( this .top == this .ArrayStack.length- 1 )     //Determine whether the stack is full
        {
            int newArrayStack[] = new int[this.ArrayStack.length*2];
            for(int i=0;i<=top;i++)
                newArrayStack[i] = this.ArrayStack[i];
            this.ArrayStack = newArrayStack;
        }
        top++;  
        ArrayStack[ this .top ] = a;    // store the element on top of the stack 
        return  true ;
    }
    //Pop stack 
    int  pop ()
     {
         if ( this .top == - 1 ) return - 1 ;      //Check if the stack is empty 
        else  return  this .ArrayStack[ this .top--];
    }
    boolean isFull()
    {
        if(this.top == this.ArrayStack.length-1)return true;
        else return false;
    }
    boolean isEmpty()
    {
        if(this.top == -1) return true;
        else return false;
    }

}

Linked list implementation: (the linked list will not be full)

import java.util.Scanner;

class  Node {                       //Node as a property of the stack 
    public  int data;
     public Node next = null ;

    Node(int data)
    {
        this.data = data;
        this.next = null;   
    }
}

public class ListStack 
{
    private Node top;

    ListStack()
    {
        this.top = null;    
    }
    public boolean push(int num)
    {
        Node p = new Node(num);
        p.next = this.top;       
        this.top = p;
        return true;

    }
    //Pop the stack 
    public  int  pop ()
     {
         if ( this .top== null ) return - 1 ;
         int num = this .top.data;
         this .top = this .top.next;    //After the head pointer after the element is fetched shift 
        return num;
    }
    // Hanku 
    boolean  isEmpty ()
     {
         return  this .top == null ;
    }
    public boolean isFull()
    {
        return true;
    }

}

test:

public class app {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        //ArrayStack s = new ArrayStack(10);
        ListStack s = new ListStack();
        s.push(10);
        s.push(50);
        s.push(20);
        while(!s.isEmpty())
        {
            System.out.print(s.pop()+" ");
        }   
    }

}

Leave a Comment

Your email address will not be published. Required fields are marked *