Table of Contents
- Understanding of Stacks
- Implementing a Stack Using OOP Concepts in Python
- Stack Parent Class
- Stack Class with Array
- Stack Class with Linked List
- Using Stack Class as a User
Data structures are essential in computer science and programming for effectively organizing and manipulating data. The stack is one such fundamental data structure.
In this article at OpenGenus, we'll look about stacks in Python and how to use object-oriented programming (OOP) techniques to create them. Understanding stacks and how they are implemented will provide you a good basis for tackling a variety of challenges.
Understanding of Stacks
A stack is a linear data structure in computer science that follows the Last-In-First-Out (LIFO) principle. It is similar to a stack of objects, where the last object placed on top is the first one to be removed. Stacks have two primary operations: push and pop.
Push: The push operation adds an element to the top of the stack. It places the new element on top of the existing elements, becoming the new top element.
Pop: The pop operation removes and returns the top element of the stack. It removes the most recently added element from the top and updates the stack to reflect the new top element.
Implementing Stack Using OOP Concept in Python
Mainly there are two ways to implement stack in python they are using array or list and using linked list.
Both list or array-based stacks and linked list-based stacks have their own advantages and trade-offs. List-based stacks are suitable when the size of the stack is known or can be estimated, and fast access to elements is required. On the other hand, linked list-based stacks are more flexible in terms of dynamic resizing and efficient insertion and deletion operations at the top of the stack. The choice between the two depends on the specific requirements of the application and the desired trade-offs between time complexity and flexibility.
Stack Parent Class
We can have one parent class of
Stack and which can be inherited by two child classes one that imlement the stack using array and the other using linked list.
First lets create class `Stack'
class Stack: def __init__(self): self.count = 0 self.top = None def is_empty(self): return self.count == 0 @abstractmethod def push(self, item): pass @abstractmethod def pop(self): pass @abstractmethod def peek(self): pass
The above code is parent class which contains abstract methods to be overriden by child classes. In this class the methods have constructor called
@abstractmethod to indicate that the methods are abstract type and need to be overriden by child classes.
Stack Class with Array
- Implementing a stack using a list or array is a straightforward and commonly used approach.
- The list or array provides a built-in structure for storing elements, allowing for easy implementation of stack operations.
- Elements are added to the top of the stack using the append() method, and they are removed from the top using the pop() method.
- The top of the stack corresponds to the last element in the list or array.
- Accessing the top element of the stack is efficient as it can be directly accessed by index.
- List or array-based stacks have a fixed size unless dynamically resized.
- Adding or removing elements at locations other than the top of the stack may require shifting elements, resulting in less efficient operations.
We can create child class that inherit
Stack class to implement the stack using array.
class StackUsingArray(Stack): def __init__(self): super().__init__() self.stack =  def push(self, item): self.stack.append(item) self.count += 1 def pop(self): if self.is_empty(): print("Stack Underflow") else: self.count -= 1 return self.stack.pop() def peek(self): if self.is_empty(): print("Stack Underflow") else: return self.stack[-1] def size(self): return self.count
In the above code the
StackUsingArray inherits the
Stack class then manipulate
self.stack. This class used parent class abstract methods to manipulate the stack as an array.
__init__: by using
super().__init__()it inherit the whole parent constructor. Then instantantiate list for stack.
push: this method implement the push operation of stack on
self.stackarray. Then it increament the count by one since count used to indicate size and push add element to the stack on top of that.
pop: this method implement the pop operation of stack on
self.stackarray. It must check if the stack is not empty then it remove the top element from the stack after decreasing the
peek: this method simly returns the top element of the stack.
size: this method returns the size of the stack.
Stack Class with Linked List
- Implementing a stack using a linked list involves creating a custom class for the linked list and manipulating the pointers between nodes.
- Each node in the linked list contains the data and a reference to the next node.
- The top of the stack is represented by the head of the linked list.
- Adding an element to the stack involves creating a new node and updating the head pointer to point to the new node.
- Removing an element from the stack involves updating the head pointer to the next node.
- Linked lists can grow or shrink dynamically, as nodes can be easily added or removed.
- Insertion and deletion operations at the top of the stack are efficient, as they only require updating the head pointer.
- Accessing elements at arbitrary positions in the stack requires traversing the linked list, which can be less efficient compared to direct indexing in a list or array.
We can also extend the same class and implement the stack in Linked List. But first we must create
class Node: def __init__(self, data): self.data = data self.next = None class StackUsingLinkedList(Stack): def __init__(self): super().__init__() self.top = None def push(self, item): new_node = Node(item) new_node.next = self.top self.top = new_node self.count += 1 def pop(self): if self.is_empty(): print("Stack Underflow") else: item = self.top.data self.top = self.top.next self.count -= 1 return item def peek(self): if self.is_empty(): print("Stack Underflow") else: return self.top.data def size(self): return self.count
The abover class also inherit the
Stack class and manipulate the data by overriding the abstract method like array one, but different implementation as we want to make stack as linked list.
Nodeclass: this class used to create a node for the linked list used in stack later. The constructor had data and top this indicated the top of the stack.
push: this method perform the push operation on stack as linked list. First it created new node as object of
Nodeby data passed by the user. Then it makes the new node's next the top to make the new pushed node the top.
pop: this method simply remove the top noder from the linked list. It does this by changing the top to the first node connected to the current top.
peek: this method return the data of the top node.
size: it return the value of the
countvariable, which is size.
Using Stack Class as a User
The above code inherit
Stack class and implement stack using linked list.
You can create objects of this class and uses them accordingly:
# Create an object of StackUsingArray array_stack = StackUsingArray() array_stack.push(10) array_stack.push(20) print(array_stack.peek()) # Output: 20 print(array_stack.size()) # Output: 2 array_stack.pop() print(array_stack.is_empty()) # Output: False # Create an object of StackUsingLinkedList linked_list_stack = StackUsingLinkedList() linked_list_stack.push("A") linked_list_stack.push("B") print(linked_list_stack.peek()) # Output: B print(linked_list_stack.size()) # Output: 2 linked_list_stack.pop() print(linked_list_stack.is_empty()) # Output: False
We don't have to create object of the parent class to use the stack. We can simply create the child class object based on our preference: if we want to use array stack we can create object of
StackUsingArray use the methods to perform the operations.
If we want to use linked list we can create object of
StackUsingLinkedList and call the methods insider the class.
Inheritance principle helped as to write clean code and less redundant code as both classes inherit common class.
Using object-oriented programming techniques in Python to implement stacks allows us to encapsulate the stack's functionality and gives an accessible and modular method to interact with stacks. The Stack class we built simplifies push, pop, peek, and isEmpty actions, making it easier to handle and modify data in a last-in, first-out fashion.
Understanding stacks and their implementation utilizing OOP ideas is critical for efficiently tackling various programming challenges. By understanding stack principles and using the power of OOP, you'll be prepared to handle increasingly complicated data structures and algorithms, allowing you to develop cleaner and more maintainable code.