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.

## Use list as stack in Python

## 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.

- The bounds for

# 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.

- The bounds for

# 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.add_first(e): Add element e to the front of deque D.
- D.add_last(e): Add element e to the back of deque D.
- 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.

## Deques in the Python Collections Module

## 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(' ')))
# your code goes here
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)
```