Country or region and language

    Choose your country or region and your language.

    Suggested for you

      All countries and regions

        Choose your character

        It shows in the top bar and on your profile. Change it any time.

        Data structures with a Python queue

        Learn what data structures do, compare common types, and build a Python parcel queue with checked output, a stack variation, and duplicate-handling checks.

        A person practicing on a laptop in a quiet workspace

        Data structures organize values so a program can store, find, add, and remove them. Common structures include arrays, linked lists, stacks, queues, hash tables, sets, trees, and graphs. Choose a structure by the operations you need, especially whether order and duplicates matter.

        Data organization and behavior

        A data structure determines how your program organizes values and supports operations on those values. You'll put that idea into practice with a Python 3 parcel queue for a fictional Cebu dispatch desk: accept each parcel identifier once, then dispatch parcels in first-arrival order.

        Three related terms help you describe the solution clearly. A data type describes a kind of value, such as a string representing a parcel identifier. A data structure organizes values, such as a queue holding parcel identifiers. An algorithm is a sequence of steps, such as checking whether a parcel has appeared before, accepting a new parcel, and dispatching the oldest accepted parcel.

        Those distinctions matter when you explain your code in a skills test. Saying that you used Python doesn't explain the design. Saying that you used a set to reject duplicate scans and a queue to preserve arrival order explains the decisions.

        Common structures and their uses

        The right structure supports your program's frequent operations without breaking its ordering or duplicate rules. Start with the required behavior, then choose an implementation.

        Common structures and the operations they support
        StructureOrganization and typical operationOrdering or duplicate ruleWorkplace use
        ArrayIndexed sequence; retrieve an item by positionPreserves position; duplicates are possibleAccess a reading by its position in a series
        Linked listNodes connected by references; insert after a known nodeOrder follows the links; duplicates are possibleMaintain a sequence with insertions at known nodes
        StackAdd and remove at one endNewest item leaves firstTrack actions for an undo operation
        QueueAdd at the back and remove from the frontOldest item leaves firstDispatch parcels in arrival order
        Hash tableUse a key to locate an entryKeys are unique; ordering depends on the implementationLook up a parcel record by identifier
        SetStore unique values; test membershipRejects duplicate values; Python sets don't promise insertion orderTrack parcel identifiers already accepted
        TreeNodes organized into parent-child relationships; traverse branchesOrdering and duplicate rules depend on the treeRepresent a department hierarchy
        GraphNodes connected by edges; follow relationshipsConnections matter more than one linear orderRepresent delivery locations and routes

        In Python 3, a list is a resizable array. A dictionary, written as dict, maps unique keys to values using a hash table. A set stores unique hashable values. Hashable means a value has a stable hash value that supports dictionary lookup or set membership; strings qualify, so parcel identifiers work well.

        The collections.deque type supports adding and removing items at either end. A deque is a concrete container; queue and stack describe behavior. Removing the oldest item gives first-in, first-out behavior, while removing the newest item gives last-in, first-out behavior.

        Practice what this post teaches

        A checked parcel queue

        The fictional Cebu parcel desk must dispatch parcels in first-arrival order and ignore repeat scans during one run. The input list preserves every scan, the set remembers accepted identifiers, and the deque holds parcels awaiting dispatch.

        Save the following code as parcel_queue.py. The example uses Python 3; the run command shown afterward is for macOS or Linux with Python 3 installed. Keep the starting scans unchanged so you can compare your output with the expected result.

        # Fictional exercise: Cebu parcel desk
        # Target: accept each parcel ID once per run; dispatch oldest first.
        # Starting scans: P102, P101, P102, P103.
        # Calculation: retain first occurrences, then remove from the left.
        # Accepted arrival order: P102, P101, P103.
        # Run on macOS or Linux: python3 parcel_queue.py
        # Baseline expected output:
        # ['P102', 'P101', 'P103']
        # One dispatch per ID: True
        # First-arrival order: True
        #
        # Variation: in this file, change queue.popleft() to queue.pop().
        # Keep every other line and starting scan unchanged; run again.
        # Variation calculation: remove newest accepted IDs first.
        # Variation expected output:
        # ['P103', 'P101', 'P102']
        # One dispatch per ID: True
        # First-arrival order: False
        
        from collections import deque
        
        scans = ['P102', 'P101', 'P102', 'P103']
        seen = set()
        queue = deque()
        
        for parcel_id in scans:
            if parcel_id not in seen:
                seen.add(parcel_id)
                queue.append(parcel_id)
        
        dispatched = []
        while queue:
            dispatched.append(queue.popleft())
        
        print(dispatched)
        print('One dispatch per ID:',
              len(dispatched) == len(set(dispatched))
              and set(dispatched) == set(scans))
        print('First-arrival order:',
              dispatched == ['P102', 'P101', 'P103'])

        Open a terminal in the folder containing parcel_queue.py and run the file.

        python3 parcel_queue.py
        
        # Expected output:
        # ['P102', 'P101', 'P103']
        # One dispatch per ID: True
        # First-arrival order: True

        The first P102 scan isn't in seen, so set.add records the identifier and deque.append adds the parcel to the right end. P101 follows. The repeated P102 scan is already in seen, so the program skips the append. P103 becomes the final accepted parcel.

        The while loop continues until the deque is empty. Each deque.popleft call removes the leftmost parcel, so the oldest accepted parcel leaves first. The dispatched list records the removal order for checking.

        To practice reasoning about changing container state, try Stateful data structure design before continuing to the variation.

        A stack from the same input

        Removing from the right changes the accepted parcels into a last-in, first-out stack. The duplicate policy stays the same, but the dispatch order reverses.

        In parcel_queue.py, replace queue.popleft() with queue.pop() inside the while loop. Leave every other line unchanged, including the starting scans and the checks, then rerun the file.

        python3 parcel_queue.py
        
        # Expected output after the replacement:
        # ['P103', 'P101', 'P102']
        # One dispatch per ID: True
        # First-arrival order: False

        The False result is intentional: the variation no longer satisfies the original first-arrival requirement. P103 was accepted last, so deque.pop removes P103 first. The variable is still named queue, but a variable name doesn't enforce queue behavior; the operations do.

        Ordering and duplicate mistakes

        Check both accepted identifiers and dispatch order, because either check alone can miss a wrong result. The example keeps those checks separate so you can see which rule the stack variation breaks.

        The first check verifies that dispatches contain no duplicates and that their identifiers match the scanned identifiers. The second compares the entire dispatched list against the required arrival order. List equality checks positions as well as values.

        Don't convert the scans directly to a set and dispatch by iterating over that set. Python sets don't promise insertion order. Sorting the identifiers isn't a repair either: sorting would put P101 before P102, even though P102 arrived first.

        A Python list with front removal is also a poor default for a growing queue. Removing its first item requires shifting the remaining elements. A deque supports efficient removal from either end without shifting all the remaining items.

        The exercise has an important limitation: seen remembers accepted identifiers for the entire run. Removing a parcel from the deque doesn't remove its identifier from seen, so a later scan can't admit that parcel again during the run. Persistent storage, concurrent workers, and retry policies need additional design and aren't covered here.

        A reusable selection check

        Write down your required lookup, ordering, and duplicate behavior before choosing a structure. The parcel example needs two structures because membership tracking and ordered removal are different jobs.

        • Use a list for a sequence you access by position.
        • Use a dictionary when a unique key should retrieve an associated value.
        • Use a set for uniqueness or membership checks.
        • Use a deque when you add and remove items at the ends, especially for a queue.
        • Consider a tree for hierarchy or a graph for relationships between connected items.

        For your next attempt, reproduce the baseline without copying, predict the stack result, and explain why the repeated parcel appears only once. The Work Gym also has Python practice. When explaining your solution, name each structure's responsibility rather than only listing Python methods.

        Common questions

        What are data structures in programming? Data structures organize values and support operations such as lookup, insertion, and removal. In the parcel example, the set tracks accepted identifiers and the deque holds parcels in dispatch order.

        What are the most common data structures? Common structures include arrays, linked lists, stacks, queues, hash tables, sets, trees, and graphs. You don't need all of them for every task: the parcel example uses a list, a set, and a deque.

        How is a data structure different from a data type? A data type describes the kind of value and the operations that value supports, while a data structure describes how values are organized. In Python, those ideas overlap because containers also have types: a parcel identifier is a string, and the queue container is a deque.

        What's the difference between a stack and a queue? A stack removes the newest item first, while a queue removes the oldest item first. In the example, changing popleft to pop changes queue behavior to stack behavior without changing the accepted identifiers.

        Why use both a set and a deque? The set answers whether a parcel identifier has already been accepted. The deque preserves accepted arrival order and supports removing the oldest parcel efficiently; the deque alone doesn't reject duplicates.

        For another practice step, try More data structure design and use the same lookup, ordering, and duplicate checklist.

        Practice what this post teaches

        Your Work Gym account

        Save your progress and pick up on another device. Your browser's progress comes with you.

        or

        You can keep practicing without an account.

        Help and feedback

        Ask a question, tell us what is not working, or share an idea. We reply by email.

        What is it about?

        We use it only to reply to you.