Stack

• Stacks can be implemented with either an array or a linked list
• Each stack operation takes O(1): Push, Top, Pop, Empty
• LIFO (Last In First Out) queues

Operations

• Push(Key): adds key to collection
• Key Top(): returns most recently added key
• Key Pop(): removes and returns most recently added key
• Boolean Empty(): returns a boolean if elements exist or not

Pros and Cons

• Additional pointer needs to be defined for every pushed element in a linked list
• Space can be wasted if we allocate a very large array in an array

Example

• Balanced Brackets