7. Stacks and Queues#
An Abstract Data Type (ADT) is a type (or class) for objects whose behavior is defined by a set of value and a set of operations.
The definition of ADT only mentions what operations are to be performed but NOT how these operations will be implemented.
It does NOT specify how data will be organized in memory and what algorithms will be used for implementing the operations. It is called “abstract” because it gives an implementation-independent view, thus providing only the essentials and hiding the details.
Stacks and Queues are two ADTs that are used to store data in a particular order.
A Stack is a collection of elements, with two main principal operations:
Push, which adds an element to the collection, and
Pop, which removes the most recently added element that was not yet removed.
The order in which elements come off a stack gives rise to its alternative name, LIFO: Last In, First Out.
A Queue is a collection of elements, with two main principal operations:
Enqueue, which adds an element to the collection, and
Dequeue, which removes the earliest added element that was not yet removed.
The order in which elements are removed from a queue gives rise to its alternative name, FIFO: First In, First Out.