An Introduction to Data Structures in Python: Stacks and Queues

Stacks are data structures based on lists and that follow the LIFO (Last In , First Out) storage method. In a stack, all operations affect the top item. In order to access the items lower in the stack, all the items above the desired item must be removed first.

class Stack():
def __init__(self):
self.stack = list()
def push(self, item):
self.stack.append(item)
def pop(self):
if len(self.stack) > 0:
return self.stack.pop()
else:
return None
def peek(self):
if len(self.stack) > 0:
return self.stack[len(self.stack) - 1]
else:
return None
def __str___(self):
return str(self.stack)

Queues

Queue’s are similar to stacks in that they can use lists and have similar functionality. The one difference is that queues are FIFO — First In, First Out. To add an item to the back of the queue, we ‘Enqueue’ that item. To remove one from the front, we ‘Dequeue’ it. Queues are used to model anything one would wait in line for, such as getting into a website with heavy traffic.

from collections import deque
class Queue():
def __init__(self):
self.queue = deque()
self.size = 0
def enqueue(self, item):
self.queue.append(item)
self.size += 1
return self.queue
def dequeue(self):
if self.size > 0:
self.size -= 1
return self.queue.popleft()
else:
return None
def get_size(self):
return len(self.queue)

Incoming Freshman @ NYU Stern