Java Program Using Queue

Stacks and Queues Best described as ADTs (interfaces in Java). public interface Stack { void push(int v) throws Exception; int pop() throws Exception; boolean isEmpty(); int peek();

// can’t push onto a full stk // can’t pop off an empty stk // returns value being popped // not universal // not universal

} public interface Queue { void enqueue(int v) throws Exception; int dequeue() throws Exception; boolean isEmpty(); }

Stacks LIFO structure (Last-In-First-Out) Implementation Array-Based class ArrayStack implements Stack { private int[] data = new int[1000]; private int size = 0; public void push(int v) { data[size++] = v; } public int pop() { return data[--size]; } } Also must add checks for full stack during push and empty stack during pop. Node-and-Link-Based (particularly easy) class LinkedStack implements Stack { class Node { int value; Node next; } private Node head = null; public void push(int v) { insertAtHead(v); } public int pop() { return deleteAtHead(); } }

Applications Expression Evaluation Given a string that represents an arithmetic expression, such as “3*4+(7-2)*5”, imagine designing a program to read the string, tokenize and parse it, then evaluate the expression to find its value in simplest terms. This procedure is called the parsing problem. Styles of Expression Notation for Arithmetic Expressions • Infix notation: a + b • Prefix notation: + a b • Postfix notation: a b + (aka “Reverse Polish Notation” or RPN) Infix is the most common for pencil-and-paper work. Prefix and postfix are common in technical applications (some programming languages such as Lisp/Scheme use prefix, some older handheld calculators like some HP calculators use postfix). Postfix notation does not need parentheses, since the evaluation scheme determines precedence of operations by the operation’s position in the expression Algorithm to directly evaluate an infix expression is complex. Instead, it’s often much easier to perform the following two steps: • Convert or translate an infix expression into a postfix expression • Evaluate the postfix notation expression Each step is a separate algorithm, and each algorithm is implemented using a stack. Algorithm for Infix-To-Postfix Translation (aka “Shunting Yard Algorithm” by Edsgar Dijkstra) Assume S contains 4 token types to define expressions (simplified to exclude function/method calls): LP (left paren) RP (right paren) NUM (number) OP (operation + - * /) S = initial infix expression as a string R = final postfix expression, initially the empty string ST = empty stack Read tokens in S one token at a time from left to right For each token TK in S If TK is LP Push TK onto ST Else if TK is RP Pop tokens off ST, move to tail of R until popped token is LP (discard LP, don’t add it to R) Else if TK is NUM Add TK to tail of R Else if TK is OP Locate any OPs on top of stack with precedence > TK pop these OPs and move them to tail of R Push TK onto ST End For For all tokens remaining on st, pop them and move them to tail of R Note • • •

Numbers or operands are never placed on the stack, they move from input string directly to result string. Left parens appear on the stack temporarily, but right parens are never placed on the stack, and the final result expression contains no parens at all. Handling of operators is the most complex case. Operators move from infix string, to stack, to result string, but precedence rules require special care.

Infix To Postfix Examples Example: “3*4+5” Token Type 3 NUM * OP 4 NUM + OP 5 NUM Result String:

Stack * * + +

“3 4 * 5 +”

Example: “3+4*5” Token Type 3 NUM + OP 4 NUM * OP 5 NUM Result String:

Result String 3 3 34 34* 34*5

Result String 3 3 34 34 345

“3 4 5 + *”

Stack + + +* +*

Example:

“((3/5)+(4/7))/(2*3+4*5)”

Token ( ( 3 / 5 ) + ( 4 / 7 ) ) / ( 2 * 3 + 4 * 5 )

Result String is

Type LP LP Num Op Num RP Op LP Num Op Num RP RP Op LP Num Op Num Op Num Num Num RP

Result String 3 3 35 35/ 35/ 35/ 35/4 35/4 35/47 35/47/ 35/47/+ 35/47/+ 35/47/+ 35/47/+2 35/47/+2 35/47/+23 35/47/+23* 35/47/+23*4 35/47/+23*4 35/47/+23*45 35/47/+23*45*+ 35/47/+23*45*+/

