Queues

Queue.

public class Queue<Item> { public boolean isEmpty(); public void enqueue(Item item); public Item dequeue(); }

• Linked list implementation. Program Queue.java implements a FIFO queue of strings using a linked list. Like Stack, we maintain a reference first to the least-recently added Node on the queue. For efficiency, we also maintain a reference last to the most-recently added Node on the queue.
• Array implementation. Similar to array implementation of stack, but a little trickier since need to wrap-around. Program DoublingQueue.java implements the queue interface. The array is dynamically resized using repeated doubling.

Iteration.

public interface Iterator<Item> { boolean hasNext(); Item next(); void remove(); // optional }

Queue<String> queue = new Queue<String>(); ... Iterator<String> i = queue.iterator(); while (i.hasNext()) { String s = i.next(); StdOut.println(s); }

• Queue iterator in Java. Queue.java illustrates how to implement an Iterator when the items are stored in a linked list.

  public Iterator iterator() { return new QueueIterator(); } private class QueueIterator implements Iterator<Item> { Node current = first; public boolean hasNext() { return current != null; } public Item next() { Item item = current.item; current = current.next; return item; } }

  It relies on a private nested subclass QueueIterator that implements the Iterator interface. The method iterator() creates an instance of typeQueueIterator and returns it as an Iterator. This enforces the iteration abstraction since the client will only the items through the hasNext() andnext() methods. The client has no access to the internals of the Queue or even the QueueIterator. It is the client's responsibility to only add elements to the list when no iterator is in action.
• Enhanced for loop. Iteration is such a useful abstraction that Java provides compact syntax (known as the enhanced for loop) to iterate over the elements of a collection (or array).

  Iterator<String> i = queue.iterator(); while (i.hasNext()) { String s = i.next(); StdOut.println(s); } for (String s : queue) StdOut.println(s);

  To take advantage of Java's enhanced foreach syntax, the data type must implement Java's Iterable interface.

  public interface Iterable<Item> { Iterator<Item> iterator(); }

  That is, the data type must implement a method named iterator() that returns an Iterator to the underlying collection. Since our Queue ADT now includes such a method, we simply need to declare it as implementing the Iterable interface and we are ready to use the foreach notation.

  public class Queue<Item> implements Iterable<Item>

Stack and queue applications.

• Queue applications: Computing applications: serving requests of a single shared resource (printer, disk, CPU), transferring data asynchronously (data not necessarily received at same rate as sent) between two processes (IO buffers), e.g., pipes, file IO, sockets. Buffers on MP3 players and portable CD players, iPod playlist. Playlist for jukebox - add songs to the end, play from the front of the list. Interrupt handling: When programming a real-time system that can be interrupted (e.g., by a mouse click or wireless connection), it is necessary to attend to the interrupts immediately, before proceeding with the current activity. If the interrupts should be handles in the same order they arrive, then a FIFO queue is the appropriate data structure.
• Arithmetic expression evaluation. Program Evaluate.java evaluates a fully parenthesized arithmetic expression.
  An important application of stacks is in parsing. For example, a compiler must parse arithmetic expressions written using infix notation. For example the following infix expression evaluates to 212.

  ( 2 + ( ( 3 + 4 ) * ( 5 * 6 ) ) )

  We break the problem of parsing infix expressions into two stages. First, we convert from infix to a different representation called postfix. Then we parse the postfix expression, which is a somewhat easier problem than directly parsing infix.
  • Evaluating a postfix expression. A postfix expression is....

    2 3 4 + 5 6 * * +

    First, we describe how to parse and evaluate a postfix expression. We read the tokens in one at a time. If it is an integer, push it on the stack; if it is a binary operator, pop the top two elements from the stack, apply the operator to the two elements, and push the result back on the stack. Program Postfix.java reads in and evaluates postfix expressions using this algorithm.
  • Converting from infix to postfix. Now, we describe how to convert from infix to postfix. We read in the tokens one at a time. If it is an operator, we push it on the stack; if it is an integer, we print it out; if it is a right parentheses, we pop the topmost element from the stack and print it out; if it is a left parentheses, we ignore it. Program Infix.java reads in an infix expression, and uses a stack to output an equivalent postfix expression using the algorithm described above. Relate back to the parse tree example in Section 4.3.
• Function calls. Perhaps the most important application of stacks is to implement function calls. Most compilers implement function calls by using a stack. This also provides a technique for eliminating recursion from a program: instead of calling a function recursively, the programmer uses a stack to simulate the function calls in the same way that the compiler would have done so. Conversely, we can often use recursion instead of using an explicit stack. Some programming languages provide a mechanism for recursion, but not for calling functions.
  Programming languages have built in support for stacks (recursion), but no analogous mechanism for dealing with queues.
  Postscript and FORTH programming languages are stack based. Java bytecode is interpreted on (virtual) stack based processor. Microsoft Intermediate Language (MSIL) that .NET applications are compiled to.
• M/M/1 queue. The M/M/1 queue is a fundamental queueing model in operations research and probability theory. Tasks arrive according to a Poisson process at a certain rate λ. This means that λ customers arrive per hour. More specifically, the arrivals follow an exponential distribution with mean 1 / λ: the probability of k arrivals between time 0 and t is (λ t)^k e^(-λ t) / k!. Tasks are serviced in FIFO order according to a Poisson process with rate μ. The two M's standard for Markov: it means that the system is memoryless: the time between arrivals is independent, and the time between departures is independent.
  Analysis of M/M/1 model. We are interested in understanding the queueing system. If λ > μ the queue size increases without limit. For simple models like M/M/1 we can analyze these quantities analytically using probability theory. Assuming μ > λ, the probability of exactly n customers in the system is (λ / μ)ⁿ (1 - λ / μ).
  • L = average number of customers in the system = λ / (μ - λ).
  • L_Q = average number of customers in the queue = λ² / (μ (μ - λ)).
  • W = average time a customer spends in the system = 1 / (μ - λ).
  • W_Q = average time a customer spends in the queue = W - 1 / μ = λ / (μ (μ - λ)).
  See this wikibook for the formulas.
  Program MM1Queue.java For more complex models we need to resort to simulation like this. Variants: multiple queues, multiple servers, sequential multi-stage servers, using a finite queue and measuring number of customers that are turned away. Applications: customers in McDonalds, packets in an internet router,
  Little's law asserts that the average number of customers in a (stable) queueing system equals the average arrival rate times their average time in the system. But the variance of customer waiting times satisfies: Var(FIFO) < Var(SIRO) < Var(LIFO).
  The distribution of the number of customers in the system does not depend on the queueing discipline (so long as it is independent of their service times). Same for expected waiting time.
  • L = λ W (average number of customers in the system)
  • L_Q = λ W_Q (average number in queue)
  • W = W_q + 1/μ (average waiting time in system)
  • W_q (average waiting time in queue)
• M/D/1 queue. Program MD1Queue.java is similar but the service occurs at a fixed rate (rather than random).
• Load balancing. Write a program LoadBalance.java that performs a load-balancing simulation.