Codility - Lesson 7 Stacks and Queues

Source Link:
https://codility.com/programmers/lessons/7-stacks_and_queues/

Some Notes: 
The structures will provide two operations: 
push (inserting the new element to the structure) and 
pop (removing some element from the structure).


7.1. Stack

The stack is a basic data structure in which the insertion of new elements takes place at
the top and deletion of elements also takes place from the top.

7.1: Push / pop function — O(1).
1 stack = [0] * N
2 size = 0
3 def push(x):
4 global size
5 stack[size] = x
6 size += 1
7 def pop():
8 global size
9 size -= 1
10 return stack[size]


7.2. Queue

The queue is a basic data structure in which new elements are inserted at the back but old
elements are removed from the front.

7.2: Push / pop / size / empty function — O(1).
1 queue = [0] * N
2 head, tail = 0, 0
3 def push(x):
4 global tail
5 tail = (tail + 1) % N
6 queue[tail] = x
7 def pop():
8 global head
9 head = (head + 1) % N
10 return queue[head]
11 def size():
12 return (tail - head + N) % N
13 def empty():
14 return head == tail


7.3. Exercises

Problem: You are given a zero-indexed array A consisting of n integers: a0, a1, . . . , an−1. Array A represents a scenario in a grocery store, and contains only 0s and/or 1s:

• 0 represents the action of a new person joining the line in the grocery store,
• 1 represents the action of the person at the front of the queue being served and leaving
the line.

The goal is to count the minimum number of people who should have been in the line before the above scenario, so that the scenario is possible (it is not possible to serve a person if the line is empty).

Solution O(n): We should remember the size of the queue and carry out a simulation of
people arriving at and leaving the grocery store.

7.3: Model solution — O(n).
1 def grocery_store(A):
2 n = len(A)
3 size, result = 0, 0
4 for i in xrange(n):
5 if A[i] == 0:
6 size += 1
7 else:
8 size -= 1
9 result = max(result, -size)
10 return result