The Stack ADT can be implemented in several ways. The two most common approaches in Python include the use of a Python list and a linked list. The choice depends on the type of application involved.
Using a Python List
The Python list-based implementation of the Stack ADT is the easiest to implement. The first decision we have to make when using the list for the Stack ADT is which end of the list to use as the top and which as the base. For the most efficient ordering, we let the end of the list represent the top of the stack and the front represent the base. As the stack grows, items are appended to the end of the list and when items are popped, they are removed from the same end. The complete implementation of the Stack ADT using a Python list is provided in \xref{lst:stack:pylist}.
Program Listing
# Implementation of the Stack ADT using a Python list. class Stack : # Creates an empty stack. def __init__(self) : self._theItems = list() # Returns True if the stack is empty or False otherwise. def isEmpty(self): return len(self) == 0 # Returns the number of items in the stack. def __len__ (self) : return len(self._theItems) # Returns the top item on the stack without removing it. def peek(self) : assert not self.isEmpty(), "Cannot peek at an empty stack" return self._theItems[-1] # Removes and returns the top item on the stack. def pop(self) : assert not self.isEmpty(), "Cannot pop from an empty stack" return self._theItems.pop() # Push an item onto the top of the stack. def push(self, item) : self._theItems.append(item)
|
The peek and pop operations can only be used with a non-empty stack since you cannot remove or peek at something that is not there. To enforce this requirement, we first assert the stack is not empty before performing the given operation. The peek method simply returns a reference to the last item in the list. To implement the pop method, we call the pop method of the list structure, which actually performs the same operation that we are trying to implement. That is, it saves a copy of the last item in the list, removes the item from the list, and then returns the saved copy. The push method simply appends new items to the end of the list since that represents the top of our stack.
The individual stack operations are easy to evaluate for the Python list-based implementation (see Table 9.2.1). isEmpty, __length__, and peek only require time. The pop and push methods both require time in the worst case since the underlying array used to implement the Python list may have to be reallocated to accommodate the addition or removal of the top stack item. When used in sequence, both operations have an amortized cost of .
| Operation | Worst Case |
|---|
s = Stack() |
|
len(s) |
|
isEmpty(s) |
|
s.push(x) |
|
x = s.pop() |
|
x = s.peek() |
|
Table 9.2.1: Worst case time-complexities for the Stack ADT implemented using a Python list.
Using a Linked List
The Python list-based implementation may not be the best choice for stacks with a large number of push and pop operations. Remember, each append and pop list operation may require a reallocation of the underlying array used to implement the list. A singly linked list can be used to implement the Stack ADT, alleviating the concern over array reallocations.
To use a linked list, we again must decide how to represent the stack structure. With the Python list implementation of the stack, it was most efficient to use the end of the list as the top of the stack. With a linked list, however, the front of the list provides the most efficient representation for the top of the stack. In Chapter 7, we saw how to easily prepend nodes to the linked list as well as remove the first node. The Stack ADT implemented using a linked list is provided in the listing below.
Program Listing
# Implementation of the Stack ADT using a singly linked list. class Stack : # Creates an empty stack. def __init__(self) : self._top = None self._size = 0 # Returns True if the stack is empty or False otherwise. def isEmpty(self) : return self._top is None # Returns the number of items in the stack. def __len__(self) : return self._size # Returns the top item on the stack without removing it. def peek(self) : assert not self.isEmpty(), "Cannot peek at an empty stack" return self._top.item # Removes and returns the top item on the stack. def pop(self) : assert not self.isEmpty(), "Cannot pop from an empty stack" node = self._top self.top = self._top.next self._size -= 1 return node.item # Pushes an item onto the top of the stack. def push(self, item) : self._top = StackNode(item, self._top) self._size += 1 # The private storage class for creating stack nodes. class StackNode : def __init__(self, item, link) : self.item = item self.next = link
|
The class constructor creates two instance variables for each Stack. The _top field is the head reference for maintaining the linked list while _size is an integer value for keeping track of the number of items on the stack. The latter has to be adjusted when items are pushed onto or popped off the stack. Figure 9.2.1 illustrates a sample Stack object for the stack from Figure 9.1.1.
Figure 9.2.1: Sample object of the Stack ADT implemented as a linked list.
The StackNode class is used to create the linked list nodes. Note the inclusion of the link argument in the constructor, which is used to initialize the _next field of the new node. By including this argument, we can simplify the prepend operation of the push method. The two steps required to prepend a node to a linked list are combined by passing the head reference top as the second argument of the StackNode constructor and assigning a reference to the new node back to _top.
The peek method simply returns a reference to the data item in the first node after verifying the stack is not empty. If the method were used on the stack represented by the linked list in Figure 9.2.1, a reference to 19 would be returned. The peek operation is only meant to examine the item on top of the stack. It should not be used to modify the top item as this would violate the definition of the Stack ADT.
The pop method always removes the first node in the list. This operation is illustrated in Figure 9.2.2 (a). This is easy to implement and does not require a search to find the node containing a specific item. The result of the linked list after popping the top item from the stack is illustrated in Figure 9.2.2 (b).
Figure 9.2.2: Popping an item from the stack: (a) the required link modifications, and
(b) the result after popping the top item.
The linked list implementation of the Stack ADT is more efficient than the Python-list based implementation. All of the operations are in the worst case, the proof of which is left as an exercise.
