Implementing Stacks, Queues, and Deques

Gregory M. Kapfhammer

February 26, 2024

What is an abstract data type? How to compare it to a data structure?

• Abstract Data Type (ADT): the interface of a data structure
• Concrete Data Structure (CDS): the implementation of ADT
• ADT is independent of implementation concerns in the CDS

Understanding the connection between and ADT and a CDS

• Abstract data type

  • What is the data to be stored or represented?
  • What are the processes that manipulate the data?
  • Avoids specifying how the data is stored or manipulated

• Concrete data structure

  • Delivered as a class in a Python program
  • Implements an efficient version of data type
  • Specifies how the data is stored and manipulated

An ADT and its CDS are the basic building blocks of programs!

• Stack: ADT for a last-in, first-out (LIFO) list
• Queue: ADT for a first-in, first-out (FIFO) list
• Deque: ADT for a flexible, double-ended queue
• Each data structure has trade-offs in its:
  • Implementation ease
  • Feature and use
  • Time overhead
  • Space overhead

Specifying and implementing the Stack abstract data type

• Data storage and access according to the LIFO discipline
• Implemented in a object-oriented fashion using composition
• Balances the need for flexibility and efficiency
• Be careful! Poor implementations can be inefficient!

Stack abstract data type

• push - add a new item to the stack
• pop - remove and return the next item in LIFO order
• peek - return the next item in LIFO order
• size - returns the number of items in the stack
• isempty - return True if storing no items or return False

• Implementation details:
  • The Stack wraps a list in a Python class
  • Use the name of the Stack to give implementation clues
  • Let’s explore the first implementation called ListStack!

ListStack implements the Stack ADT

class ListStack:
    def __init__(self):
        self._L = []

    def push(self, item):
        self._L.append(item)

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

    def peek(self):
        return self._L[-1]

    def __len__(self):
        return len(self._L)

    def isempty(self):
        return len(self) == 0

• The ListStack uses a list called _L to store data items

Using the ListStack

def manipulate_stack():
    stack = ListStack()
    stack.push('umbrella')
    stack.push('backpack')
    stack.push('sandals')
    print("Stack contents after push operations: ", [item for item in stack._L])
    stack.pop()
    print("Stack contents after pop operation: ", [item for item in stack._L])

manipulate_stack()

Stack contents after push operations:  ['umbrella', 'backpack', 'sandals']
Stack contents after pop operation:  ['umbrella', 'backpack']

• The manipulate_stack function creates a ListStack
• Function illustrates the LIFO behavior of the ListStack
• It breaks encapsulation of ListStack by accessing _L

Inefficient implementation of Stack

class InefficientListStack(ListStack):    
    def push(self, item):
        self._L.insert(0, item)

    def pop(self):
        return self._L.pop(0)

    def peek(self):
        return self._L[0]

• Inserting a new item moves all other items
• The insert call in push takes \(O(n)\) time
• Removing an item moves all other items
• The pop call in push takes \(O(n)\) time
• Wow, this stack has two linear operations!

Using the InefficientListStack

def manipulate_stack():
    stack = InefficientListStack()
    stack.push('umbrella')
    stack.push('backpack')
    stack.push('sandals')
    print("Stack contents after push operations: ", [item for item in stack._L])
    stack.pop()
    print("Stack contents after pop operation: ", [item for item in stack._L])

manipulate_stack()

Stack contents after push operations:  ['sandals', 'backpack', 'umbrella']
Stack contents after pop operation:  ['backpack', 'umbrella']

• Function creates an InefficientListStack instance
• Same behavior as the ListStack but with inefficiency
• When would the inefficiency become a problem?

Specifying and implementing the Queue abstract data type

• Data storage and access according to the FIFO discipline
• Implemented in a object-oriented fashion using composition
• Adds new behaviors not found in the Stack ADT
• Illustrates the trade-off between time and space overhead

Queue abstract data type

• enqueue(item) - add a new item to the queue
• dequeue() - remove and return the next item in FIFO order
• peek() - return (without removing) the next item in FIFO order
• len - return the number of items in the queue
• isempty() - return True if storing no items or return False

• Implementation details:
  • The Queue abstract data type wraps a list in a Python class
  • Use the name of the Queue to give implementation clues
  • Let’s explore the first implementation called ListQueueSimple!

ListQueueSimple implements Queue

class ListQueueSimple:
    def __init__(self):
        self._L = []

    def enqueue(self, item):
        self._L.append(item)

    def dequeue(self):
        return self._L.pop(0)

    def peek(self):
        return self._L[0]

    def __len__(self):
        return len(self._L)

    def isempty(self):
        return len(self) == 0

• The ListQueueSimple uses a list called _L to store data items

Using the ListQueueSimple

def manipulate_queue():
    queue = ListQueueSimple()
    queue.enqueue('umbrella')
    queue.enqueue('backpack')
    queue.enqueue('sandals')
    print("Queue contents after enqueue operations: ", [item for item in queue._L])
    queue.dequeue()
    print("Queue contents after dequeue operation: ", [item for item in queue._L])

