Jan 1, 2013

Stack implementation using a singly linked list

The below is a stack implementation using a singly linked list.
1. push adds node on top of the stack
2. pop removes the top most node from the stack
3. top returns the top most node of the stack without modifying it
4. isEmpty checks if the stack does not have any elements

The details of the StackNode class

package com.ds.programs;

class StackNode<E>
{
    E data;
    StackNode<E> next;
}

The Stack class with push, pop, top and isEmpty implementation
package com.ds.programs;

import java.util.NoSuchElementException;

public class Stack<E>
{
    private StackNode<E> m_head;

    public Stack () {
        m_head = null;
    }

    public void push (E n) {
        StackNode<E> tmp = getNewNode();
        tmp.data = n;

        StackNode<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 StackNode<E> getNewNode () {
        return new StackNode<E>();
    }
}

The StackTest junit class for testing the above stack implementation
package com.ds.programs;

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");
    }
}

No comments :

Post a Comment