Weird performance of list reversal in Python

Question

I run this script and I don't understand how the list reversal works.

class Queue:
    def __init__(self):
        self._push_stack = list()
        self._pop_stack = list()


    def push(self, x):
        self._push_stack.append(x)
        self._pop_stack.append(x)
        self._pop_stack.reverse()
        print(self._push_stack, self._pop_stack) # debugging


    def pop(self):
        if len(self._pop_stack) == 0:
            raise IndexError("pop from an empty queue")
        else:
            self._push_stack.pop()
            return self._pop_stack.pop()


queue = Queue()
queue.push(3)
queue.push(5)
queue.push(7)
queue.push(9)
print(queue.pop())
print(queue.pop())
print(queue.pop())
print(queue.pop())

The output for this script is:

[3] [3]
[3, 5] [5, 3]
[3, 5, 7] [7, 3, 5]
[3, 5, 7, 9] [9, 5, 3, 7]
7
3
5
9

What I don't understand is why [3, 5, 7], when reversed, is [7, 3, 5] and not [7, 5, 3]; why [3, 5, 7, 9], when reversed, is [9, 5, 3, 7], and not [9, 7, 5, 3].

PS please ignore other shortcomings of the script.

You are reversing the order of `pop_stack` after each element you add - that causes some very strange order of elements — UnholySheep, Nov 10 '20 at 16:13
I don't know what explanation you want that your weird code and the debugging output does not already demonstrate. You keep flipping the order of `self._pop_stack`, so it ends up in a weird order. — khelwood, Nov 10 '20 at 16:14
Ignoring the other shortcomings of the script ignores the reason for this behaviour.. — MalteHerrmann, Nov 10 '20 at 16:15
[How to debug small programs.](//ericlippert.com/2014/03/05/how-to-debug-small-programs/) | [What is a debugger and how can it help me diagnose problems?](//stackoverflow.com/q/25385173/843953) After the second iteration, you have `push: [3, 5] pop: [5, 3]`. Then you append 7 to each list, so you have `push: [3, 5, 7] pop: [5, 3, 7]`. Then you reverse `pop`, so you have `push: [3, 5, 7] pop: [7, 3, 5]`. Your debug output already tells you this. — Pranav Hosangadi, Nov 10 '20 at 16:15

score 2 · Accepted Answer · answered Nov 10 '20 at 16:13

You reverse the pop stack each time, which is bad. After the second push, you have [5, 3], then you append 7, leaving [5, 3, 7], then you reverse it, giving you [7, 3, 5].

You don't need to reverse every time, see this answer for an explanation on how to properly implement the logic.

score 0 · Answer 2 · answered Nov 10 '20 at 16:14

0

You are reversing the list at every iteration after the append operation, this is causing the list to be [3,5] before 7 is appended and then reversed

answered Nov 10 '20 at 16:14

Tamir

1,224
1
5
18

score 0 · Answer 3 · answered Nov 10 '20 at 16:18

This is because you are not reversing [3, 5, 7] but [5, 3, 7] if you take a closer look at your code you are reversing the pop_stack every time you push an item. Instead of that you should be prepending:

instead of

self._pop_stack.append(x)
self._pop_stack.reverse()

You can use: self._pop_stack.insert(0, x)

Weird performance of list reversal in Python

3 Answers3