Admin: Replacing charlesreid1.com:3000 with git.charlesreid1.com

2019-10-09T03:55:11Z

Replacing charlesreid1.com:3000 with git.charlesreid1.com

← Older revision		Revision as of 03:55, 9 October 2019
Line 1:		Line 1:
	Queue data structure, implemented in Python using an underlying array-based structure - a list. (See also: [[Arrays/Python]])		Queue data structure, implemented in Python using an underlying array-based structure - a list. (See also: [[Arrays/Python]])

	Link: https://charlesreid1.com~~:3000~~/cs/python/src/master/stacks-queues-deques/queues/ArrayQueue.py		Link: https://git.charlesreid1.com/cs/python/src/master/stacks-queues-deques/queues/ArrayQueue.py

	==Class code==		==Class code==

Admin: /* Flags */

2017-09-09T17:06:29Z

Flags

← Older revision		Revision as of 17:06, 9 September 2017
Line 196:		Line 196:
	[[Category:Python]]		[[Category:Python]]
	[[Category:Queues]]		[[Category:Queues]]
			[[Category:Arrays]]
	[[Category:Python Queues]]		[[Category:Python Queues]]

	{{~~DataStructuresFlag~~}}		{{StacksQueuesFlag}}

Admin: /* git.charlesreid1.com */

2017-06-05T21:31:38Z

git.charlesreid1.com

← Older revision		Revision as of 21:31, 5 June 2017
Line 1:		Line 1:
	~~==git~~.~~charlesreid1.com==~~		Queue data structure, implemented in Python using an underlying array-based structure - a list. (See also: [[Arrays/Python]])

	Link: https://charlesreid1.com:3000/cs/python/src/master/stacks-queues-deques/queues/ArrayQueue.py		Link: https://charlesreid1.com:3000/cs/python/src/master/stacks-queues-deques/queues/ArrayQueue.py

Admin: /* Output */

2017-05-30T06:57:46Z

Output

← Older revision		Revision as of 06:57, 30 May 2017
Line 128:		Line 128:

	==Output==		==Output==

			<pre>

	$ python ArrayQueue.py		$ python ArrayQueue.py
Line 189:		Line 191:

	</pre>		</pre>


	=Flags=		=Flags=

Admin: Created page with "==git.charlesreid1.com== Link: https://charlesreid1.com:3000/cs/python/src/master/stacks-queues-deques/queues/ArrayQueue.py ==Class code==

 """ Queue ADT: ArrayQueue..."

2017-05-30T06:57:29Z

Created page with "==git.charlesreid1.com== Link: https://charlesreid1.com:3000/cs/python/src/master/stacks-queues-deques/queues/ArrayQueue.py ==Class code== <pre> """ Queue ADT: ArrayQueue..."

New page

==git.charlesreid1.com==

Link: https://charlesreid1.com:3000/cs/python/src/master/stacks-queues-deques/queues/ArrayQueue.py

==Class code==

<pre>
"""
Queue ADT: ArrayQueue

This class implements the following methods:
Q.enqueue(e)
Q.dequeue()
Q.first()
Q.is_empty()
len(Q)

This class utilizes an array-based data structure.

The Queue class needs to keep track of where the
beginning and end of the structure is.
This will dynamically expand under the hood
as needed. This is an O(1) data structure,
when amortized.

It needs to keep track of three things:
- pointer to first item in queue
- number of elements in queue (use in place of last pointer)
- pointer to data structure itself

"""

class Empty(Exception):
pass

class ArrayQueue:

def __init__(self):
"""Keep track of 3 things"""
INIT_CAP = 10
self._data = [None]*INIT_CAP
self._front = 0
self._n = 0

def __len__(self):
"""Return number of elements in queue"""
return self._n

def __str__(self):
return str(self._data)
#ix_sequence = [(self._front+i)%(len(self._data)) for i in range(self._n)]
#contents = ",".join([str(self._data[ix]) for ix in ix_sequence])
#return "[" + contents + "]"

#####################
# Note: start with the
# simple stuff. __getitem__,
# __len__, __init__, __str__, etc.

def is_empty(self):
"""Returns true if no elements in queue"""
return self._n==0

def dequeue(self):
"""Pop an item from the front of the queue (inch the front pointer along)"""
if(self.is_empty()):
raise Empty("oops, empty queue")

dafront = self._data[self._front]

self._data[self._front]=None # clean up
self._front = (self._front+1)%(len(self._data)) # update front pointer
self._n -= 1

