Fixed-length stack image

In this article we will look at how we can implement a fixed-length stack in Python.

A stack is a data structure that observes the Last In First Out(LIFO) principle. This is where  the last item to be inserted is the first one to be removed.

In some cases, it may be necessary to have a stack that is of fixed-length. Fixed-length stacks have a predetermined maximum number of elements that they can hold.

There are two types of fixed-length stacks.The first type raises an error on an attempt to add an element when the maximum capacity is reached, the other type discards the oldest item to accommodate the incoming one.

A list-based Fixed-length stack

In this section we will implement a FixedStack class using a list for internal storage of the stack elements. 

The class have the following methods: 

push(e) Adds element e at the top of the stack. Raises an error if the stack is full.
pop() Removes and returns the top element. Raises an exception if the stack is empty.
top() Returns the top element without removing it. Raises an exception if the stack is empty.
is_empty() Checks whether the stack is empty. Returns True if so, False otherwise.
is_full() Checks whether the stack is full. Returns True if so, False otherwise.
ExampleEdit & Run

Fixed Stack implementation

#an exception to be raised when the stack is full
class StackFull(Exception):
   pass 

#an exception to be raised by an empty stack
class StackEmpty(Exception):
   pass

#The FixedStack class
class FixedStack: 
   def __init__(self, capacity):
      self.capacity = capacity 
      self._data = [] #a non-public list to store stack elements

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

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

   def is_full(self):
      return len(self) == self.capacity

   def push(self, item): 
      if self.is_full(): 
         raise StackFull( "Stack is full, cannot add item.") 

      self._data.append(item)

   def pop(self): 
      if self.is_empty():
         raise StackEmpty(("Stack is empty, cannot pop item."))
      return self._data.pop()

   def top(self):
      if self.is_empty():
         raise StackEmpty(("Stack is empty, cannot pop item."))
      return self._data[-1]

#test the stack
S = FixedStack(3) # a fixed stack of length 3

S.push(10)
S.push(20)
S.push(30)
print(S.pop())
print(S.pop())
print(S.pop())
S.push(50)
S.push(60)
S.push(70)
print("size: ", len(S))
S.push(80)

 Visualize
Output:
302010size:  3Traceback (most recent call last):  File "<string>", line 53, in <module>  File "<string>", line 26, in pushStackFull: Stack is full, cannot add item.[Finished in 0.011189359938725829s]

Fixed-length stack using collections.deque 

The deque class in the collections module has efficient methods for adding and removing elements from both ends. We can use a deque object as a stack by appending and popping from just one end, either the rear or the front of the deque.

The fixed-length property can be achieved by setting the maxlen parameter when instantiating  the deque.

We can use append() and pop() methods to perform push and pop operations from the rear end of the deque object.

Note: A deque does not raise an error if full. It instead removes the oldest item to create room for the incoming item. This ensures that the  maximum capacity is never exceeded and that there is always space for new items to be added.

ExampleEdit & Run
from collections import deque

#create a fixed-stack of length 5
S = deque(maxlen = 3)

#add elements
S.append("Python")
S.append("Java")

#remove elements
print(S.pop())
print(S.pop())

#add elements until maxlen is reached.
S.append("Python")
S.append("Java")
S.append("C++")
S.append("Kotlin")

print(S)
 Visualize
Output:
JavaPythondeque(['Java', 'C++', 'Kotlin'], maxlen=3)[Finished in 0.013128309044986963s]

As shown above, when the maxlen parameter is set and  the deque is full, appending an element makes the oldest element to be discarded to create room for the incoming element.