CITS2200 - Lecture 7

← Back to Home

CITS2200 - Lecture 6
Stacks - Slides

Abstract Data Types

• Abstraction means that we hide implementation details and only focus on what something does, and not how it works
• An abstract data type is a high-level description of a data structure, it specifies:
  • Data stored
  • Operations allowed
  • Error conditions
• ADTs is not code but rather a concept

The Stack ADT

• The stack ADT stores arbitrary objects -> it stores anything
• Insertions & deletions follow last-in, first-out scheme (LIFO)

Supports several basic operations:

• push(object): insert element
• object pop(): remove and return last inserted element
• object top(): return last element (without removal)
• integer len(): return # of elements stored
• boolean is_empty(): indicates whether stack is empty

As the stack is an ADT, we have defined:

• What operations exist
• How they behave (LIFO)
• What errors occur (e.g. popping empty stack)

We do not know how these operations are actually implemented

Applications of Stacks

• Direct Applications
  • Page-visited history in a Web browser
  • Undo sequence in a text editor
  • Chain of method calls in a language that supports recursion
• Indirect applications
  • Auxiliary data structure for algorithms
  • Component of other data structures

Array-Based Stack

• Arrays can be used to implement a stack
• Add elements from left to right
• Variable keeps track of the top element index

• If array becomes full, push operation will need to grow array and copy all elements over

Spaces used is $O(n)$
Operation runs in time $O(1)$, amortized in case of a push
Push op expensive → $O(n)$, but only happen when array is full

---

CITS2200 - Lecture 8