3 ms·
This implements a queue API, but does not implement the queue Big-O performance required for a queue. The queue pop() is implemented as: stack.pop(0) which
by eesmith 7y ago
This implements a queue API, but does not implement the queue Big-O performance required for a queue. The queue pop() is implemented as:
stack.pop(0)
which takes O(N) time. As evidence:
>>> import time
>>> for i in range(10, 20):
... values = [0]*(2**i)
... t1 = time.time()
... for _ in range(2**i):
... x = values.pop(0)
... t2 = time.time()
... print(2**i, t2-t1)
...
1024 0.0003371238708496094
2048 0.0009081363677978516
4096 0.0019719600677490234
8192 0.006997108459472656
16384 0.021010160446166992
32768 0.09459710121154785
65536 0.39771080017089844
131072 1.7854771614074707
262144 7.326504945755005
524288 33.3485050201416
This is clearly quadratic.
The article says "A common programming interview question, and for a change, one that you will actually be able to use in the job, is that of implementing a Queue by means of using Stacks in Python."
This sort of solution indicates that the interviewee is a novice programmer. The implementation can only reasonably be used for small queues, where the quadratic behavior is not important.
It is much better to use collections.deque in every real-world use.
>>> import time, collections
>>> for i in range(10, 20):
... values = collections.deque([0]*(2**i))
... t1 = time.time()
... for _ in range(2**i):
... x = values.popleft()
... t2 = time.time()
... print(2**i, t2-t1)
...
1024 0.00043392181396484375
2048 0.0006589889526367188
4096 0.001123666763305664
8192 0.0021991729736328125
16384 0.003899812698364258
32768 0.004210948944091797
65536 0.007882833480834961
131072 0.01650714874267578
262144 0.03747200965881348
524288 0.06636691093444824