Stacks and Queues

• Stack: collection of items with last in, first out retrieval
• Queue: collection of items with first in, first out retrieval

Abstract Data Type (ADT)

• First let's define data type
  • a set of values and the associated operations on those values
• in Java, the most basic data types are primitive data types

Integers as data types

• What numbers are in the set of integers?
  • all the whole numbers, positive, negative, and zero
• What operations can be performed on these values?
  • Addition, subtraction, multiplication, division, modulus
• Integers have
  • a set of values
  • associated operations.
  • It is a data type.
• In Java, we call them ints

Boolean as a data type

• What is the set of values?
  • true and false.
• What are the operations?
  • AND (&&), OR (||) and NOT (!).
• Boolean has
  • a set of values
  • associated operations.
• It is a data type.

Java objects as data types

• We put primitive data types together in aggregates
• The operations on the data are defined in methods
• An objects has
  • a set of values (instance variables)
  • associated data (methods)
• It become new data types

Abstract Data Type

• has a set of values (objects)
• the basic operations that can be performed on that collection of data.
• It defines a new data type
• The concept is similar to a class

Abstract Data type

• defines the fundatmental operations on the data
• does not define the implementation
• There can be different implementations

Abstract Data Type

• There are two important parts to an ADT:
  • its specification ( the data and operations) and
  • its implementation (how the data is stored and the algorithms to accomplish the operations).
• there can be more than one implementation
• The user of the ADT does not need to know anything about the implementation.
  • I need to know that ArrayList has add and get methods.
  • I do not know or care how the data is actually stored or how the methods are implemented.
• In Java, abstract data types are implemented as classes

Array ADT

Array ADT An array Abstract Data Type is a ordered sequence of elements. It provides random access to a specific element in O(1) time by specifying an integer index.

• In Java, an array is one implementation of the array ADT
• ArrayList is another implementation

List ADT

List ADT A list Abstract Data Type is a ordered sequence of elements that can be traversed sequentually and allows for insertion and removal of elements at any position in O(1) time.

• LinkedList is one implementation

Stack

• Allows insertion and removal of elements only at one end
  • Traditionally called the top of the stack
• New items are added to the top of the stack
• Items are removed at the top of the stack
• Called last in, first out or LIFO order
• Traditionally, addition and removal operations are called push and pop
• Think of a stack of books:
  

Stack ADT

Stack ADT A stack Abstract Data Type is a collection of elements that allows access only at one end, called the top. It is structured such that the last element added will be the first element removed.

• This type of retrieval is called "last in, first out" or LIFO order.
• Implementation
  • implemented using a LinkedList
  • implemented using an array

Stack Operations

• push
• pop
• empty
• And also peek

Stacks in the Java Library

• Class Stack implements the abstract data type, stack
  • has the push and pop operations
  • also peek to look at the top of the stack without removing it
  • There is no Stack interface

Working with Stacks

• Stack class in java.util

Stack<Integer> s = new Stack<>();	Constructs an empty stack.
s.push(1); s.push(2); s.push(3);	Adds to the top of the stack; s is now [1, 2, 3]. (Following the toString method of the Stack class, we show the top of the stack at the end.)
int top = s.pop();	Removes the top of the stack; top is set to 3 and s is now [1, 2].
head = s.peek();	Gets the top of the stack without removing it; head is set to 2.
boolean b = s.empty()	Sets b to false. Same as s.size() == 0.

Queue

• Add items to one end of the queue (the tail)
• Remove items from the other end of the queue (the head)
• Queues store items in a first in, first out or FIFO fashion
• Items are removed in the same order in which they have been added
• Think of people lining up:
  • People join the tail of the queue and wait until they have reached the head of the queue

A Queue

Queue ADT

Queue ADT A queue Abstract Data Type is a collection of ordered elements structured such that the first element added will be the first element removed.

