[Data Structure] Stack (ADT)

Stack

 

Stack is an Abstract Data Type (ADT) in which items are only inserted on or removed from the top of a stack. 

The stack push operation inserts an item on the top of the stack. 

The stack pop operation removes and returns the item at the top of the stack. 

 

A stack is referred to as a Last-In First-Out (LIFO) ADT. 

A stack can be implemented using a linked list, an array, or a vector. 

 

Common Stack ADT Operations

 

 

Suppose we implement a stack ADT using a linked list, where the first element at the head of the linked list will be the top, and the tail will be the bottom.Then, the push function will prepend a new node to the list, and pop function will remove the head node. 

Simple.

 

 

Python: Array Based Stacks

Now, we want to implement it with an array, so it will be an array-based stacks. 

It will have to object variables in addition to the array:

1. allocation_size, an integer for the array's allocated size and
2. length, an integer for the stack's length. 

 

If the stack is empty, the length is 0 and the top element is at array[length - 1].

 

Let's start with an unbounded stack, a stack that has no limit for its allocation_size. 

Usually, we start with an empty array-based stack. 

Then we will start pushing elemnets to it.

 

When we push element to the array, we will need to check if allocation_size == length, and if it is, we will need to resize the array by changing the allocation_size. 

There are many ways you can resize it. 

One good option that we will use is to double the allocation_size when we need to resize. 

 

Now, if we double the allocation_size there will definitely be a limit of the size because we have a limited memory. How about limiting the size manually so that it doesn't occupy excessive memory location? Here comes the bounded stack. 

 

There are two common ways of implementing the bounded stack. 

1. We can replace allocation_size to max_length when initializing or
2. We can use additional object variable max_lengt, and update allocation_size starting from 1.

 

Let's try implementing it with Python lists! 

class Stack:
    def __init__(self):
        self.stack_list = list()

    def pop(self):
        return self.stack_list.pop()

    def push(self, new_data):
        self.stack_list.append(new_data)

 

If we use Python lists, we don't actually have to handle maximum length and allocation size manually becaues Python does it for us! We can simply use the builtin methods pop and push of list object to create Stack class.

That was obviously unbounded stack. 

Let's make it to consider for boundaries so that it can be a bounded stack. 

 

class Stack:
    # Initializes the stack. If the optional_max_length argument is omitted or 
    # negative, the stack is unbounded. If optional_max_length is non-negative, 
    # the stack is bounded.
    def __init__(self, optional_max_length = -1):
        self.stack_list = []
        self.max_length = optional_max_length
    #
    # Pops and returns the stack's top item.
    def pop(self):
        return self.stack_list.pop()
    #
    # Pushes an item, provided the push doesn't exceed bounds. Does nothing 
    # otherwise. Returns True if the push occurred, False otherwise.
    def push(self, item):
        # If at max length, return false
        if len(self.stack_list) == self.max_length:
            return False
        #
        # If unbounded, or bounded and not yet at max length, then push
        self.stack_list.append(item)
        return True

We set one additional optional object constructor's parameter optional_max_length for the maximum length of the bounded stack. 

If the value is negative, then it means that the stack is unbounded, and vice versa. 

When we try to push a new item to the stack, if the current length of the array is equal to the maximum length, then it will not append the item and return False.