Java Chapter 14 - Stacks and Queues

14.1 Stacks

A stack is collection of data items that follows the list-in first-out (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)*(8-4)*(5-3)

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 first-in first-out (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