Abstract Data Types: Containers

├─ What is a CONTAINER
├─ What are the operations a CONTAINER requires
└─ What are the data structures that implement CONTAINER

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:

only push & pull operations are supported
insertion, access and deletion is done only on head or tail
size can be bounded, in which case an exception will be thrown if data inserted is out of bounds
no iteration is supported

How values are added to container tail:

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.

Where:

VALUE: value of a container entry

What are the data structures that implement container?

Most common implementations of containers are:

Stack: a LIFO container using a List as storage
Queue: a FIFO container using a List as storage

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)