• This type of retrieval is called "first in, first out" or FIFO order.
• Items are added at one end of the queue (the tail) and removed from the other end (the head).
• Items in a queue "wait their turn."
• Implementation
  • implemented using an array
  • implemented using a linked list

Queue Operations

• add (enque)
• remove (deque)
• empty
• can also peek

Queues in the Java Library

• Queue interface defines a queue abstract data type
• Methods of Queue interface in the standard Java library include:
  • add to add an element to the tail of the queue
  • remove to remove the head of the queue
  • peek to get the head element of the queue without removing it
• The LinkedList class implements the Queue interface, and you can use it when a queue is required:

  Queue<String> queue = new LinkedList<String>();

Working with Queues

• There is a Queue interface defined in the API
• LinkedList implements the Queue interface
• Declare a Queue instance variable and instantiate a LinkedList

  Queue<Integer> queue = new LinkedList<Integer>();

Working with Queues

Queue<Integer> q = new LinkedList<>();	The LinkedList class implements the Queue interface.
q.add(1); q.add(2); q.add(3);	Adds to the tail of the queue; q is now [1, 2, 3]
int head = q.remove();	Removes the head of the queue; head is set to 1 and q is [2, 3]
head = q.peek();	Gets the head of the queue without removing it; head is set to 2.
boolean b = s.empty()	Sets b to false. Same as s.size() == 0.

Priority Queues

• A collection of items, each with a priority
• Add elements in any order
• Remove the most urgent one
• Not a queue!

Priority Queue

• give low values to urgent priorities
• priority 1 denotes the most urgent priority.
• Thus, each removal operation extracts the minimum element from the queue.

Priority Queue Example

Look at this code

• assume we have a WorkOrder class
  • has a priority
  • has a description

PriorityQueue<WorkOrder> q = new PriorityQueue<WorkOrder>();
q.add(new WorkOrder(3, "Shampoo carpets"));
q.add(new WorkOrder(1, "Fix broken sink"));
q.add(new WorkOrder(2, "Order cleaning supplies"));

Priority Queue Example cont.

Call q.remove() for the first time

• the work order with priority 1 is removed.
• if there are two elements with the same priority
  • the priority queue will choose arbitrarily
• priority queue needs to be able to tell which element is the smallest
  • elements in the should belong to a class that implements the Comparable interface

Working with Priority Queues

PriorityQueue<Integer> q = new PriorityQueue<>();	This priority queue holds Integer objects. In practice, you would use objects that describe tasks.
q.add(3); q.add(1); q.add(2);	Adds values to the priority queue.
int first = q.remove(); int second = q.remove();	Each call to remove removes the most urgent item: first is set to 1, second to 2.
int next = q.peek();

Thoughts to ponder

• Why would you want to declare a variable as
  Queue<String> q = new LinkedList<String>()
  instead of simply declaring it as a linked list?
• Would it be a good idea to use a stack to manage print jobs?

Class Question 1

What does this code print?

Stack<Integer> s = new Stack<>();
Queue<Integer> q = new LinkedList<>();
PriorityQueue<Integer> p = new PriorityQueue<>();
s.push(1); s.push(3); s.push(2);
while (s.size() > 0) q.add(s.pop());
while (q.size() > 0) p.add(q.remove());
while (p.size() > 0) System.out.print(p.remove() + " ");

1. 1 3 2
2. 1 2 3
3. 3 2 1
4. 2 3 1

Stacks and Queues: Uses in Computer Science

• Queue
  • Event queue of all events, kept by the Java GUI system
  • Queue of print jobs
• Stack
  • Run-time stack that a processor or virtual machine keeps to organize the variables of nested methods
  • expression evaluation in compilers

Application: Balancing Parentheses

• Easy to check whether parentheses are balanced
• Example: -(b * b - (4 * a * c ) ) / (2 * a)
• Increment counter at (, decrement at )
• Counter must be 0 at end and never < 0 in the middle
• What if we have different kinds of parentheses?
• –{ [b ⋅ b - (4 ⋅ a ⋅ c ) ] / (2 ⋅ a) }
• Push them on a stack

Application: Balancing Parentheses

When you see an opening parenthesis, push it on the stack.
When you see a closing parenthesis, pop the stack.
If the opening and closing parentheses don’t match
   The parentheses are unbalanced. Exit.
If at the end the stack is empty
   The parentheses are balanced.
Else
   The parentheses are not balanced.

Application: Balancing Parentheses

Evaluating Reverse Polish Expressions

• Infix operators need parentheses to specify what comes first: (3 + 4) * 5
• Polish notation: Write operator before operands
• * + 3 4 5
• Invented by the Polish mathematician Jan Łukasiewicz
• Reverse Polish: Write them after the operand
• 3 4 + 5 *
• Used in classic pocket calculators and the Java virtual machine

Reverse Polish Notation

If you read a number
   Push it on the stack.
Else if you read an operand
   Pop two values off the stack.
   Combine the values with the operand.
   Push the result back onto the stack.
Else if there is no more input
   Pop and display the result.

Reverse Polish Notation

Lecture 15 Clicker Question 2

How do you write (3 + 4) x 5 + 6 in Reverse Polish?

1. 3 4 5 x + 6 +
   
2. 3 4 + 5 x 6 +
   
3. 3 + 4 5 x + 6
   
4. None of the above

Evaluating Algebraic Expressions

• Regular notation, not reverse polish
• Push numbers on one stack, operators on another
  
• Core step—evaluating the top:
  
  • Pop two numbers
  • Pop an operator
  • Apply operator to numbers
  • Push the result

  Number stack	Operator stack	Unprocessed input	Comments
  		3 + 4
  3		+ 4
  3	+	4
  4 3	+	No more input	Evaluate the top
  7			The result is 7

Operator Precedence

• * has higher precedence than +
• * and / have the same precedence
• Don't push an operator if it has higher precedence than the top operator. Instead, evaluate the top.
  

  Number stack	Operator stack	Unprocessed input	Comments
  		3 * 4 + 5
  3		* 4 + 5
  3	*	4 + 5
  4 3	*	+ 5	* has higher precedence Evaluate the top
  12	+	5	Now push +
  5 12	+	No more input	Evaluate the top
  17			The result is 17

Parentheses

• Push a left parenthesis "("
• When encountering a right parentesis ")", evaluate the top until the left paren "(" reappears

  Number stack	Operator stack	Unprocessed input	Comments
  		3 * (4 + 5)
  3		* (4 + 5)
  3	*	(4 + 5)
  	( *	4 + 5)
  4 3	( *	+ 5)
  4 3	+ ( *	5)
  5 4 3	+ ( *	)
  9 3	( *	No more input	Evaluate the top
  9 3	*		Pop matching (
  27			Evaluate the top—the result is 27

Complete Algorithm

If you read a number
	 Push it on the number stack.
Else if you read a (
	 Push it on the operator stack.
Else if you read an operator op
	 While the top of the stack has a higher precedence than op
		 Evaluate the top.
	 Push op on the oper­ator stack.
Else if you read a )
	 While the top of the stack is not a (
		 Evaluate the top.
	 Pop the (.
Else if there is no more input
	 While the operator stack is not empty
		 Evaluate the top.

Backtracking

• Escaping from a maze
  
• Use a stack to remember all paths that still need to be tried
• At an intersection, push all paths
• Pop one and follow it
• When a path is a dead end, pop the next one (that's the backtracking)
  
• Repeat until exit
• Can use a queue as well, but not as intuitive (you don't just go back to the last choice)

Maze Escape Example

Maze Escape Pseudocode

Push all paths from the point on which you are standing on a stack.
While the stack is not empty
	 Pop a path from the stack.
	 Follow the path until you reach an exit, intersection, or dead end.
	 If you found an exit
		 Congratulations!
	 Else if you found an intersection
		 Push all paths meeting at the intersection, except the current one, onto the stack.