Stack of Plates

Implement a data structure, SetOfStacks, that is composed of several stacks and creates a new stack once the previous one exceeds capacity. push and pop should behave identically to a single stack.

Solution

This solution is not necessarily complicated - we simply need to create another data structure with an array of stacks, an integer to keep track of the current stack’s size, and the capacity of the stacks. When we push an element which exceeds the current stack’s capacity, we create a new stack. We can use the stack size attribute to perform other logical operations for push and pop.

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

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

  def push(self, value):
    if(self.top == None):
      node = Node(value)
      self.top = node

    else:
      node = Node(value)
      node.next = self.top
      self.top = node

  def pop(self):
    value = self.top.value
    self.top = self.top.next
    return value

class SetOfStacks:
  def __init__(self, capacity=10):
    self.stacks = []
    self.stack_size = 0
    self.capacity = capacity

  def push(self, value):
    if(not self.stacks):
      stack = Stack()
      stack.push(value)
      self.stacks.append(stack)
      self.stack_size += 1

    elif(self.stack_size < self.capacity):
      self.stacks[-1].push(value)
      self.stack_size += 1

    elif(self.stack_size == self.capacity):
      stack = Stack()
      stack.push(value)
      self.stacks.append(stack)
      self.stack_size = 1

  def pop(self):
    value = self.stacks[-1].pop()
    self.stack_size -= 1

    if(self.stack_size == 0):
      self.stacks.pop()
      self.stack_size = 10

    return value