3 ms·
How to implement a Queue using Stacks in Python
- eesmith 7y agoThis 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