CmSc 250 Intro to Algorithms

QUEUES

  1. Definition and basic operations
    2.

    Definition: A sequence of elements of the same type.
    The first stored element is first accessible.
    The structure is known also under the name FIFO - first in first out.

    Basic operations:

    Put (EnQueue): store a data item at the end of the queue

    Get (DeQueue): retrieve a data item from the beginning of the queue

  2. Queue ADT
    3.

    Notation:

    Q - queue
    e - item of same type as the elements of Q
    b - boolean value

    Operations:

    InitQueue(Q)
    Procedure to initialize Q to an empty queue

    QueueEmpty(Q) à b
    Boolean function that returns TRUE is Q is empty

    QueueFull(Q) à b
    Boolean function that returns TRUE if Q is full
    (used with array-based implementations of queues).

    Put(Q,e)
    Procedure to place an item e into Q at the end
    (if there is room, i.e. Q is not full, for array-based implementations)

    Get(Q)à e
    Procedure to take the first item stored in if Q is not empty

  3. Problems

    4. Problem 1:

    AppendQueue(Q,P): A procedure to append a queue P onto the end of a queue Q, leaving P empty.

    Pre: queue P and queue Q initialized (possibly empty)
    Post: Q contains all elements originally in Q followed by the elements
    that were in P in same order. P is empty.

    Algorithm:

    While not QueueEmpty(P) do

    e ¬ get(P)
    put(Q,e)

    The same problem can be solved using recursive function calls instead of a loop:

    AppendQueue(Q,P)

    {
    If not QueueEmpty(P) then

    e ¬ get(P)
    put(Q,e)
    AppendQueue(Q,P)
     else return
    }

    The "loop" version of the algorithm is the preferred one as it is simpler,
    and the recursion is nothing more than a hidden loop.

    Complexity of the algorithm: O(N), N - the number of elements in P.

    Problem 2: (Solution)

    ReverseQueue(Q): A procedure to reverse the elements in a queue Q

    Pre: queue Q, initialized (possibly empty)
    Post: Q contains all elements re-written in reverse order

    1. Design a non-recursive algorithm to solve the problem, using a stack
    2. Design a recursive algorithm to solve the problem.
    3. What is the complexity of these algorithms?

    Problem 3: (Solution)

    AppendReverseQueue(Q,P): A procedure to append a queue P in reverse order
    onto the end of a queue Q, leaving P empty.

    Pre: queue P and queue Q initialized (possibly empty)
    Post: Q contains all elements originally in Q followed by the elements
    that were in P in reverse order. P is empty

    1. Design a recursive algorithm to solve the problem
    2. What is the complexity of the algorithm?
Back to Contents page
Created by Lydia Sinapova