forked from phuang07/python_algorithms
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathqueue.py
More file actions
134 lines (109 loc) · 3.98 KB
/
Copy pathqueue.py
File metadata and controls
134 lines (109 loc) · 3.98 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
#!/usr/bin/env python
# -*- coding: utf-8 -*-
"""This module implements a linked list based queue data structure.
A queue is a data structure to hold a collection of items in order ad which
supports operations such as the addition of an item (*enqueue*) and removal of
an item (*dequeue*) can be performed. The items are always enqueued at the rear
end of the queue and dequeued from the front end of the queue. As such, the
queue can be also viewed as a First-In-First-Out(*FIFO*) data structure. In a
FIFO data structure, the first item added to the structure is the first one to
be removed. Apart from those two operations, *peek* operation can also be
implemented, returning the value at the front end without removing it.
The particular implementation of queue in this module is based on linked list,
as array based queue implementation is already supported in python's list. In
the linked list based implementation, the queue object need to keep track of
the front and the rear nodes where each node contains an item and a link to the
next node.
.. note:: For most practical purposes, the python's implementation as dequeue
suffices as a queue object. Use append method instead of enqueue and
popleft method instead of dequeue for queue operations in a list.
Complexity:
* push -- O(1)
* pop -- O(1)
* peek -- O(1)
"""
class _Node(object):
"""An internal class that represents a node with a single value
and links to other nodes.
"""
def __init__(self, item):
self.item = item
self.next = None
class Queue(object):
"""An implementation of a simple queue with linked list."""
def __init__(self):
"""Initialize an empty queue."""
self._first = None
self._last = None
self._size = 0
@property
def size(self):
"""The number of items in the queue."""
return self._size
def isEmpty(self):
"""Check if the queue is empty.
Returns:
True if the queue is empty.
False otherwise.
"""
return self._size == 0
def enqueue(self, item):
"""Insert an item to the queue."""
n = self._last
self._last = _Node(item)
if self.isEmpty():
self._first = self._last
else:
n.next = self._last
self._size += 1
def dequeue(self):
"""Remove and return the first item from the queue.
Returns:
The first item from the queue.
Raises:
IndexError: If the queue is empty.
"""
if self.isEmpty():
raise IndexError("dequeue from empty queue")
n = self._first
self._first = self._first.next
self._size -= 1
return n.item
def peek(self):
"""Return the first item from the queue.
Returns:
The first item from the queue.
Raises:
IndexError: If the queue is empty.
"""
if self.isEmpty():
raise IndexError("peek at empty queue")
return self._first.item
def __iter__(self):
"""Return iterator for the queue."""
current = self._first
while current:
yield current.item
current = current.next
def __str__(self):
"""String representation of the queue."""
return " ".join([str(item) for item in self])
def __repr__(self):
"""Representation of the queue."""
return "Queue(" + str(self) + ")"
if __name__ == "__main__":
print("Queue using linked list.")
q = Queue()
while True:
n = int(raw_input("Enter a number to enter or 0 to pop a number"
" (exit when queue empty): "))
if n:
q.enqueue(n)
print("Queued: " + str(n))
print("Current queue: " + str(q))
else:
if q.isEmpty():
print("Queue is empty.")
break
print("Dequeued: " + str(q.dequeue()))
print("Current queue: " + str(q))