A Discussion on Stack ADT

"Stack" - is a very basic and neatly designed Abstract Data Type that is available to us. If we have to describe the structure of the STACK ADT, it can be simply said as a ADT which follows LIFO queue servicing model. It is very much similar to a Stack of Plates. When you want to add a plate to the Stack, you add the new plate to the top end of the Stack and if you want to remove a plate from the stack, you do it the same way i.e., remove the plate from the top end of the stack.

Advantage :
It is easy to implement.
The accessor methods ( PUSH & POP) are much simpler than the accessor methods of most other ADTs.
Easy to handle the data using Stack ADT.

Implementation Details :
Stack are usually implemented with Arrays. Arrays are the most primitive Data type that is usually available with any programming language. In Stack, we simply abstract the access to the array and restrict the access only to the last element ( top most element of the stack). By using array, we can implement the basic accessor methods i.e., PUSH & POP in O(1) time. We simply store the last element's index and access is using Array indexing. Hence it is accessible in Constant time. ie., O(1).

Assume Stack is implemented using an array Stack[] of size N and the index of the top most element in the Stack is stored in "top". The parameter "o" refers to the generic Object which can be anything from int to float.

Other supporting methods ( can be implemented easily for any array):
size() - returns the current size of the Stack.
isEmpty() - returns boolean value telling whether the Stack is empty or not.

PUSH(o) :
if Stack.size() == N then
throw stackFullError
Else
top <- top + 1
Stack[top] <- o

POP():
if Stack.isEmpty() then
throw stackEmptyError
Else
o <- Stack[top]
Stack[top] <- null
top <- top - 1
return o


The problem in the above implementation is the array size should be initialized at the beginning. Thus if the stack size turns out to be small, space is wasted and if stack size turns out to be large, then the stack can crash when array indexing exceeds the upper limit.

Solution:
Thus it is better to use Linked List in place of Array when space efficiency is our main concern.
Traditionally, we have a link to the head of the Linked List and we update the elements at the end opposite to the head of the Linked list. But the problem in using Linked List is the accessor methods turns out to be O(t) where t refers to the current size of the stack. Here, a reference to the Head of the Linked List is not absolutely necessary at all. The main aspect of Stack is they allow access only at one end of the ADT. Hence holding a pointer to the top most end of the stack should improve the accessor method's running time. Thus, we can simply implement the linked list in reverse order and hold pointer to the head.

Linked List Structure:

topmost -> n-1 -> n-2 -> ........ -> bottommost

Here by holding a pointer to the topmost element, we can implement PUSH & POP methods in O(1) time. Thus Stack turns out to be an efficient ADT even while using Linked List. Hence using a reverse order of storage in Linked List, we get space efficient and time efficient Stack ADT.