Sunbelt Computer Software

PL/B Language Development and Support

Python/data_structures/queue/linked_queue.py at master · maxleaf/Python · GitHub

156 lines (138 loc) · 3.62 KB

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

155

156

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

from __future__ import annotations

from collections.abc import Iterator

from typing import Any

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()