Stacks and Queues - Advanced Topics in Java: Core Concepts in Data Structures - page 129

public NodeData(char c, int n) {
ch = c;
num = n;
}

public char getCharData() {return ch;}

public int getIntData() {return num;}

public static NodeData getRogueValue() {
return new NodeData('$', -999999);
}

} //end class NodeData

The following is a sample run of Program P4.6:

Type an infix expression and press Enter
(7 - 8 / 2 / 2) * ((7 - 2) * 3 - 6)

The postfix form is
7 8 2 / 2 / - 7 2 - 3 * 6 - *

Its value is 45

4.5 Queues
A queue is a linear list in which items are added at one end and deleted from the other end. Familiar examples are
queues at a bank, a supermarket, a concert, or a sporting event. People are supposed to join the queue at the rear and
exit from the front. We would expect that a queue data structure would be useful for simulating these real-life queues.
Queues are also found inside the computer. There may be several jobs waiting to be executed, and they are held
in a queue. For example, several people may each request something to be printed on a network printer. Since the
printer can handle only one job at a time, the others have to be queued.
These are the basic operations we want to perform on a queue:

• Add an item to the queue (we say enqueue )

• Take an item off the queue (we say dequeue )

• Check whether the queue is empty

• Inspect the item at the head of the queue

Like with stacks, we can easily implement the queue data structure using arrays or linked lists. We will use a
queue of integers for illustration purposes.

4.5.1 Implementing a Queue Using an Array
In the array implementation of a queue (of integers), we use an integer array ( QA , say) for storing the numbers and two
integer variables ( head and tail ) that indicate the item at the head of the queue and the item at the tail of the queue,
respectively.