Stack

LIFO

• push()
• pop()

Implementation

stack

• 用一个top variable track the end of the stack
• just append to the end and pop from end

def pop():
    value = self.stack[top]
    self.top -= 1
    return

def push(val):
    self.top += 1
    self.stack[top] = value

if overflow, resize the array

linked list

• head as a dummy node
• push(), 不断地insert到head
• pop(), 从head pop

no overflow problem