The underlying data structure for a stack can be either an array or a linked list. Stack data structures exhibit a first in last out (LIFO) characteristics. When messages 1,2,3 are pushed into the Stack, these messages can only be retrieved in the order of 3,2,1.

Stacks can be represented using an internal or linked list. Each implementation has its unique advantage/disadvantages. Since stacks do not allow un-ordered insertion/deletion, operations for insertion/deletion have constant time time complexity. O(1). In summary:

O(operation)

O(1)

insertion

Y(es)

deletion, e.g.: (pop)

Y

peek

Y

Stack array

Internally an array is used to store the data according to the array index. The ordered access of the array elements means that elements do not need to shifted when insertion/deletion occurs. The array keeps track of its current array position using tail.

Instead of using an internal array to store data, a Linked list implementation of a stack store data in nodes (objects). Each node object references the neighboring node by “next” reference.