Abstract Data Types: Containers

What is a container?

A container is a sequential abstract data type that behaves like a black box where following rules have to be obeyed:

What are the operations a container requires?

Although, as an abstract data type, container comes with no implementation, it requires from data structures that implement it to provide support for a minimal set of operations:

Operation Arguments Returns Description
clear   void Clears container of all values.
size   ULONG Gets container size
isEmpty   bool Checks if container is empty
push VALUE void Pushes value to head @ stack or tail @ queue.
peek   VALUE Gets value in container head @ stack or tail @ queue.
pop   VALUE Removes entry in container head @ stack or tail @ queue and returns its value.

What are the data structures that implement container?

Most common implementations of containers are:

Time complexity table using Big O Notation becomes:

Operation Stack Queue
clear O(N) O(N)
size O(1) O(1)
isEmpty O(1) O(1)
push O(1) O(1)
peek O(1) O(1)
pop O(1) O(1)

Share