Don't like this style? Click here to change it! blue.css

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".

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.

Stacks

A stack of coins has two operations:

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):

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

Cute Queue

spelling troubles

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

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?

Steam Valve

If there is still time then implement a Queue using a linked list.

What changes?

Code Comments:

Code Comments