stacks and queues

Stacks store/retrieve pattern

LIFO

stacks analogy

stack of trays in a cafeteria

• can only add to top

• can only remove from top

• cannot remove from middle

.push();

adds argument element to top of stack

.pop()

retrieves and removes stack’s top element

.peek();

retrieves but does not remove stack’s top element

Stack and queues similarity 1

modularly resizable (like arraylists)

queues store/retrieve pattern

FIFO

queues analogy

line of people

• add to back

• remove from front

• cannot retrieve/remove from middle

.add();

adds argument element to back of queue

.remove();

retrieves and removes queues front element

if empty, throws an exception

.poll();

same as remove, but returns null is queue is empty

.peek();

retrieves but does not remove queues front element

queue java API

interface

Queue instantiation

Which of the following is/are valid?:

#1.) Queue<Student> = new Queue<Student>();

#2.) Queue<Student> = new LinkedList<Student>();

#3.) LinkedList<Student> = new Queue<Student>();

#4.) Student<Queue> = new Student<Queue>();

2

ideal stack and queue time complexity

constant time

could we implement stack using an arraylist?

yes

Could we implement a Queue using an ArrayList?

no

Could we implement a Queue using a LinkedList (w/ front only)?

no

Could we implement a Queue using a LinkedList (w/ front and back)?

yes