# Really, we need to resize this thing to be smaller
# when we remove stuff from it.
# If it is too big by a quarter, chop it in half.
if(self._n < len(self._data)//4):
self.resize( len(self._data)//2 )

return dafront

def enqueue(self, e):
"""Add an item to the back of the queue"""
if(self._n==len(self._data)):
self.resize(2*self._n)

insert_index = (self._front + self._n )%(len(self._data))
self._data[insert_index] = e
self._n += 1

def resize(self,newsize):
"""Resize, and shift everything to the front"""
old = self._data
walk = self._front
self._data = [None]*newsize
for k in range(self._n):
self._data[k] = old[walk]
walk = (walk+1)%len(old)
self._front = 0

def first(self):
return self._data[self._first]
</pre>

==Class test==

<pre>
if __name__=="__main__":
print("Testing ArrayQueue.")
a = ArrayQueue()
for c in "ABCDEFGHIJKLMNOPQRSTUVWX":
a.enqueue(c)
print(a)
for i in range(15):
a.dequeue()
print(a)
for c in "9876543":
a.enqueue(c)
print(a)
for i in range(8):
a.dequeue()
print(a)
print("Final:")
print(a)
</pre>

==Output==

$ python ArrayQueue.py
Testing ArrayQueue.
['A', None, None, None, None, None, None, None, None, None]
['A', 'B', None, None, None, None, None, None, None, None]
['A', 'B', 'C', None, None, None, None, None, None, None]
['A', 'B', 'C', 'D', None, None, None, None, None, None]
['A', 'B', 'C', 'D', 'E', None, None, None, None, None]
['A', 'B', 'C', 'D', 'E', 'F', None, None, None, None]
['A', 'B', 'C', 'D', 'E', 'F', 'G', None, None, None]
['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', None, None]
['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', None]
['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J']
['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', None, None, None, None, None, None, None, None, None]
['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', None, None, None, None, None, None, None, None]
['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', None, None, None, None, None, None, None]
['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', None, None, None, None, None, None]
['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', None, None, None, None, None]
['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', None, None, None, None]
['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', None, None, None]
['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', None, None]
['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', None]
['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T']
['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None]
['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None]
['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None]
['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None]
[None, 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None]
[None, None, 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None]
[None, None, None, 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None]
[None, None, None, None, 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None]
[None, None, None, None, None, 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None]
[None, None, None, None, None, None, 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None]
[None, None, None, None, None, None, None, 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None]
[None, None, None, None, None, None, None, None, 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None]
[None, None, None, None, None, None, None, None, None, 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None]
[None, None, None, None, None, None, None, None, None, None, 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None]
[None, None, None, None, None, None, None, None, None, None, None, 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None]
[None, None, None, None, None, None, None, None, None, None, None, None, 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None]
[None, None, None, None, None, None, None, None, None, None, None, None, None, 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None]
[None, None, None, None, None, None, None, None, None, None, None, None, None, None, 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None]
['P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', None, None, None, None, None, None, None, None, None, None, None]
['P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', '9', None, None, None, None, None, None, None, None, None, None]
['P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', '9', '8', None, None, None, None, None, None, None, None, None]
['P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', '9', '8', '7', None, None, None, None, None, None, None, None]
['P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', '9', '8', '7', '6', None, None, None, None, None, None, None]
['P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', '9', '8', '7', '6', '5', None, None, None, None, None, None]
['P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', '9', '8', '7', '6', '5', '4', None, None, None, None, None]
['P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', '9', '8', '7', '6', '5', '4', '3', None, None, None, None]
[None, 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', '9', '8', '7', '6', '5', '4', '3', None, None, None, None]
[None, None, 'R', 'S', 'T', 'U', 'V', 'W', 'X', '9', '8', '7', '6', '5', '4', '3', None, None, None, None]
[None, None, None, 'S', 'T', 'U', 'V', 'W', 'X', '9', '8', '7', '6', '5', '4', '3', None, None, None, None]
[None, None, None, None, 'T', 'U', 'V', 'W', 'X', '9', '8', '7', '6', '5', '4', '3', None, None, None, None]
[None, None, None, None, None, 'U', 'V', 'W', 'X', '9', '8', '7', '6', '5', '4', '3', None, None, None, None]
[None, None, None, None, None, None, 'V', 'W', 'X', '9', '8', '7', '6', '5', '4', '3', None, None, None, None]
[None, None, None, None, None, None, None, 'W', 'X', '9', '8', '7', '6', '5', '4', '3', None, None, None, None]
[None, None, None, None, None, None, None, None, 'X', '9', '8', '7', '6', '5', '4', '3', None, None, None, None]
Final:
[None, None, None, None, None, None, None, None, 'X', '9', '8', '7', '6', '5', '4', '3', None, None, None, None]

</pre>

=Flags=

[[Category:Python]]
[[Category:Queues]]
[[Category:Python Queues]]

{{DataStructuresFlag}}

StacksQueues/Python/ArrayQueue - Revision history

Admin: Replacing charlesreid1.com:3000 with git.charlesreid1.com

Admin: /* Flags */

Admin: /* git.charlesreid1.com */

Admin: /* Output */

Admin: Created page with "==git.charlesreid1.com== Link: https://charlesreid1.com:3000/cs/python/src/master/stacks-queues-deques/queues/ArrayQueue.py ==Class code==
""" Queue ADT: ArrayQueue..."