manipulate_queue()

Queue contents after enqueue operations:  ['umbrella', 'backpack', 'sandals']
Queue contents after dequeue operation:  ['backpack', 'sandals']

• Function creates a ListQueueSimple instance
• Can you see how this is different than the ListStack?
• Differences between the FIFO and LIFO disciplines?

Wait! This Queue implementation is inefficient because it calls pop(0)!

• Calling pop(0) takes \(O(n)\) time due to the item shifting

• Either approach is inefficient for a Queue implementation

• Making the Queue implementation more efficient:

  • Do not delete the items when removed from Queue
  • Ignore each item when it is removed from Queue
  • Keep an index to the head of the Queue
  • Will this increase the space overhead or delete data ?!?!

ListQueueFakeDelete uses an index

class ListQueueFakeDelete: 
    def __init__(self):
        self._head = 0
        self._L = []

    def enqueue(self, item):
        self._L.append(item)

    def peek(self):
      return self._L[self._head]

    def dequeue(self):
        item = self.peek()
        self._head += 1
        return item

    def __len__(self):
        return len(self._L) - self._head

    def isempty(self):
        return len(self) == 0

Using the ListQueueFakeDelete

def manipulate_queue():
    queue = ListQueueFakeDelete()
    queue.enqueue('umbrella')
    queue.enqueue('backpack')
    queue.enqueue('sandals')
    print("Queue contents after enqueue operations: ", [item for item in queue._L])
    queue.dequeue()
    print("Queue contents after dequeue operation: ", [item for item in queue._L])

manipulate_queue()

Queue contents after enqueue operations:  ['umbrella', 'backpack', 'sandals']
Queue contents after dequeue operation:  ['umbrella', 'backpack', 'sandals']

• Function creates a ListQueueFakeDelete instance
• Output is not same as using the ListQueueSimple
• Wait, is output actually different from ListQueueSimple’s?

Revised ListQueueFakeDelete

class ListQueue(ListQueueFakeDelete):
    def dequeue(self):
        item = self._L[self._head]
        self._head += 1
        if self._head > len(self._L)//2:
            self._L = self._L[self._head:]
            self._head = 0
        return item

• Define a subclass of the ListQueueFakeDelete
• Provide a new implementation of the dequeue method
• Periodically “compact” the list to reduce space overhead
• Uses the same strategy as the list.pop() in Python
• What is the trade-off between time and space overhead?

Time complexity of dequeue

• Worst-case time complexity of the dequeue function is \(O(n)\)
• Inefficient line: self._L = self._L[self._head:]
• “List slicing” in a list index has a linear time complexity
• Understanding the performance of the dequeue function:
  • All of the other operations are \(O(1)\)
  • The worst-case scenario that involves list slicing only occurs when self._head > len(self._L)//2
  • On average, the cost per item is constant because the list modification is infrequent and demand-driven!

Error handling in the Stack and Queue implementations

• A Python method can raise an Exception to signal an error
• An Exception can be “caught” or it can lead to a crash
• Handle cases when use of the data structure is incorrect
• Goal: make the data structure implementations more robust

Stack with exception handling

class RobustStack(ListStack):
    def pop(self):
        try:
            return self._L.pop()
        except IndexError:
            raise RuntimeError("pop from empty stack")

s = RobustStack()
s.push(5)
s.pop()
# un-comment the next line to see a crash!
# s.pop()

5

• Avoids a crash when pop is called on an empty stack
• This pop method can raise an IndexError on empty stack
• Use a try and except block to catch the IndexError

Specifying and implementing the Deque abstract data type

• A double-ended queue is more flexible than the Queue
• Add or remove items from the front and back of the Queue
• Wow, it combines the Stack and Queue ADTs!

Deque abstract data type

• addfirst(item) - add item to the front of the deque
• addlast(item) - add item to the end of the deque
• removefirst(item) - remove and return the first item in the deque
• removelast(item) - remove and return the last item in the deque
• len - return the number of items in the deque

• Implementation details:
  • The Deque wraps a list in a Python class
  • Use the name of the Deque to give implementation clues
  • Let’s explore the first implementation called ListDeque!

Implementation of ListDeque

class ListDeque:
    def __init__(self):
        self._L = []

    def addfirst(self, item):
        self._L.insert(0, item)

    def addlast(self, item):
        self._L.append(item)

    def removefirst(self):
        return self._L.pop(0)

    def removelast(self):
        return self._L.pop()

    def __len__(self):
        return len(self._L)

• Modification methods have a postfix label of first or last

Limitations of ListDeque

• What is the performance of this implementation?
  • Inserting and popping at index \(0\) takes \(O(n)\) time
  • Due to the sequential storage of lists in memory
  • Changes at the list’s beginning require shifting all items
  • Shifting occurs when making room or filling gaps
• Need a new approach to avoid this fundamental overhead!

Key question: Can we preserve the features of the Deque while avoiding the linear time complexity of addfirst and removefirst?