Learn about stack, queue, dequeue, its implementation and running time.

# Stack

• Stack: a collection of objects that are inserted and removed according to the last-in, first-out (LIFO) principle.

## Operations

• S.push(e): Add element e to the top of stack S.
• S.pop(): Remove and return the top element from the stack S
• S.top(): Return a reference to the top element of stack S, without removing it.
• S.is_empty(): Return True if stack S does not contain any elements.
• len(S): Return the number of elements in stack S.

## Time Complexity

• Time complexity of array-based stack implementation
• The bounds for push and pop are amortized due to similar bounds for the list class.
• The space using is $O(n)$, where $n$ is the current number of elements in the stack.

# Queue

• Queue: a collection of objects that are inserted and removed according to the first-in, first-out (FIFO) principle.

## Operations

• Q.enqueue(e): Add element e to the back of queue Q.
• Q.dequeue(): Remove and return the first element from the queue Q.
• Q.first(): Return a reference to the first element of queue Q, without removing it.
• Q.is_empty(): Return True if queue Q does not contain any elements.
• len(Q): Return the number of elements in queue Q.

## Queue in Python

• Using list as queue in python is possible but not efficient because all of the other elements have to be shifted by one after inserts or pops
• To implement queue, use ‘collections.deque’ which was designed to have fast appends and pops.
from collectinos import deque
queue = dequeue(["Eric", "John", "Michael"])
queue.append("Terry") # Q.enequeue(e)
queue.popleft() # Q.dequeue()
queue[0] # Q.first()
len(queue)==0 # Q.is_empty()
len(queue) # len(Q)


## Time Complexity

• Time complexity of array-based queue implementation
• The bounds for enqueue and dequeue are amortized due to the resizing of the array.
• The space using is $O(n)$, where $n$ is the current number of elements in the queue.

# Double-Ended Queue

• Double-Ended Queue (deque): a queue-like data structure that supports insertion and deletion at both the front and the back of the queue.

## Operations

• D.delete_first(): Remove and return the first element from the deque D.
• D.delete_last(): Remove and return the last element from the deque D.
• D.first(): Return a reference to the first element of deque D, without removing it.
• D.last(): Return a reference to the last element of deque D, without removing it.
• D.is_empty(): Return True if deque D does not contain any elements.
• len(D): Return the number of elements in deque D.

## Time Complexity

• ‘n’ is the number of elements currently in the container. ‘k’ is either the value of a parameter or the number of elements in the parameter.

# Quiz

Stack related quiz Game of Two Stacks in HackerRank

## Answer code in Python 3

#!/bin/python3

import sys

g = int(input().strip())
for a0 in range(g):
n,m,x = input().strip().split(' ')
n,m,x = [int(n),int(m),int(x)]
a = list(map(int, input().strip().split(' ')))
b = list(map(int, input().strip().split(' ')))

sum = 0
count = 0
max_count =0
tempA = []

# Inverse 'a' and 'b' list to use as stack
a.reverse()
b.reverse()

# Pop from stack A and sum until it exceeds the limit
while len(a)!=0:
if sum + a[-1] <= x:
sum += a[-1]
count += 1
tempA.append(a.pop()) # Save pop-ed element from stack A
else:
break
max_count = count # Save current max_count

# Pop from stack B and plus it with 'sum'
while len(b)!=0:
sum += b.pop()
count += 1

# If 'sum' exceeds the limit, discard one from tempA
while sum > x and len(tempA)!=0:
sum -= tempA.pop()
count -= 1

if sum <= x and max_count < count:
max_count = count
elif sum > x:
break

print (max_count)


# References

• Book: Cracking the coding interview [Link]
• Book: Data structures and algorithms in python [Link]

Tags:

Categories:

Updated: