Warm-Up Question

Find two functions \(f(n)\) and \(g(n)\) that satisfy the following relationship. If no such \(f\) and \(g\) exist, write "None".

• \(f(n) = \mathcal{o}(g(n))\) and \(f(n) \neq \Theta(g(n))\)
• \(f(n) = \Theta(g(n))\) and \(f(n) = \mathcal{o}(g(n))\)
• \(f(n) = \Theta(g(n))\) and \(f(n) \neq \mathcal{O}(g(n))\)
• \(f(n) = \Omega(g(n))\) and \(f(n) \neq \mathcal{O}(g(n))\)
• \(f(n) = \omega(g(n))\) and \(f(n) = \mathcal{O}(g(n))\)

Class 14: Stacks and Queues

Fast schedulers. These data structures are made for loading and unloading data where the order matters. You will almost certainly remember them because they are useful and simple.

A stack of coins has two operations:

• push(coin) which puts a coin on top
• pop() which gets the top coin

Here is a simple stack implementation:

LIFO vs FIFO Task 1: Would you describe this data structure as "First In First Out" or "Last In First Out"?

Complexity Task 2: What is the complexity of Push? What is the complexity of Pop?

Design Task 3: How could you design the Mult-Set (Bag) ADT using a Stack as the underlying data structure? What complexity do you get for each operation?

Find Min Task 4: Design an implementation of Stack which also includes find_min(). Design it so that pop(), push(x), and find_min() all have \(\mathcal{O}(1)\) worst-case performance. (pop is the tricky one.)

ASIDE: Polish Notation, if you want to make a simple expression evaluator, use a stack and "reverse polish notation":

((1 + 2) * 3) - (36 / (2 + 4)) becomes:

3 1 2 + * 36 2 4 + / -

Here is a stack-based algorithm (read from left):

• If you encounter a number then PUSH it onto stack
• If you encounter an operator then POP two numbers from stack and do operation
• PUSH the result back onto the stack
• When you have finished reading POP your result

Simple Eval Task 5: Use my Stack with template ints. Allow only "+" and "*" as operations, and only single digit inputs. Write code to evaluate "643+*9*" (378 is the result).

At Home Task 6: Write a stack which uses a linked list as the underlying data structure. Pros: never overflow. Cons: heap memory is allocation is slow.

Queues

Queues are data structures that ensure fairness! The operations are:

• Enqueue(x) put x at the end
• Dequeue() return the first item

Here is a simple implementation:

LIFO or FIFO? 7: You know what to answer.

Interpret Task 8: Why do I do head = head + 1 % max? Why does tail go up by one and not down by one?

Design Task 9: If you wrote code for a call center, routing calls for assistance, why would you choose a Queue over a Stack?

Recursive Task 10: If you were writing a coding language and wanted to implement a recursive program would why would you use a Stack over a Queue?

Code Comments: