51

I want to check a condition against the front of a queue before deciding whether or not to pop. How can I achieve this in python with collections.deque?

list(my_deque)[0]

seems ugly and poor for performance.

jsstuball
  • 4,104
  • 7
  • 33
  • 63
  • 4
    that's not necessary to convert to `list`, since `deque` supports direct indexing. Also, the "front" of the queue is the *last* element (i.e., index `-1`) in the list representation of the `deque`, not the first one. – GPhilo Feb 06 '18 at 10:08

4 Answers4

61

TL;DR: assuming your deque is called d, just inspect d[0], since the "leftmost" element in a deque is the front (you might want to test before the length of the deque to make sure it's not empty). Taking @asongtoruin's suggestion, use if d: to test whether the deque is empty (it's equivalent to if len(d) != 0:, but more pythonic)

Why not converting to list?

Because deque is indexable and you're testing the front. While a deque has an interface similar to a list, the implementation is optimized for front- and back- operations. Quoting the documentation:

Deques support thread-safe, memory efficient appends and pops from either side of the deque with approximately the same O(1) performance in either direction.

Though list objects support similar operations, they are optimized for fast fixed-length operations and incur O(n) memory movement costs for pop(0) and insert(0, v) operations which change both the size and position of the underlying data representation.

Converting to list might be desirable if you have lots of operations accessing the "middle" of the queue. Again quoting the documentation:

Indexed access is O(1) at both ends but slows to O(n) in the middle. For fast random access, use lists instead.

Conversion to list is O(n), but every subsequent access is O(1).

Community
  • 1
  • 1
GPhilo
  • 18,519
  • 9
  • 63
  • 89
  • 4
    You should be able to just directly check if the deque is empty without needing to check its length (i.e. `if d:` rather then `if len(d) > 0:`) – asongtoruin Feb 06 '18 at 10:08
  • @asongtoruin I read that as an implicit length-test, since the two statements are equivalent, but of course `if d:` is the more pythonic way to write it. – GPhilo Feb 06 '18 at 10:10
  • 2
    I looked for a duplicate, but couldn't find one. You have my UV! you could add that converting to `list` is not only ugly but underperformant – Jean-François Fabre Feb 06 '18 at 10:13
  • 1
    I realise I was being pedantic - your answer is correct but I can see how someone might think `len` was required – asongtoruin Feb 06 '18 at 10:14
  • @asongtoruin your comment was very welcome ;) I chose to keep the wording of the answer generic because I don't know whether the OP has implicit assumptions on the deque, but of course your comment is on-point and I will add it as a note to the answer – GPhilo Feb 06 '18 at 10:16
  • like `if d and d[-1]==somethng:` – Jean-François Fabre Feb 06 '18 at 10:22
  • @Jean-FrançoisFabre depending on the OP's usage of the deque, `and`-ing those clauses together might cause some trouble with the `else` clause because you don't distinguish which of the two conditions sent you to the else branch. I think nesting to `if`s here is the best choice – GPhilo Feb 06 '18 at 10:31
  • 2
    Hold on, depending on how you are using the deque, the "front" of the deque might be at the beginning! (i.e. `d[0]`) – information_interchange Oct 31 '19 at 23:07
  • Both ends are optimised – GPhilo Oct 31 '19 at 23:44
  • @information_interchange exactly right, the -1th element is the most recently added therefore the last in the queue (assuming a FIFO queue and append()). The answer should use the 0th element like OP in the question – ljden Mar 11 '22 at 02:14
  • @ljden considering how old this answer is, I can't believe nobody else pointed it out (I didn't understand information_exchange's comment at the time, apparently). Of course your right, if we assume the deque is filled with append() (and I'd argue that's the most common case), the front is at index 0. I'll amend the answer when I have a chance (on mobile ATM), but if you want to suggest an edit I'd gladly accept it. Thank you! – GPhilo Mar 11 '22 at 09:04
  • @GPhilo submitted an edit – ljden Mar 12 '22 at 10:15
13

You can simply find the last element using my_deque[-1] or my_deque[len(my_deque)-1] .

tsukyonomi06
  • 514
  • 1
  • 6
  • 19
5

Here is a simple implementation that allowed me to check the front of the queue before popping (using while and q[0]):

Apply your own condition against q[0], before q.popleft(), below:

testLst = [100,200,-100,400,340]
q=deque(testLst)

while q:
    print(q)
    print('{}{}'.format("length of queue: ", len(q)))
    print('{}{}'.format("head: ", q[0]))
    print()

    q.popleft()

output:

deque([100, 200, -100, 400, 340])
length of queue: 5
head: 100

deque([200, -100, 400, 340])
length of queue: 4
head: 200

deque([-100, 400, 340])
length of queue: 3
head: -100

deque([400, 340])
length of queue: 2
head: 400

deque([340])
length of queue: 1
head: 340
Grant Shannon
  • 4,709
  • 1
  • 46
  • 36
2

Assuming your deque is implemented from collections python

from collections import deque
deque = deque() //syntax

Deque too can be interpreted as a list in terms of accessing using indices. You can peek front element by using deque[0] and peek last using deque[-1] This works without popping elements from left or right and seems efficient too.

Josef
  • 2,869
  • 2
  • 22
  • 23
vijay9908
  • 59
  • 2