Stack

---

Access

Arrays are random-access data structures

• each element can be accessed directly and in constant time.

A linked list is a sequential-access data strucutre

• each element can be accessed only by traversing the list.

A stack and a queue are restricted or limited-access data structures.

• You can only access the element at the front or back position.
• Limiting operations creates efficient implementations.

Stack

Stack is an ADT where operations are done on one end of the collection and access to all other positions are restricted.

• LIFO: last in and first out.
• push adds elements
• pop removes the most recently added element that was not yet moved.
• top returns the top value without removing it

We split top and pop because single responsibility principle tells us that every unit of program should only have a single responsibility.

LinkedList implementation: the head of the linked list is the top of the stack. Array implementation: the top of the stack is at the end of the array.

Dynamic array stack

We can't always assume that an array is going to be sufficiently big. If the stack is at full capacity, and another value is pushed, an exception will be thrown. We can grow the underlying array reactively by allocating a new array and copy each element from the original array each time we push when the array is full.

• Its amortized runtime is 1. Most of the time, it is O(1), but once in a while, its more than O(n), but it balances out .

Amortized Analysis

More common for data structures (instead of algorithms) since they perform sequences of operations.

The motivation for amortized analysis is that looking at the (worst-case) runtime per operation rather than sequence of operations can be too pessimistic.

How to: Add up the total cost of all the operations in the sequence and divide it by the number of operations to get the amortized runtime.

It is different from average case analysis because average case analysis describes the typical input. We describe the input with the probability of it happening. We ende up with a probabilistic analysis. Amortized analysis looks at the entire sequence of operations instead of one operation with one input.

We call it "the amortized cost is..."

Example: Suppose we perform 10 operations with cost 1, and 1 operation with cost 10. The amortized cost for this sequence of operations would be 20/11 = 2. We can perform the same operation several times and calculate the amortized cost per operation