What is the Stack?
Stack is an abstract linear data structure.
Stack is a first-in-last-out data structure. The element that is added first is removed last. We can also term it as last in first out. In stack the most recent element is termed the top element.
Stack natively doesn’t support index-based access, unlike array. A new element can only be added to the top of the stack and it becomes the top of the stack. Stack is a widely used data structure in various day-to-day applications. The stack is used in the implementation of the operating system kernel and also in the language compiler implementation. Stack is used to reporting active stack frames at a certain pointing time during the execution of a program.
Pros of the Stack
- Constant time insertion and deletion from the top of the stack in LIFO order.
- Dynamic memory allocation, unlike an array.
Cons of the Stack
- Only single-time traversal is possible.
- Doesn’t support searching.
- Random access is not possible.
Applications of the Stack
- Call stack implementation for program execution, to store active stack frames.
- Arithmetic expressions evaluations. Conversion of infix expression into its postfix or prefix equivalent,
- Web browser back and forward button implementations.
- Undo/Redo features in Text editors.
Stack Operations
Some common operations in the stack are:
- push: Add a new element on the top of the stack.
- a. For efficiency enqueue operation should be of constant complexity.
- pop: Remove an element from the top of the stack and returns it.
- a. For efficiency dequeue operation should be of constant complexity.
- peek: Returns the top element without removing it.
- is_empty: Check if the stack is empty
- Is_full: Check if the stack is full.
Implementations of the Stack using Python
Python’s inbuilt list data structure can be used to implement the Stack basic operations with constant complexity O(1).
Python inbuilt list provides append and pop methods, which is O(1) complex.
Let’s define the constructor of the stack, here we will initialize a list container to store the stack values.
We will also define the maximum allowed size of the stack, upon reaching this size user won’t be able to add new elements until removing or popping stack values.
class Stack:
"""Implementation of the stack.
Args:
max_size: Maximum size of the stack.
"""
def __init__(self, max_size: int):
self.max_size = max_size
self._data = []
self.size = 0
Push operation
Using the list inbuilt append method we can implement the push operation that has constant time complexity O(1).
Upon adding the element on the top of the stack, we also increase the size of the stack to keep track of the stack size.
def push(self, value: Any) -> None:
"""Add an element to the stack.
Args:
value: Value to push to the stack.
Raises:
ValueError: If the stack is full.
"""
if self.size == self.max_size:
raise ValueError("Stack is full.")
self._data.append(value)
self.size += 1
Pop operation
We can use the list inbuilt pop method to implement the pop operation in constant time complexity O(1).
We also decrease the size of the stack upon removing the top element of the stack.
def pop(self) -> Any:
"""Pop the top element from the stack.
Returns:
Top of the stack.
"""
self.size -= 1
return self._data.pop()
Rest of the stack operations are straightforward and similar to the queue.
Below is the full implementation of the Stack.
from typing import Any
class Stack:
"""Implementation of stack.
Args:
max_size: Maximum size of the stack.
"""
def __init__(self, max_size: int):
self.max_size = max_size
self._data = []
self.size = 0
def push(self, value: Any) -> None:
"""Add an element to the stack.
Args:
value: Value to push to the stack.
Raises:
ValueError: If the stack if full.
"""
if self.size == self.max_size:
raise ValueError("Stack is full.")
self._data.append(value)
self.size += 1
def pop(self) -> Any:
"""Pop the top element from the stack.
Returns:
Top of the stack.
"""
self.size -= 1
return self._data.pop()
def is_empty(self) -> bool:
"""Check if the queue is empty.
Returns:
A bool indicating if the stack is empty.
"""
return not self.size
def is_full(self) -> bool:
"""Check of the stack is full.
Returns:
A bool indicating if the stack is full.
"""
return self.size == self.max_size
def peek(self) -> Any:
"""Returns the top element without removing it.
Returns:
Top element of the stack.
"""
if not self.is_empty():
return self._data[-1]
return None
if __name__=="__main__":
stack = Stack(3)
stack.push(1)
stack.push(2)
stack.push(3)
print(stack.peek())
print(stack.is_empty())
print(stack.is_full())
print(stack.pop())
print(stack.pop())
print(stack.pop())
print(stack.peek())
print(stack.is_empty())