Queues and Stacks

Stack

Queue

Priority Queue

Queues and stacks are containers whose main methods for access are push() and pop(). JGL includes three containers with this property.

A Stack is a first-in, last-out data structure that pops elements in the opposite order than they were pushed. By default, a Stack uses an Array for its internal storage, although this can easily be changed.

A Queue is a first-in, first-out data structure that pops elements in the same order than they were pushed. By default, a Queue uses an SList for its internal storage, although this can easily be changed.

A PriorityQueue is a form of queue that keeps its elements in a quasi-sorted state and pops them based on their sorted order rather than in the order that they were pushed. A PriorityQueue uses an Array for its underlying storage.

Each of these containers implement the Container interface, as shown by the following diagram:

The rest of this chapter describes each of these container types in detail.

Stack

In addition to implementing the methods defined in the Container interface, a Stack supports the push() the pop() methods as shown by the following example.

Example Stacks1.java

// Copyright(c) 1996,1997 ObjectSpace, Inc.

import com.objectspace.jgl.*;

import java.util.Enumeration;



public class Stacks1

  {

  public static void main( String[] args )

    {

    Stack stack = new Stack();

    stack.push( "bat" );

    stack.push( "cat" );

    stack.push( "dog" );

    System.out.println( "stack = " + stack );

    System.out.println();



    System.out.println( "Non-destructively enumerate the Stack." );

    Enumeration e = stack.elements();

    while ( e.hasMoreElements() )

      System.out.println( e.nextElement() );

    System.out.println();



    System.out.println( "Pop and print each element." );

    while ( !stack.isEmpty() )

      System.out.println( stack.pop() );

    }

  }

Output
stack = Stack( Array( bat, cat, dog ) ) Non-destructively enumerate the Stack. bat cat dog Pop and print each element. dog cat bat

By default, a Stack uses an Array for its underlying storage. To change this to a different container, supply the container when the Stack is constructed.

Example Stacks2.java

// Copyright(c) 1996,1997 ObjectSpace, Inc.

import com.objectspace.jgl.*;



public class Stacks2

  {

  public static void main( String[] args )

    {

    // Use a DList as the underlying data structure.

    Stack stack = new Stack( new DList() );

    stack.push( "bat" );

    stack.push( "cat" );

    stack.push( "dog" );



    System.out.println( "Print the Stack." );

    System.out.println( stack );

    }

  }

Output
Print the Stack. Stack( DList( bat, cat, dog ) )

Queue

In addition to implementing the methods defined in the Container interface, a Queue supports the push() and pop() methods as shown by the following example.

Example Stacks3.java

// Copyright(c) 1996,1997 ObjectSpace, Inc.

import com.objectspace.jgl.*;

import java.util.Enumeration;



public class Stacks3

  {

  public static void main( String[] args )

    {

    Queue queue = new Queue();

    queue.push( "bat" );

    queue.push( "cat" );

    queue.push( "dog" );



    System.out.println( "queue = " + queue );

    System.out.println();



    System.out.println( "Non-destructively enumerate the Queue." );

    Enumeration e = queue.elements();

    while ( e.hasMoreElements() )

      System.out.println( e.nextElement() );

    System.out.println();



    System.out.println( "Pop and print each element." );

    while ( !queue.isEmpty() )

      System.out.println( queue.pop() );

    }

  }

Output
queue = Queue( SList( bat, cat, dog ) ) Non-destructively enumerate the Queue. bat cat dog Pop and print each element. bat cat dog

By default, a Queue uses an SList for its underlying storage. To change this to a different container, supply the container when the Queue is constructed.

PriorityQueue

A PriorityQueue uses an internal Array to store pushed elements in a heap structure. By default, elements are compared using their hash values, although you can change this behavior by supplying a function object when the queue is constructed. Note that although a PriorityQueue always pops elements in the order determined by the comparitor, this does not mean that that objects are stored in order within the internal heap structure. The following example uses a PriorityQueue to push and pop Integer objects in descending order.

Example Stacks4.java

// Copyright(c) 1996,1997 ObjectSpace, Inc.

import com.objectspace.jgl.*;

import java.util.Enumeration;



public class Stacks4

  {

  public static void main( String[] args )

    {

    // Use a HashComparator for comparing elements. Since the hash value of an

    // Integer is its int value, this will order Integers in descending order.

    PriorityQueue queue = new PriorityQueue();

    queue.push( new Integer( 5 ) );

    queue.push( new Integer( -2 ) );

    queue.push( new Integer( 10 ) );

    queue.push( new Integer( 6 ) );

    queue.push( new Integer( 20 ) );

    queue.push( new Integer( -10 ) );



    System.out.println( "queue = " + queue );

    System.out.println();



    System.out.println( "Non-destructively enumerate the PriorityQueue." );

    Enumeration e = queue.elements();

    while ( e.hasMoreElements() )

      System.out.print( e.nextElement() + " " );

    System.out.println();



    System.out.println( "Pop and print each element." );

    while ( !queue.isEmpty() )

      System.out.print( queue.pop() + " " );

    System.out.println();

    }

  }

Output
queue = PriorityQueue( Array( 20, 10, 5, -2, 6, -10 ) ) Non-destructively enumerate the PriorityQueue. 20 10 5 -2 6 -10 Pop and print each element. 20 10 6 5 -2 -10

The following example uses a GreaterString function object to pop String objects in ascending order.

Example Stacks5.java

// Copyright(c) 1996,1997 ObjectSpace, Inc.

import com.objectspace.jgl.*;

import com.objectspace.jgl.predicates.*;



public class Stacks5

  {

  public static void main( String[] args )

    {

    // Use a GreaterString function object for comparing elements. This will

    // order strings in ascending order.

    PriorityQueue queue = new PriorityQueue( new GreaterString() );

    queue.push( "cat" );

    queue.push( "dog" );

    queue.push( "ape" );

    queue.push( "bat" );

    queue.push( "fox" );

    queue.push( "emu" );



    System.out.println( "Pop and print each element." );

    while ( !queue.isEmpty() )

      System.out.print( queue.pop() + " ");

    System.out.println();

    }

  }

Output
Pop and print each element. ape bat cat dog emu fox

Contents

Sets

Array Adapters