Python Data Structures and Algorithms

Stack implementation

Now let us study an implementation of a stack in Python. We start off by creating a node class, just as we did in the previous chapter with lists:

class Node:     def __init__(self, data=None):         self.data = data         self.next = None 

This should be familiar to you by now: a node holds data and a reference to the next item in a list. We are going to implement a stack instead of a list, but the same principle of nodes linked together still applies.

Now let us look at the stack class. It starts off similar to a singly linked list. We need to know the node at the top of the stack. We would also like to keep track of the number of nodes in the stack. So we will add these fields to our class:

class Stack:     def __init__(self):  self.top ...