• Collections:
  • We now know how to use several
  • We need to know something about implementing them
• Data Structures:
  • We now know about contiguous and linked data structures
  • We need to know how to implement collections using both

• A Limitation:
  • Only appropriate for fixed capacity collections
• Issues that Arise:
  • Keeping track of the next empty space
  • Keeping track of the "current" filled space
  • Shuffling

• The Basics:
  • Use a node that contains a value and a "pointer" to the next node
  • The pointers "link" the different nodes together
• An Illustration:
  • 

• Defined:
  • An ordered collection in which elements can be pushed/added onto the top and popped/removed from the top
• An Important Acronym:
  • Last-in, first-out (LIFO)
• A Physical Analogy:
  • A box of paper -- when you add a piece of paper to the box it gets put on the top; the only piece of paper that can be removed is the top sheet

• Capacity:
  • 3
• Push on a 1:

  • 1

    .

    .

• Push on a 2:

  • 1

    2

    .

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

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

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

• Defined:
  • An ordered collection in which elements can be pushed/added onto the back and popped/removed from the front
• An Important Acronym:
  • First-in, first-out (FIFO)
• Physical Analogy:
  • A "waiting line" -- when you add a person to the line they go to the back and people are served from the front

• Capacity:
  • 3
• Push on a 1:

  • 1

    .

    .

• Push on a 2:

  • 1

    2

    .

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

• Periodic Shuffling:
  • Keep a pointer to the front and rear elements and move all of the elements down when space at the back runs out
  • This is analgous to a waiting line in which the server moves (until space runs out)
  • Think about a clock in which the ticks are on a line, not a circle
• Using a "Circular Array":
  • Keep a pointer to the front and rear elements and have them "wrap around"
  • This is analgous to a waiting line in which the server moves in a circle

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