# #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 Structureis 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 notstack.isEmpty()# The elements will be printed in this order: 3 -> 2 -> 1

print stack.pop()

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:`are 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 :)`

Stacks

## 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 the`items`

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 :)