FilesExpand file tree

master

/

circular_queue.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

94 lines (84 loc) · 2.52 KB

master

/

circular_queue.py

Copy path

Top

File metadata and controls

• Code
• Blame

94 lines (84 loc) · 2.52 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

# Implementation of Circular Queue (using Python lists)

class CircularQueue:

"""Circular FIFO queue with a fixed capacity"""

def __init__(self, n: int):

self.n = n

self.array = [None] * self.n

self.front = 0 # index of the first element

self.rear = 0

self.size = 0

def __len__(self) -> int:

"""

>>> cq = CircularQueue(5)

>>> len(cq)

0

>>> cq.enqueue("A") # doctest: +ELLIPSIS

<data_structures.queue.circular_queue.CircularQueue object at ...

>>> len(cq)

1

"""

return self.size

def is_empty(self) -> bool:

"""

>>> cq = CircularQueue(5)

>>> cq.is_empty()

True

>>> cq.enqueue("A").is_empty()

False

"""

return self.size == 0

def first(self):

"""

>>> cq = CircularQueue(5)

>>> cq.first()

False

>>> cq.enqueue("A").first()

'A'

"""

return False if self.is_empty() else self.array[self.front]

def enqueue(self, data):

"""

This function insert an element in the queue using self.rear value as an index

>>> cq = CircularQueue(5)

>>> cq.enqueue("A") # doctest: +ELLIPSIS

<data_structures.queue.circular_queue.CircularQueue object at ...

>>> (cq.size, cq.first())

(1, 'A')

>>> cq.enqueue("B") # doctest: +ELLIPSIS

<data_structures.queue.circular_queue.CircularQueue object at ...

>>> (cq.size, cq.first())

(2, 'A')

"""

if self.size >= self.n:

raise Exception("QUEUE IS FULL")

self.array[self.rear] = data

self.rear = (self.rear + 1) % self.n

self.size += 1

return self

def dequeue(self):

"""

This function removes an element from the queue using on self.front value as an

index

>>> cq = CircularQueue(5)

>>> cq.dequeue()

Traceback (most recent call last):

...

Exception: UNDERFLOW

>>> cq.enqueue("A").enqueue("B").dequeue()

'A'

>>> (cq.size, cq.first())

(1, 'B')

>>> cq.dequeue()

'B'

>>> cq.dequeue()

Traceback (most recent call last):

...

Exception: UNDERFLOW

"""

if self.size == 0:

raise Exception("UNDERFLOW")

temp = self.array[self.front]

self.array[self.front] = None

self.front = (self.front + 1) % self.n

self.size -= 1

return temp