FilesExpand file tree

master

/

linked_queue.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

154 lines (137 loc) · 3.59 KB

master

/

linked_queue.py

Copy path

Top

File metadata and controls

• Code
• Blame

154 lines (137 loc) · 3.59 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

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

""" A Queue using a linked list like structure """

from __future__ import annotations

from typing import Any, Iterator

class Node:

def __init__(self, data: Any) -> None:

self.data: Any = data

self.next: Node | None = None

def __str__(self) -> str:

return f"{self.data}"

class LinkedQueue:

"""

>>> queue = LinkedQueue()

>>> queue.is_empty()

True

>>> queue.put(5)

>>> queue.put(9)

>>> queue.put('python')

>>> queue.is_empty();

False

>>> queue.get()

5

>>> queue.put('algorithms')

>>> queue.get()

9

>>> queue.get()

'python'

>>> queue.get()

'algorithms'

>>> queue.is_empty()

True

>>> queue.get()

Traceback (most recent call last):

...

IndexError: dequeue from empty queue

"""

def __init__(self) -> None:

self.front: Node | None = None

self.rear: Node | None = None

def __iter__(self) -> Iterator[Any]:

node = self.front

while node:

yield node.data

node = node.next

def __len__(self) -> int:

"""

>>> queue = LinkedQueue()

>>> for i in range(1, 6):

... queue.put(i)

>>> len(queue)

5

>>> for i in range(1, 6):

... assert len(queue) == 6 - i

... _ = queue.get()

>>> len(queue)

0

"""

return len(tuple(iter(self)))

def __str__(self) -> str:

"""

>>> queue = LinkedQueue()

>>> for i in range(1, 4):

... queue.put(i)

>>> queue.put("Python")

>>> queue.put(3.14)

>>> queue.put(True)

>>> str(queue)

'1 <- 2 <- 3 <- Python <- 3.14 <- True'

"""

return " <- ".join(str(item) for item in self)

def is_empty(self) -> bool:

"""

>>> queue = LinkedQueue()

>>> queue.is_empty()

True

>>> for i in range(1, 6):

... queue.put(i)

>>> queue.is_empty()

False

"""

return len(self) == 0

def put(self, item: Any) -> None:

"""

>>> queue = LinkedQueue()

>>> queue.get()

Traceback (most recent call last):

...

IndexError: dequeue from empty queue

>>> for i in range(1, 6):

... queue.put(i)

>>> str(queue)

'1 <- 2 <- 3 <- 4 <- 5'

"""

node = Node(item)

if self.is_empty():

self.front = self.rear = node

else:

assert isinstance(self.rear, Node)

self.rear.next = node

self.rear = node

def get(self) -> Any:

"""

>>> queue = LinkedQueue()

>>> queue.get()

Traceback (most recent call last):

...

IndexError: dequeue from empty queue

>>> queue = LinkedQueue()

>>> for i in range(1, 6):

... queue.put(i)

>>> for i in range(1, 6):

... assert queue.get() == i

>>> len(queue)

0

"""

if self.is_empty():

raise IndexError("dequeue from empty queue")

assert isinstance(self.front, Node)

node = self.front

self.front = self.front.next

if self.front is None:

self.rear = None

return node.data

def clear(self) -> None:

"""

>>> queue = LinkedQueue()

>>> for i in range(1, 6):

... queue.put(i)

>>> queue.clear()

>>> len(queue)

0

>>> str(queue)

''

"""

self.front = self.rear = None

if __name__ == "__main__":

from doctest import testmod

testmod()