Stack ( (( (( ((/ ((/ ( (+ (+( (+( (+(/ (+(/ (+ / /( /( /(* /(* /(+ /(+ /(+* /(+* /

35/47/+23*45*+/

Example (2+3*4)*(3+4*2) Token ( 2 + 3 * 4 ) * ( 3 + 4 * 2 )

Result String is

Type LP Num Op Num Op Num RP Op LP Num Op Num Op Num RP

Result String 2 2 23 23+ 234 234*+ 234*+ 234*+ 234*+3 234*+3 234*+34 234*+34 234*+342 234*+342*+ 234*+342*+*

234*+342*+*

Stack ( ( (+ (+ (+* (+* * *( *( *(+ *(+ *(+* *(+* *

Postfix Evaluation This algorithm is even simpler than the last one. Read the postfix expression from left to right. Whenever you read a number or symbol (operand), push it onto the stack. Whenever you read an operation, pop the stack twice to get the top two operands off the stack, apply the operator to these operands, and push the result back onto the stack. When you reach the end of the postfix expression, the final result should be the single value on the stack. Pop the stack to get the final value, leaving the stack in its initial empty state. S = Initial postfix expression (numbers and ops, no parens) ST = empty stack Read tokens in S one token at a time from left to right For each token TK in S If TK is NUM Push TK onto ST Else if TK is OP Y = Pop ST X = Pop ST Z = X TK Y Push Z onto ST End For Result = Pop ST Note • • •

This algorithm only evaluates input expressions that are already in postfix notation, it won’t work for infix or prefix expressions. Operations are never placed onto the stack, only numbers (values). Since the input is in postfix notation, there are no parentheses to process at all.

Postfix Evaluation Examples Example Infix Notation: “3*4+5” Postfix Notation: “3 4 * 5 +” Token Type Stack 3 Num 3 4 Num 34 * Op 12 5 Num 12 5 + Op 17 Result is 17 Example Infix Notation: “3+4*5” Postfix Notation: “3 4 5 * +” Token Type Stack 3 Num 3 4 Num 34 5 Num 345 * Op 3 20 + Op 23 Result is 23

Example Infix Postfix Token 2 3 4 * + 3 4 2 * + *

(2 + 3 * 4) * (3 + 4 * 2) 2 3 4 * + 3 4 2 * + * Type Num Num Num Op Op Num Num Num Op Op Op

Final stack pop = 154

Stack 2 2 3 2 3 4 2 12 14 14 3 14 3 4 14 3 4 2 14 3 8 14 11 154

Queues FIFO structure (First-In-First-Out) Implementations Array Based class ArrayQueue implements Queue { private int size = …; private int[] data = new int[size]; private int h = 0; // head index private int t = 0; // tail index public boolean isEmpty() { } public boolean isFull() { } public void enqueue(int value) { } public int dequeue() { } } Linear Queue Easy to implement using a smart array, but wasteful of available space Head and tail pointers “drift” to the right, array elements at indexes before head index are wasted. Circular Queue Very popular implementation, implemented like a linear queue, but the head and tail pointers are allowed to “wrap around” back to the left end of the array if they “run off” the right end of the array. Queue can be expanded if it runs out of space, just like a smart array Problem is that it requires careful logical checking to maintain queue in consistent state. Circular Queue Implementation #1 When incrementing head and tail pointers, the indexes must wrap: h = (h+1)%size; t = (t+1)%size; When indexing the array, the indexes can be used directly: data[t] = value; Need an extra state variable boolean empty = true; This variable must be used to tell the difference between an empty circular queue and a full circular queue. Circular Queue Implementation #2 When incrementing head and tail pointers, do not wrap the indexes: h = h + 1; t = t + 1; When indexing the array, the indexes cannot be used directly, they must be wrapped: data[t%size] = value; To determine if queue is empty, no extra boolean is required, simply compare h and t. boolean isEmpty() { return h==t; } Node-and-Link-Based As with the stack, the queue can easily be implemented as a linked list public void enqueue(int v) { insertAtTail(v); } public int dequeue() { return removeFromHead(); }

Applications Buffers There are many applications for queues, for example, in operating systems and other systems programs to implement buffers. A buffer is a temporary storage area in RAM used to interface between a producer of data and a consumer of data. For example, when a program in RAM reads from or writes to a file, the slow access speed of the hard drive makes it impractical for a running program to access the disk directly. Instead, a buffer is used to sit between the application running in RAM (the consumer of the data) and the data in a file on the disk (the producer of the data). When the application opens the file and issues a read command for the first time, the operating system accesses the disk and moves a relatively large chunk of data from disk to the buffer (more data than the program actually requested). Whenever the application now issues a read command, the operating system just goes to the buffer in RAM and fetches the next requested data. In the background, the operating system will quietly keep the buffer filled by occasionally accessing the file on disk and moving more chunks of data from disk to RAM, asynchronously from the application. When the application writes data to a file on disk, the same process happens in reverse. The operating system quietly moves data from the application to the buffer, and then later moves large chunks of data from the buffer to the disk. This is why it is especially important to close or “flush” the output buffer when writing to a file. If your program ends without the close or flush, the last bytes of data written to the buffer may not get copied to the file, and this data will be lost. Simulation and Performance Evaluation A style of simulation called discrete-event simulation uses queues to represent resources in a system that have customers that line up (queue up) for service. The system is described in a statistical sense by defining waiting time and service time distributions. Queues are created and connected in a network to describe the physical system. Then customers are added as elements that wait in a queue for service, leave the queue once service is obtained, and follow the network flow to join another queue, and so on. The goal of the simulation is to establish values for such parameters as: • Average length of all queues • Average service time for all queues • Average time a customer spends in the system Simulations can become quite complex and many other parameters are possible to measure. For example, this style of simulation could be used to model the flow of automobile traffic through a grid of city streets. Traffic lights at intersections would represent queues, and each automobile would represent a customer. After waiting in the line for one queue (traffic signal), a customer (automobile) leaves that queue, follows the network connection (street) to the next queue (next traffic signal), and so on. Traffic congestion is measured by observing the lengths of all queues, and the amount of time it takes a customer to move through the network.

M/M/1 Queueing Model This is a mathematical model for how a queue works. It’s a widely studied mathematical model and is the simplest model for how a queue works. The notation for the describing the behavior of the queue is defined by the notation: • x/y/n where • x identifies the random distribution of customer interarrival time intervals • y identifies the random distribution of service time intervals • n identifies the number of servers for the queue The identifier “M” stands for “Markovian” and is used to describe interarrival or service times that are distributed exponentially. The exponential distribution has the form •

F(t) = 1 – e-λt where 1/λ is the mean value of the distribution

For M/M/1 queues, it is customary to represent the interarrival distribution mean as 1/λ, and the service time mean as 1/μ. Some Useful Performance Measures of the M/M/1 Queue • The traffic intensity parameter is ρ = λ/μ. • Mean number of customers in the system is N = ρ/(1 – ρ). • Mean time in the system (queuing + service) = T = 1/(μ – λ). Note that the traffic intensity ρ must be < 1 for the M/M/1 queue Worked Examples Suppose the mean interarrival time to a queue is 3 minutes, and the mean service time is 1 minute. λ = 1/3, μ = 1, ρ = 1/3 N = (1/3)/(2/3) = 1/2 customers T = 1/(2/3) = 2 minutes Now suppose the mean interarrival time is 3 minutes, and the mean service time is 2.7 minutes λ = 1/3 = 0.33, μ = 1/2.7 = 0.37, ρ = 0.33/0.37 = 0.9 N = 0.9/0.1 = 9 customers T = 1/0.037 = 27 minutes Now suppose the average interarrival time is 3 minutes, and the average service time is 2.9 minutes λ = 1/3 = 0.33, μ = 1/2.9 = 0.3448, ρ = 0.33/0.3448 = 0.9667 N = 0.9667/0.033 = 29 customers T = 1/0.037 = 87 min Simulation For simple queueing problems, common performance measures can be calculated directly from known formulas. If the problem becomes more complex, the simple formulas no longer apply and the system must be simulated by writing a program that creates data structures to represent the queues, simple objects or tokens to represent customers, and random numbers to represent interarrival and service times. The simulation measures the size (length) of the queues and other performance measures at regular intervals and reports means or distributions at the end of the simulation.

Example Traces Trace using one stack New

[] (TOS on left)

Push 3

[3]

Push 4

[4 3]

Push 7

[7 4 3]

Push 10

[10 7 4 3]

Pop

[7 4 3]

Push 5

[5 7 4 3]

Push 15

[15 5 7 4 3]

Pop

[5 7 4 3]

Pop

[7 4 3]

Trace using two stacks A and B New A A push 3

A [] A [3]

A push 4

A [4 3]

A push 5

A [5 4 3]

A push 6

A [6 5 4 3]

New B

A [6 5 4 3] B []

B push(pop A)

A [5 4 3] B [6]

B push(pop A)

A [4 3] B [5 6]

B push(pop A)

A [3] B [4 5 6]

B push(pop A)

A [] B [3 4 5 6]

Note: two stacks can be used to reverse a series of elements

Trace using a queue New enq enq enq enq deq deq enq deq deq

3 8 12 9

7

[] (head on left, tail on right) [3] [3 8] [3 8 12] [3 8 12 9] [8 12 9] [12 9] [12 9 7] [9 7] [7]