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

2019-10-09T03:55:01Z

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

← Older revision		Revision as of 03:55, 9 October 2019
Line 1:		Line 1:
	See code on git.charlesreid1.com: https://charlesreid1.com~~:3000~~/cs/python/src/master/stacks-queues-deques/deque/ArrayDeque.py		See code on git.charlesreid1.com: https://git.charlesreid1.com/cs/python/src/master/stacks-queues-deques/deque/ArrayDeque.py

	Double-ended queue (deque) implemented using an underlying array-based structure - a list. (See also: [[Arrays/Python]]		Double-ended queue (deque) implemented using an underlying array-based structure - a list. (See also: [[Arrays/Python]]

Admin: /* Flags */

2017-09-09T17:06:06Z

Flags

← Older revision		Revision as of 17:06, 9 September 2017
Line 209:		Line 209:

	==Flags==		==Flags==

			{{StacksQueuesFlag}}

	[[Category:Queues]]		[[Category:Queues]]
	[[Category:Python]]		[[Category:Python]]
	[[Category:Python Queues]]		[[Category:Python Queues]]
	~~{{DataStructuresFlag}}~~		[[Category:Deques]]

Admin at 08:21, 30 May 2017

2017-05-30T08:21:33Z

← Older revision		Revision as of 08:21, 30 May 2017
Line 205:		Line 205:
	['1', None, None, None]		['1', None, None, None]
	</pre>		</pre>



			==Flags==

			[[Category:Queues]]
			[[Category:Python]]
			[[Category:Python Queues]]
			{{DataStructuresFlag}}

Admin: Created page with "See code on git.charlesreid1.com: https://charlesreid1.com:3000/cs/python/src/master/stacks-queues-deques/deque/ArrayDeque.py Double-ended queue (deque) implemented using an..."

2017-05-30T08:21:04Z

Created page with "See code on git.charlesreid1.com: https://charlesreid1.com:3000/cs/python/src/master/stacks-queues-deques/deque/ArrayDeque.py Double-ended queue (deque) implemented using an..."

New page

See code on git.charlesreid1.com: https://charlesreid1.com:3000/cs/python/src/master/stacks-queues-deques/deque/ArrayDeque.py

Double-ended queue (deque) implemented using an underlying array-based structure - a list. (See also: [[Arrays/Python]]

==ArrayDeque test==

<pre>

if __name__=="__main__":
d = ArrayDeque()
for i,c in enumerate("ABCDEFGHIJKLMNOP"):
d.add_first(c)
print(d)

for j in range(100):
try:
d.delete_first()
print(d)
except Empty:
pass

print("Length of d: {0}".format(len(d)))

for i,c in enumerate("12345"):
d.add_last(c)
print(d)

for j in range(4):
d.delete_last()
print(d)

print("final:")
print(d)
</pre>

==ArrayDeque class==

<pre>
"""
Deque (double-ended queue) ADT

ArrayDeque: implements an array-based double-ended queue

A deque object D implements the following core methods:
* D.add_first : add the item to the front of the deque
* D.add_last : add the item to the end of the deque
* D.delete_first : remove and return the ifrst item from the deque
* D.delete_last : remove and return the last item from the deque

Additional convenience methods:
* D.first : peek at first item
* D.last : peek at last item
* D.is_empty : returns True if deque has no elements
* D.__len__ : length
* D.__str__ : turn into string)

Private utility methods:
* D._resize : resize the deque (dynamic growth/shrinkage)

"""

class Empty(Exception):
pass

class ArrayDeque:
"""
"""
def __init__(self):
INIT_CAP = 10
self._first = 0
self._data = [None]*INIT_CAP
self._n = 0

def __len__(self):
"""length of deque"""
return self._n

def __str__(self):
"""string representation of deque"""
return str(self._data)

def is_empty(self):
"""returns true if deque is empty"""
return self._n==0

def add_first(self, e):
"""add item to beginning of deque"""
if(self._n==len(self._data)):
self._resize(2*self._n)
# First minus one because moving one index ahead of first
addix = (self._first - 1)%len(self._data)
self._data[addix] = e
self._first = addix
self._n += 1

def add_last(self, e):
"""add item to end of deque"""
if(self._n==len(self._data)):
self._resize(2*self._n)
# First plus n: jumping to the next open index,
# which must be index first + n.
# If there are n items starting at first, then they will be
# at first through (first + n - 1).
# Next open index is at first + n.
addix = (self._first + self._n)%(len(self._data))
self._data[addix] = e
self._n += 1

def delete_first(self):
if(not self.is_empty()):
ret = self._data[self._first]
self._data[self._first] = None
self._first = (self._first + 1)%(len(self._data))
self._n -= 1

# If we're down to smaller than a quarter occupied,
# cut array size in half.
if(self._n < len(self._data)//4):
self._resize(len(self._data)//2)

else:
raise Empty("oops, empty deque")

def delete_last(self):
if(not self.is_empty()):
getix = (self._first + self._n - 1)%(len(self._data))
ret = self._data[getix]
self._data[getix] = None
self._n -= 1

# If we're down to smaller than a quarter occupied,
# cut array size in half.
if(self._n < len(self._data)//4):
self._resize(len(self._data)//2)

else:
raise Empty("oops, empty deque")

def _resize(self,newcap):
"""private method: resize the underlying array"""
old = self._data
self._data = [None]*newcap
walk = self._first

# Need to pay close attention here:
# range over each of the n elements
for k in range(self._n):
self._data[k] = old[walk]
# Increment walk after the update, not before
walk += 1
walk %= len(old)

self._first = 0
</pre>

==ArrayDeque test output==

<pre>
$ python ArrayDeque.py
[None, None, None, None, None, None, None, None, None, 'A']
[None, None, None, None, None, None, None, None, 'B', 'A']
[None, None, None, None, None, None, None, 'C', 'B', 'A']
[None, None, None, None, None, None, 'D', 'C', 'B', 'A']
[None, None, None, None, None, 'E', 'D', 'C', 'B', 'A']
[None, None, None, None, 'F', 'E', 'D', 'C', 'B', 'A']
[None, None, None, 'G', 'F', 'E', 'D', 'C', 'B', 'A']
[None, None, 'H', 'G', 'F', 'E', 'D', 'C', 'B', 'A']
[None, 'I', 'H', 'G', 'F', 'E', 'D', 'C', 'B', 'A']
['J', 'I', 'H', 'G', 'F', 'E', 'D', 'C', 'B', 'A']
['J', 'I', 'H', 'G', 'F', 'E', 'D', 'C', 'B', 'A', None, None, None, None, None, None, None, None, None, 'K']
['J', 'I', 'H', 'G', 'F', 'E', 'D', 'C', 'B', 'A', None, None, None, None, None, None, None, None, 'L', 'K']
['J', 'I', 'H', 'G', 'F', 'E', 'D', 'C', 'B', 'A', None, None, None, None, None, None, None, 'M', 'L', 'K']
['J', 'I', 'H', 'G', 'F', 'E', 'D', 'C', 'B', 'A', None, None, None, None, None, None, 'N', 'M', 'L', 'K']
['J', 'I', 'H', 'G', 'F', 'E', 'D', 'C', 'B', 'A', None, None, None, None, None, 'O', 'N', 'M', 'L', 'K']
['J', 'I', 'H', 'G', 'F', 'E', 'D', 'C', 'B', 'A', None, None, None, None, 'P', 'O', 'N', 'M', 'L', 'K']
['J', 'I', 'H', 'G', 'F', 'E', 'D', 'C', 'B', 'A', None, None, None, None, None, 'O', 'N', 'M', 'L', 'K']
['J', 'I', 'H', 'G', 'F', 'E', 'D', 'C', 'B', 'A', None, None, None, None, None, None, 'N', 'M', 'L', 'K']
['J', 'I', 'H', 'G', 'F', 'E', 'D', 'C', 'B', 'A', None, None, None, None, None, None, None, 'M', 'L', 'K']
['J', 'I', 'H', 'G', 'F', 'E', 'D', 'C', 'B', 'A', None, None, None, None, None, None, None, None, 'L', 'K']
['J', 'I', 'H', 'G', 'F', 'E', 'D', 'C', 'B', 'A', None, None, None, None, None, None, None, None, None, 'K']
['J', 'I', 'H', 'G', 'F', 'E', 'D', 'C', 'B', 'A', None, None, None, None, None, None, None, None, None, None]
[None, 'I', 'H', 'G', 'F', 'E', 'D', 'C', 'B', 'A', None, None, None, None, None, None, None, None, None, None]
[None, None, 'H', 'G', 'F', 'E', 'D', 'C', 'B', 'A', None, None, None, None, None, None, None, None, None, None]
[None, None, None, 'G', 'F', 'E', 'D', 'C', 'B', 'A', None, None, None, None, None, None, None, None, None, None]
[None, None, None, None, 'F', 'E', 'D', 'C', 'B', 'A', None, None, None, None, None, None, None, None, None, None]
[None, None, None, None, None, 'E', 'D', 'C', 'B', 'A', None, None, None, None, None, None, None, None, None, None]
['D', 'C', 'B', 'A', None, None, None, None, None, None]
[None, 'C', 'B', 'A', None, None, None, None, None, None]
[None, None, 'B', 'A', None, None, None, None, None, None]
['A', None, None, None, None]
[None, None]
Length of d: 0
['1', None]
['1', '2']
['1', '2', '3', None]
['1', '2', '3', '4']
['1', '2', '3', '4', '5', None, None, None]
['1', '2', '3', '4', None, None, None, None]
['1', '2', '3', None, None, None, None, None]
['1', '2', None, None, None, None, None, None]
['1', None, None, None]
final:
['1', None, None, None]
</pre>

StacksQueues/Python/ArrayDeque - Revision history

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

Admin: /* Flags */

Admin at 08:21, 30 May 2017

Admin: Created page with "See code on git.charlesreid1.com: https://charlesreid1.com:3000/cs/python/src/master/stacks-queues-deques/deque/ArrayDeque.py Double-ended queue (deque) implemented using an..."