#SideNotes — Stack — Abstract Data Type and Data Structure
In this #sidenotes we will talk about Stack as an Abstract Data Type and as a Data Structure.
Abstract data types, commonly abbreviated ADTs, are a way of classifying data structures based on how they are used and the behaviors they provide. They do not specify how the data structure must be implemented but simply provide a minimal expected interface and set of behaviors.
Data Structure is a concrete implementation of a data type. It’s possible to analyze the time and memory complexity of a Data Structure but not from a data type. The Data Structure can be implemented in several ways and its implementation may vary from language to language.
Stack — Abstract Data Type
The distinguishing characteristic of a stack is that the insertion or removal of elements takes place at the same end.
Stack holds a collection of elements but different from the Array or List those elements can only be manipulated from one end of the stack. This end is commonly known to be the top of the stack.
The principle by which a stack is ordered is called LIFO (last-in first-out).
The last element inserted in the stack would be the first element removed from the stack.
It’s possible to see a Stack as a pile of books, the last book inserted on the top of the pile is the easiest book to be removed from that pile.
ADT — Interface
The Stack interface can be implemented in different ways, is important to have operations to push a new element and to pop an element:
# Main operations
push(element) -> Add an element to the top
pop() -> Remove the element from the toppeek() -> See what is the element in the top
isEmpty() -> Check if the stack is empty
Since abstract data types don’t specify an implementation, this means it’s also incorrect to talk about the time complexity of a given abstract data type.
ADT — Operations
Traversal : You must be thinking, “how could I print all the elements of a Stack?”
A Stack can be traversed , is possible to navigate in the stack using the pop to remove the element from the top until the stack is empty.
stack = Stack()
stack.push(1) # 1 is added to the top
stack.push(2) # 2 is added to the top
stack.push(3) # 3 is added to the top# Stack looks like = Stack(3, 2, 1)stack.peek() # 3 is the top element in the stackwhile the is not stack.isEmpty()
print stack.pop() # The elements will be printed in this order: 3 -> 2 -> 1
This is an abstract operation and the implementation will define how you interact with the Stack.
Stack — Data Structure
Implementation
A Stack can be implemented in several ways, some implementations use an Array and store the top reference to manipulate the stack of elements. It’s also possible to use a LinkedList taking advantage of the insertion and removal from the beginning is an O(1) operation.
We can achieve the O(1) either with an Array or LinkedList to the push and pop operations.
We will see both ways of implementing the Stack and then it’s up to us to decide what is better for the problem we are solving :)
To have in mind:
Stacksare simple and can be implemented using Arrays or Linked List. The implementation here is to show the concepts and to fulfill the ADT, this is not a code designed to be used in production :)
Implementation using Array
C — Implementation using Array
This is a simple implementation of a Stack using the C language. In this case, we are using an array to store the data and we need to define the Stack size when creating it. This is an implementation constraint and this could be implemented in several ways.
We use theitems array to hold the data and then we have the top pointer to determine what item in the stack we are manipulating.
The important behavior here is to always manipulate one end of the Stack.
Golang — Implementation using Array
We can also implement this in Golang but there’s no much difference. Our implementation is simple and is not being as optimized to memory as it could be.
Note: We are not exporting the methods because this is a one file example.
Python — Implementation using an Array
We can use a list in Python and create an abstraction to make it behave like a Stack.
Complexity
# Stack - Using an Array
# Running timeO(1) -> push
O(1) -> pop# Stack - Using an Array
# MemoryO(N)
Implementation using Linked List
It could be easily implemented using a LinkedList too and this can be a good exercise if you want to implement a stack and a linked list :)
