StacksQueues/Python/ArrayQueue

From charlesreid1

Revision as of 06:57, 30 May 2017 by Admin (talk | contribs) (→‎Output)

git.charlesreid1.com

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

Class code

"""
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]

Class test

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)

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]

Flags



CSFlag.jpg
Data Structures
Part of Computer Science Notes

This is the staging ground for computer science notes as part of the 2017 CS Study Plan.


Data Structures

Classes of data structures: Abstract Data Types

Array-based and Link-based memory management: ArrayLists and Linked Lists

Algorithmic Analysis of Data Structures: Algorithmic Analysis of Data Structures

Advanced data structures: Advanced Data Structures


Flags  · Template:DataStructuresFlag  · e




CSFlag.jpg
Arrays
Part of Computer Science Notes

Series on Data Structures


Arrays Study Guide


Arrays

Python: Arrays/Python  · Arrays/Python/Sizeof  · Arrays/Python/AppendCost  · Arrays/Python/CaesarCipher  · Arrays/Python/CompactArrays  · Arrays/Python/DynamicArray

Java: Arrays/Java  · Arrays/Java/CaesarCipher  · Arrays/Java/FisherYates  · Arrays/Java/PythonList  · Arrays/Java/Repeatedly_Remove

Categories: Category:Python Arrays


Flags  · Template:ArraysFlagBase  · e




CSFlag.jpg
Stacks and Queues
Part of Computer Science Notes

Series on Data Structures


StacksQueues


Stacks and Queues: Python

StacksQueues/Python  · StacksQueues/Python/ArrayStack  · StacksQueues/Python/ArrayQueue  · StacksQueues/Python/ArrayDeque

StacksQueues/Python/LinkedStack


Stacks and Queues: Java

StacksQueues/Java  · StacksQueues/Java/ArrayStack  · StacksQueues/Java/ArrayQueue  · StacksQueues/Java/ArrayQueueFS  · StacksQueues/Java/ArrayDeque

StacksQueues/Java/LinkedStack  · StacksQueues/Java/LinkedQueue  · StacksQueues/Java/LinkedDeque


Applications

Postfix_Expressions#Stacks  · StacksQueues/Subsets  · StacksQueues/Subsets/Java


Flags  · Template:StacksQueuesFlagBase  · e




CSFlag.jpg
Priority Queues and Heaps
Part of Computer Science Notes

Series on Data Structures


Priority Queues

Java: Priority Queues/Java  · Priority Queues/ADT  · Priority Queues/Sorted  · Priority Queues/Unsorted

Performance: Priority Queues/Timing and Performance

Applications: Maximum Oriented Priority Queue  · Priority Queues/Stack


Heaps

Priority Queues/Heap  · Priority Queues/Java  · Priority Queues/Comparators

Heap Sort


Flags  · Template:PriorityQueuesFlagBase  · e




CSFlag.jpg
Linked List
Part of Computer Science Notes

Series on Data Structures


Lists Study Guide


Linked Lists

Java: Linked Lists/Java  · Linked Lists/Java/Single  · Linked Lists/Java/Double  · Linked Lists/Java/Circular

Performance: Linked Lists/Java/Timing  · Linked Lists/Java/Reverse

Python: Linked Lists/Python  · Linked Lists/Python/Single


Flags  · Template:LinkedListFlagBase  · e




CSFlag.jpg
Trees
Part of Computer Science Notes

Series on Data Structures


Trees Study Guide


Trees

Abstract data type: Trees/ADT

Concrete implementations: Trees/LinkedTree  · Trees/ArrayTree  · SimpleTree



Tree Traversal

Preorder traversal: Trees/Preorder

Postorder traversal: Trees/Postorder

In-Order traversal: Binary Trees/Inorder

Breadth-First Search: BFS

Breadth-First Traversal: BFT

Depth-First Search: DFS

Depth-First Traversal: DFT

OOP Principles for Traversal: Tree Traversal/OOP  · Tree Traversal/Traversal Method Template

Tree operations: Trees/Operations Performance  · Trees/Removal



Tree Applications

Expression Trees

Finding Minimum in Log N Time: Tree/LogN Min Search



Binary Trees

Abstract data type: Binary Trees/ADT

Concrete implementations: Binary Trees/LinkedBinTree  · Binary Trees/ArrayBinTree

Binary Trees/Cheat Sheet  · Binary Trees/OOP  · Binary Trees/Implementation Notes



Flags  · Template:TreesFlagBase  · e





CSFlag.jpg
Search Trees
Part of Computer Science Notes

Series on Data Structures


Search Trees

Binary Search Trees  · Balanced Search Trees

Trees/OOP  · Search Trees/OOP  · Tree Traversal/OOP  · Binary Trees/Inorder



Heaps

(Note that heaps are also value-sorting trees with minimums at the top. See Template:PriorityQueuesFlag and Priority Queues.)



Flags  · Template:SearchTreesFlagBase  · e




CSFlag.jpg
Maps and Dictionaries
Part of Computer Science Notes

Series on Data Structures


Maps and Sets Study Guide  · Hash Tables Study Guide


Maps/Dictionaries

Maps  · Maps/ADT  · Maps in Java  · Maps/OOP  · Maps/Operations and Performance

Multimaps  · Guava Maps

Map implementations: Maps/AbstractMap  · Maps/UnsortedArrayMap  · Maps/SortedArrayMap

Dictionaries

Dictionary implementations: Dictionaries/LinkedDict  · Dictionaries/ArrayDict


Hashes

Hash Maps/OOP  · Hash Maps/Operations and Performance

Hash Maps/Dynamic Resizing  · Hash Maps/Collision Handling with Chaining

Hash functions: Hash Functions  · Hash Functions/Cyclic Permutation

Hash map implementations: Hash Maps/AbstractHashMap  · Hash Maps/ChainedHashMap


Skip Lists

Skip Lists  · Java/ConcurrentSkipList  ·

Java implementations: SkipList


Sets

Sets  · Sets/ADT  · Sets in Java  · Sets/OOP  · Multisets


Flags  · Template:MapsFlagBase  · e





GraphFlag.png
Graphs
notes on graph theory, graph implementations, and graph algorithms

Part of Computer Science Notes

Series on Data Structures


Graphs


Graph Theory:

Graphs/Definitions  · Graphs/Matching  · Graphs/Connectivity

First Theorem of Graph Theory


Graph Implementations:

Graphs/Data Structures  · Graphs/ADT

Graphs/Java/Adjacency Map  · Graphs/Java/Adjacency Map Lite

Graphs/Guava


Graph Algorithms:

Algorithms/Graphs


Traversal:

Graphs/Traversal  · Graphs/Euler Tour  · Graphs/Depth First Traversal  · Graphs/Breadth First Traversal

Category:Traversal


Connectivity and Cycles:

Graphs/Finding Cycles  · Graphs/Finding Connected Components  · Graphs/Reachability


Transitive Closure:

Graphs/Transitive Closure  · Graphs/Floyd Warshall Algorithm


Shortest Path:

Graphs/Shortest Path  · Graphs/Edge Relaxation  · Graphs/Dijkstra


Minimum Spanning Tree:

Graphs/Minimum Spanning Tree  · Graphs/Prim Jarnik Algorithm  · Graphs/Kruskal Algorithm

Graphs/Cluster Finding


Directed Acyclic Graphs:

DAGs  · Graphs/Cycles  · Graphs/Topological Sort


Category:Graphs  · Category:Algorithms  · Category:CS  · Category:Data Structures


Flags  · Template:GraphsFlagBase  · e




Retrieved from "https://charlesreid1.com/w/index.php?title=StacksQueues/Python/ArrayQueue&oldid=17602"