Stacks and Queues

Stacks

Implementation

Implemented using lists or linked lists in python

for this scenario - implemented using lists

must contain following functions:

• push() - inserts value into stack
• pop() - removes and return value from stack
• peek() - returns value at top of the stack - last inserted value
• is_empty() - returns boolean depending on whether there are any elements in the stack
• size() - returns the total number of elements currently in the stack

NOTE: Stack stores values in LIFO order -> meaning elements pop out of stack in the exact same order they were pushed in.

Big O Complexity

• push() - O(1)
• pop() - O(1)
• peek() - O(1)
• is_empty() - O(1)
• size() - O(1)

Queues

Implementation

Queues can represented by lists, linked lists or stacks

commonly implemented using lists, implemented here using DLL.

dequeuing from front is O(n) with arrays or lists, O(1) with linked lists.

must contain following functions:

• enqueue() - add an element to queue to the rear
• dequeue() - remove and return and element from the front
• is_empty() - returns True if there are no elements in queue
• front() - returns the value at the front of the queue
• rear() - returns the value at the back of the queue
• size() - returns the number elements in the queue

NOTE: Queues store values in FIFO format -> meaning elements can only be dequeued in the order that they were enqueued.

Big O Complexity

• enqueue() - O(1)
• dequeue() - O(1)
• is_empty() - O(1)
• front() - O(1)
• rear() - O(1)
• size() - O(1)