Java Chapter 14  Stacks and Queues
14.1 Stacks
A stack is collection of data items
that follows the listin firstout (LIFO) principle. Operations include
Push (the item onto the top of the stack), Pull (the item from the top of the
stack, Peek (look at the item on top of the stack without pulling it), and
IsEmpty.
Examples of stacks:
1. A stack of plates. You push a plate on top of the stack. You
pull a plate from the top of the stack.
2. The computer undo function. Each operation the user performs is pushed
onto the stack. When the user hits undo, the last operation is pulled from
the stack.
3. Backtracking. When you are exploring a maze, you push each choice point
onto a stack. If you reach a dead end, then you must pull choice points
from the stack so you can backtrack.
The Stack class below may be used after importing java.util.*
Class Stack 

Command  Description 
Stack<String> s = new Stack<String>()  Constructs a new stack of type String. 
push("apple")  Places the value on top of the stack. 
pop()  Removes and returns the value on top of the stack. 
peek()  Returns the value on top of the stack without removing it. 
size()  Returns the number of items on the stack. 
isEmpty()  Returns true of false whether the stack has items. 
14.2 Using a Stack to Check if Parentheses are Balanced
The algorithm below can be used to check if
parenthesis, brackets, and braces are balanced in an equation.
Balanced input strings:
(a) (([{}])) (b)
(()[]{[]}) (c) {([]([{()([()])}]))}
Unbalanced input strings:
(a) )() (b) [(])
(c) (([]{})
Loop  Step through each character (token) of
the input string
{
if token is an opening (, [, or {, then push it.
else if token is a closing ), ], or }, AND the stack is
empty, then return false
else if token is a ), then pop from the stack. If
it isn't a (, then return false
else if token is a ], then pop from the stack. If
it isn't a [, then return false
else if token is a }, then pop from the stack. If it
isn't a {, then return false
}
if the stack is empty, return true
else return false
14.3 Using Two Stacks to Evaluate an Equation
The algorithm below use two stacks (Value and
Operator) to evaluate a simple equation. Note that this algorithm ignores
operator precedence.
Here's an example equation:
(2+3)*(84)*(53)
Loop  Step through each character
(token) of the input string
{
if token is a number then push onto Value stack
else if token is an operator +,,*,/ or opening ( then
push onto Operator stack
else if token is a closing ),
{
1. Pop the operator from
the Operator stack
2. Pop the Value stack
twice
3. Apply the operator to
the operands
4. Push the result onto
Value stack
5. Pop the opening ( and
discard
}
}
Loop  while the Operator stack isn't empty
{
1. Pop the operator from the Operator stack
2. Pop the Value stack twice
3. Apply the operator to the operands
4. Push the result onto Value stack
}
Return the item on the Value stack
14.3 Queues
A queue is collection of data items
that follows the firstin firstout (FIFO) principle. Operations include
Enqueue (add the item to the back of the queue), Dequeue (remove the item from
the front of the queue, Peek (look at the item on top of the stack without
pulling it), and IsEmpty.
Types of Queues 

Queue Type  Description  Example(s) 
First In First Out (FIFO)  FIFO is the default queue. The first item enqueued will be the first one dequeued. 
1. A line of people waiting to checkout 2. A buffer in a router 
Priority Queue  A priority is assigned to each item when it is enqueued. Items with the highest priority are dequeued first. 
1. A job scheduler 2. Security at an airport where travelers whose flights are leaving soon move to the front of the line 
Round Robin  A round robin queue processes a portion of each item in the queue then goes to the next item.  1. Scheduling of processes on a computer are a combination of round robin and priority queues 
Implementing a FIFO queue of string elements using an ArrayList would have the following
methods:
void Enqueue(String S)
// add a new
element at 0 of the ArrayList and make it equal to the parameter S
String Dequeue()
// return the last
element of the ArrayList and
delete it
String Peek()
// return the last
element of the ArrayList but do NOT delete it
boolean IsEmpty()
// return true or false
depending if the ArrayList is empty