JMU
Stacks and Queues
An Introduction with Examples in Java


Prof. David Bernstein
James Madison University

Computer Science Department
bernstdh@jmu.edu


Motivation
Implementing Collections Using Contiguous Memory
Implementing Collections Using Linked Memory
Stacks
Stacks that Use Contiguous Memory
Stacks that Use Contiguous Memory (cont.)

One Approach

javaexamples/stackqueue/contiguous/Stack.java
        /**
 * A Stack (of Object objects)
 *
 * This implementation uses contiguous memory
 *
 * @version 1.0
 * @author  Prof. David Bernstein, James Madison University
 */
public class Stack
{
    private int         top;
    private Object[]    contents;

    public static final int CAPACITY = 100;

    /**
     * Construct a new (empty) Stack
     */
    public Stack()
    {
        top = -1;
        contents = new Object[CAPACITY];
    }



    /**
     * Pop an Object off of the top of this Stack
     *
     * @return  The Object on the top of this Stack
     */
    public Object pop()
    {
        Object  value;


        if (top != -1) 
        {
            value = contents[top];
            top   = top - 1;
        } 
        else
        {
            value = null;
        }

        return value;
    }


    /**
     * Push an Object onto the top of this Stack
     *
     * @param first   The Object to push
     */
    public void push(Object first)
    {
        if (top < CAPACITY-1)
        {
            top = top + 1;

            contents[top] = first;
        }
    }
}
        
Stacks that Use Linked Memory

The Node Class

javaexamples/stackqueue/linked/Node.java
        /**
 * A Node (containing an Object) in a singly-linked
 * data structure
 *
 * Note: This class is not public.  Hence, it will only 
 * be visible to classes in this package.  (This is an 
 * example of package visibility.)
 *
 * @author  Prof. David Bernstein, James Madison University
 * @version 1.0
 */
class Node
{
    Object    value;
    Node      next;
}
        
Stacks that Use Linked Memory (cont.)

One Possible Linked Stack

javaexamples/stackqueue/linked/Stack.java
        /**
 * A Stack (of Object objects)
 *
 * This implementation uses linked memory
 *
 * @version 1.0
 * @author  Prof. David Bernstein, James Madison University
 */
public class Stack
{
    private Node top;


    /**
     * Construct a new (empty) Stack
     */
    public Stack()
    {
        top = null;
    }



    /**
     * Pop an Object off of the top of this Stack
     *
     * @return  The Object on the top of this Stack
     */
    public Object pop()
    {
        Object  value;


        if (top != null) 
        {
            value = top.value;
            top = top.next;
        } 
        else
        {
            value = null;
        }

        return value;
    }


    /**
     * Push an Object onto the top of this Stack
     *
     * @param first   The Object to push
     */
    public void push(Object first)
    {
        Node temp;

        temp = new Node();

        temp.value = first;
        temp.next = top;

        top = temp;
    }
}
        
Queues
Queues that Use Contiguous Memory
Queues that use Contiguous Memory (cont.)

Using Constant Shuffling

javaexamples/stackqueue/contiguous/Queue.java
        /**
 * A Queue (of Object objects)
 *
 * This implementation uses contiguous memory
 *
 * @version 1.0
 * @author  Prof. David Bernstein, James Madison University
 */
public class Queue
{
    private int           back;
    private Object[]      contents;

    public static final int CAPACITY = 100;

    /**
     * Construct a new (empty) Queue
     */
    public Queue()
    {
        back  = -1;
        contents = new Object[CAPACITY];
    }



    /**
     * Pop an Object off of the front of this Queue
     *
     * @return  The Object at the front of this Queue
     */
    public Object pop()
    {
        int     i;
        Object  value;


        if (back != -1) 
        {
            value = contents[0];

            // Shuffle
            for (i=0; i < back; i++)
            {
                contents[i] = contents[i+1];
            }

            back  = back - 1;

        } 
        else
        {
            value = null;
        }

        return value;
    }


    /**
     * Push an Object onto the back of this Queue
     *
     * @param last   The Object to push
     */
    public void push(Object last)
    {
        if (back < CAPACITY-1)
        {
            back = back + 1;
            contents[back] = last;
        }
    }
}
        
Queues that use Contiguous Memory (cont.)
Queues that use Linked Memory

One Possible Linked Queue

javaexamples/stackqueue/linked/Queue.java
        /**
 * A Queue (of Object objects)
 *
 * This implementation uses linked memory
 *
 * @author  Prof. David Bernstein, James Madison University
 * @version 1.0
 */
public class Queue
{
    private int         size;    
    private Node        back, front;


    /**
     * Construct a new (empty) Queue
     */
    public Queue()
    {
        front = null;
        size = 0;        
    }



    /**
     * Pop an Object off of the front of this Queue
     *
     * @return  The Object at the front of this Queue
     */
    public Object pop()
    {
        Object  value;


        if (front != null) 
        {
            value = front.value;
            front = front.next;
            size--;            
        } 
        else
        {
            value = null;
        }

        return value;
    }


    /**
     * Push an Object onto the back of this Queue
     *
     * @param last   The Object to push
     */
    public void push(Object last)
    {
        Node temp;

        temp = new Node();
        temp.value = last;
        temp.next = null;

        size++;        

        if (front == null) 
        {
            front = temp;
        }
        else
        {
            back.next = temp;
        }

        back = temp;
    }


    /**
     * Return the number of elements currently
     * in this Queue
     */
    public int size()
    {
       return size;       
    }
    
}