Chapter 13: Collections 267
{
private Node front, back;
private int numElements;
public LinkedQueue()
{
}
//———————————————
// Puts item on end of queue.
//———————————————
public void enqueue(Object item)
{
}
public Object dequeue()
{
Object item = null;
}
//———————————————
// Returns true if queue is empty.
//———————————————
public boolean isEmpty()
{
}
}
//———————————————
// Returns the number of elements in the queue.
//———————————————
public int size()
{
}
//———————————————
{
String result = “\n”;
Node temp = front;
while (temp != null)
{
result += temp.getElement() + “\n”;
temp = temp.getNext();
268 Chapter 13: Collections
}
return result;
}
}
//************************************************************
private Node next;
private Object element;
//——————————————————-
// Creates an empty node
//——————————————————-
public Node()
{
next = null;
element = null;
}
}
//——————————————————-
// Returns the node that follows this one
//——————————————————-
public Node getNext()
{
return next;
}
}
//——————————————————-
// Returns the element stored in this node
//——————————————————-
public Object getElement()
{
return element;
}
public void setElement(Object element)
{
this.element = element;
}
}
//***********************************************************
// TestQueue
// A driver to test the methods of the QueueADT implementations.
//**********************************************************
public class TestQueue
{
public static void main(String[] args)
{
QueueADT q = new LinkedQueue();
System.out.println(“\nHere’s the queue: ” + q);
System.out.println(“It contains ” + q.size() + ” items.”);
System.out.println(“\nDequeuing two…”);
System.out.println(q.dequeue());
q.enqueue (” ice cream”);
System.out.println(“\nHere’s the queue again: ” + q);
System.out.println(“Now it contains ” + q.size() + ” items.”);
System.out.println(“\nDequeuing everything in queue”);
while (!q.isEmpty())
270 Chapter 13: Collections
Queue Manipulation
The file QueueTest.java contains a printQueue method that takes an object of type QueueADT and prints its
contents, restoring the queue before it returns. It uses a temporary queue that actually holds the same
information as the original queue. If you know the number of elements in the queue, you can write a printQueue
method that prints the queue and restores it to its original form without using an auxiliary data structure (stack,
queue, etc.). Think about how, then do it! That is, modify the printQueue method in QueueTest so that it
behaves exactly as it does now but does not require an auxiliary data structure. Note that this code uses a
LinkedQueue implementation for the QueueADT (see previous exercises), but you could substitute an
ArrayQueue if you like.
// **************************************************************
// QueueTest.java
//
// A simple driver to manipulate a queue.
//
// **************************************************************
public class QueueTest
{
public static void main(String[] args)
{
QueueADT queue = new LinkedQueue();
//put some stuff in the queue: 0,2,4,..,14
//dequeue 4 items
for (int i=0; i<4; i++)
}
//———————————————————-
// Prints elements of queue, restoring it before returning
//———————————————————-
public static void printQueue(QueueADT queue)
{
QueueADT temp = new LinkedQueue();
//print everything in the queue, putting elements
//back into a temporary queue
while (!queue.isEmpty())
{
Chapter 13: Collections 271
}
System.out.println ();
272 Chapter 13: Collections
An Array Stack Implementation
Java has a Stack class that holds elements of type Object. However, many languages do not provide stack types,
so it is useful to be able to define your own. File StackADT.java contains an interface representing the ADT for
a stack of objects and ArrayStack.java contains a skeleton for a class that uses an array to implement this
interface. Fill in code for the following public methods:
void push(Object val)
In writing your methods, keep in mind the following:
The bottom of an array-based stack is always the first element in the array. In the skeleton given, variable
top holds the index of the location where the next value pushed will go. So when the stack is empty, top is
0; when it contains one element (in location 0 of the array), top is 1, and so on.
File StackTest.java contains a simple driver to test your stack. Save it to your directory, compile it, and make
sure it works. Note that it tries to push more things than will fit on the stack, but your push method should deal
with this.
// ***************************************************************
// StackADT.java
// —————————————————
// Adds a new element to the top of the stack.
// —————————————————
public void push(Object val);
// —————————————————
// —————————————————
// Returns true if stack is empty, false otherwise.
// —————————————————
public boolean isEmpty();
//
// ***************************************************************
Chapter 13: Collections 273
public class ArrayStack implements StackADT
{
// Constructor — initializes top and creates array
// —————————————————
public ArrayStack()
{
}
{
}
// —————————————————
// Removes and returns value at top of stack. If stack
// is empty returns null.
// —————————————————
public Object pop()
{
}
// —————————————————
// Returns true if stack is empty, false otherwise.
}
}
274 Chapter 13: Collections
// *********************************************************
// StackTest.java
public static void main(String[] args)
{
StackADT stack = new ArrayStack();
//push some stuff on the stack
for (int i=0; i<6; i++)
stack.push(i*2);
//should print 5 4 3 2 1
while (!stack.isEmpty())
System.out.print(stack.pop() + ” “);
System.out.println();
}
}
Chapter 13: Collections 275
A Linked Stack Implementation
Java has a Stack class that holds elements of type Object. However, many languages do not provide stack types,
so it is useful to be able to define your own. File StackADT.java contains an interface representing the ADT for
a stack of objects and LinkedStack.java contains a skeleton for a class that uses a linked list to implement this
interface. It depends on the Node class in Node.java. (This could also be defined as an inner class.) Fill in code
for the following public methods:
void push(Object val)
int pop()
In writing your methods, keep in mind that in a linked implementation of a stack, the top of stack is always at
the front of the list. This makes it easy to add (push) and remove (pop) elements.
File StackTest.java contains a simple driver to test your stack. Save it to your directory, compile it, and make
sure it works.
// ***************************************************************
// StackADT.java
// The classic Stack interface.
// ***************************************************************
public interface StackADT
{
// —————————————————
// Returns true if stack is empty, false otherwise.
// —————————————————
public boolean isEmpty();
// —————————————————
// Returns true if stack is full, false otherwise.
// ***************************************************************
public class LinkedStack implements StackADT
{
private Node top; // reference to top of stack
// —————————————————
276 Chapter 13: Collections
// Constructor — initializes top
// —————————————————
public LinkedStack()
{
}
// —————————————————
// Removes and returns value at top of stack. If stack
// is empty returns null.
// —————————————————
public Object pop()
{
}
// —————————————————
// Returns true if stack is empty, false otherwise.
// —————————————————
public boolean isEmpty()
{
}
//***********************************************************
// Node.java
// A general node for a singly linked list of objects.
//***********************************************************
public class Node
{
private Node next;
private Object element;
Chapter 13: Collections 277
{
next = null;
this.element = element;
}
{
next = node;
}
//—————————————————-
// Returns the element stored in this node
//—————————————————-
public Object getElement()
{
return element;
}
// *******************************************************
// StackTest.java
//
// A simple driver that exercises push, pop, isFull and isEmpty.
// Thanks to autoboxing, we can push integers onto a stack of Objects.
//
// *******************************************************
public class StackTest
{
278 Chapter 13: Collections
System.out.print(stack.pop() + ” “);
System.out.println();
Chapter 13: Collections 279
Stack Manipulation
Sometimes it’s useful to define operations on an ADT without changing the type definition itself. For example,
you might want to print the elements in a stack without actually adding a method to the Stack ADT (you may
not even have access to it). To explore this, use either the Stack class provided by Java (in java.util) or one of
the stack classes that you wrote in an earlier lab exercise and the test program StackTest.java. Add the
following static methods to the StackTest class (the signature for these methods and the declaration in StackTest
assumes you are using a stack class named Stack—modify them to use the name of your class):
Modify the main method to test these methods. Be sure you print enough information to see if they’re working!
// ***************************************************************
// StackTest.java
public static void main(String[] args)
{
// Declare and instantiate a stack
Stack stack = new Stack();
//push some stuff on the stack
for (int i=0; i<10; i++)
stack.push(i);
}
280 Chapter 13: Collections
Matching Parentheses
One application of stacks is to keep track of things that must match up such as parentheses in an expression or
braces in a program. In the case of parentheses when a left parenthesis is encountered it is pushed on the stack
and when a right parenthesis is encountered its matching left parenthesis is popped from the stack. If the stack
has no left parenthesis, that means the parentheses don’t match—there is an extra right parenthesis. If the
expression ends with at least one left parenthesis still on the stack then again the parentheses don’t
match—there is an extra left parenthesis.
File ParenMatch.java contains the skeleton of a program to match parentheses in an expression. It uses the
Stack class provided by Java (in java.util). Complete the program by adding a loop to process the line entered to
see if it contains matching parentheses. Just ignore characters that are neither left nor right parentheses. Your
loop should stop as soon as it detects an error. After the loop print a message indicating what happened—the
parentheses match, there are too many left parentheses, or there are too many right parentheses. Also print the
part of the string up to where the error was detected.
// ********************************************************************
// ParenMatch.java
public static void main (String[] args)
{
Stack s = new Stack();
String line; // the string of characters to be checked
Scanner scan = new Scanner(System.in);