FilesExpand file tree

 master

/

deque.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

48 lines (39 loc) · 1.87 KB

 master

/

deque.py

Copy path

Top

File metadata and controls

• Code
• Blame

48 lines (39 loc) · 1.87 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

"""

A deque is similar to all of the other sequential data structures but

has some implementation details that are different from other sequences

like a list. This module highlights those differences and shows how

a deque can be used as a LIFO stack and a FIFO queue.

"""

from collections import deque

def main():

# A list is identical to a vector where a new array is created when

# there are too many elements in the old array, and the old array

# elements are moved over to the new array one-by-one. The time

# involved with growing its size increases linearly. A deque is

# identical to a doubly linked list whose nodes have a left pointer

# and a right pointer. In order to grow the linked list, a new node

# is created and added to the left, or the right, of the linked list.

# The time complexity involved with growing its size is constant.

# Check out the source code for a list and a deque here:

# https://github.com/python/cpython/blob/3.8/Objects/listobject.c

# https://github.com/python/cpython/blob/3.8/Modules/_collectionsmodule.c

dq = deque()

for i in range(1, 5):

# Similar to adding a new node to the right of the linked list

dq.append(i)

# Similar to adding a new node to the left of the linked list

dq.appendleft(i * 2)

# A deque can be iterated over to build any data structure

assert [el for el in dq] == [8, 6, 4, 2, 1, 2, 3, 4]

assert tuple(el for el in dq) == (8, 6, 4, 2, 1, 2, 3, 4)

assert {el for el in dq} == {8, 6, 4, 2, 1, 3}

# A deque can be used as a stack

# https://en.wikipedia.org/wiki/Stack_(abstract_data_type)

assert dq.pop() == 4

assert dq.pop() == 3

# A deque can be used as a queue

# https://en.wikipedia.org/wiki/Queue_(abstract_data_type)

assert dq.popleft() == 8

assert dq.popleft() == 6

if __name__ == '__main__':

main()