Stack

Implementation by list

Stack: linear data structure with Last in first out (LIFO).

st = [1, 2 , 3, 4, 5]

# push: T(n) = O(1), S(n) = S(1)
st.append(60) # output: st = [1, 2 , 3, 4, 5, 60]
st.append(70)

# pop/top/peek: T(n) = O(1), S(n) = S(1)
peekElement = st.pop() # output: peakElement = 70, st = [1, 2 , 3, 4, 5, 60] 
st.pop() # st = [1, 2 , 3, 4, 5] 

# size: T(n) = O(1), S(n) = S(1)
size = len(st)

Implementation by deque

Deque: Doubly Ended Queue. Enable operations from both the ends of the container, which means deque can implement both stack and queue. In python, deque is from module “collections”.

When T(n) = O(1), S(n) = S(1). *6

import collections
de = collections.deque([1, 2, 3, 4, 5])


# 1. right push: T(n) = O(1), S(n) = S(1)
de.append(60) # output: de = deque([1,2,3,4,5,60])

# 2. left push: T(n) = O(1), S(n) = S(1)
de.appendleft(-0.2) # output: de = deque([-0.2,1,2,3,4,5,60])

# 3. right pop: T(n) = O(1), S(n) = S(1)
r = de.pop() # r: 60, de = deque([-0.2,1,2,3,4,5])
de.pop() # de = deque([-0.2,1,2,3,4])

# 4. left pop: T(n) = O(1), S(n) = S(1)
l = de.popleft() # l: -0.2, de = deque([1,2,3,4])

# 5. size: T(n) = O(1), S(n) = S(1) 
len = len(de)

# 6. get front and back item of deque: T(n) = O(1), S(n) = S(1) 
front = de[0] # front = 1
back = de[-1] # back = 4

When T(n) = O(N), S(n) = S(1). *5

import collections

de = collections.deque([10, 20, 30, 20, 40, 50])

# 1. index: get the first occurrence of element. T(n) = O(N), S(n) = S(1)
idx = de.index(20) # idx = 1

# 2. insert: insert(pos, val). T(n) = O(N), S(n) = S(1)
de. insert(3,50) # de = deque([10, 20, 30, 50, 20, 40, 50]) . insert the value 50 at 4th position (there're 3 elements before inserted value).

# 3. remove： remove the first occurrence of element. T(n) = O(N), S(n) = S(1)
de.remove(50) # de = deque([10, 20, 30, 20, 40, 50])

# 4. count: count the occurrences of element. T(n) = O(N), S(n) = S(1)
c = de.count(20) # c = 2

# 5. reverse: reverse deque (in-place). T(n) = O(N), S(n) = S(1)
de.reverse() # de = deque([50, 40, 20, 30, 20, 10])

When T(n) = O(K), S(n) = S(1). *3

import collections

de = collections.deque([10, 20, 30, 20, 40, 50])

# 1. extend: push multiple elements in the back/right. 
de.extend([6, 7, 8]) # de = deque([10, 20, 30, 20, 40, 50, 6, 7, 8]). T(n) = T(3), S(n) = S(1)

# 2. extendleft: push multiple elements in the front/left. T(n) = T(2), S(n) = S(1)
de.extendleft([-400, -300]) # de = deque([-300, -400, 10, 20, 30, 20, 40, 50, 6, 7, 8]). 
# Pay attention to the order of -300 and -400.

# 3. rotate: rotate the deque by k (if k>0 rotate to right, elif k<0 rotate to left)
de.rotate(5) # de = deque([40, 50, 6, 7, 8,-300, -400, 10, 20, 30, 20]). # slide 5 elements to the right. # T(n) = T(5), S(n) = S(1)
de.rotate(-2) # de = deque([6, 7, 8, -300, -400, 10, 20, 30, 20, 40, 50]). # slide 2 elements to the left. # T(n) = T(2), S(n) = S(1)