Queue - Question 3 Answers

\begin{algorithm}
\caption{Circular Queue}
\begin{algorithmic}
\REQUIRE size = maximum number of items the queue can hold
\OUTPUT circular queue data structure
\FUNCTION{create}{size}
    \STATE queue $\gets$ new memory allocation
    \STATE queue.array $\gets$ array of size
    \STATE queue.maxSize $\gets$ size
    \STATE queue.back $\gets$ 0
    \STATE queue.front $\gets$ 0
    \STATE queue.itemCount $\gets$ 0
    \RETURN{queue}
\ENDFUNCTION
\STATE
\REQUIRE queue = queue data structure
\REQUIRE value = value to add to the queue
\FUNCTION{enqueue}{queue, value}
    \IF{queue.itemCount = queue.maxSize}
        \STATE stack overflow
    \ENDIF
    \STATE queue.array[back] $\gets$ value
    \STATE queue.itemCount $\gets$ queue.itemCount + 1
    \STATE queue.back $\gets$ (queue.back + 1) $\bmod$ queue.maxSize
\ENDFUNCTION
\STATE
\REQUIRE queue = queue data structure
\OUTPUT oldest item in the queue
\FUNCTION{dequeue}{queue}
    \IF{queue.itemCount = 0}
        \STATE stack underflow
    \ENDIF
    \STATE value $\gets$ queue.array[queue.front]
    \STATE queue.itemCount $\gets$ queue.itemCount - 1
    \STATE queue.front $\gets$ (queue.front + 1) $\bmod$ queue.maxSize
    \RETURN{value}
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}

\begin{algorithm}
\caption{Deque}
\begin{algorithmic}
\OUTPUT deque data structure
\FUNCTION{create}{}
    \STATE deque $\gets$ new memory allocation
    \STATE deque.list $\gets$ new linked list
    \STATE deque.itemCount = 0
    \RETURN deque
\ENDFUNCTION
\STATE
\REQUIRE deque = deque data structure
\REQUIRE value = value to add to the top of the deque
\FUNCTION{push}{deque, value}
    \STATE \CALL{LinkedListInsertAtHead}{deque.list, value}
    \STATE deque.itemCount $\gets$ deque.itemCount + 1
\ENDFUNCTION
\STATE
\REQUIRE deque = deque data structure
\REQUIRE value = value to the bottom of the deque
\FUNCTION{push}{deque, value}
    \STATE \CALL{LinkedListInsertAtTail}{deque.list, value}
    \STATE deque.itemCount $\gets$ deque.itemCount + 1
\ENDFUNCTION
\STATE
\REQUIRE deque = deque data structure
\OUTPUT value at the top of the deque
\FUNCTION{pop}{deque}
    \IF{deque.itemCount = 0}
        \STATE deque underflow
    \ENDIF
    \STATE value $\gets$ deque.list.head
    \STATE deque.itemCount $\gets$ deque.itemCount - 1
    \STATE \CALL{LinkedListDeleteAtHead}{deque.list}
    \RETURN value
\ENDFUNCTION
\STATE
\REQUIRE deque = deque data structure
\OUTPUT value at the bottom of the deque
\FUNCTION{popRight}{deque}
    \IF{deque.itemCount = 0}
        \STATE deque underflow
    \ENDIF
    \STATE value $\gets$ deque.list.tail
    \STATE deque.itemCount $\gets$ deque.itemCount - 1
    \STATE \CALL{LinkedListDeleteAtTail}{deque.list}
    \RETURN value
\ENDFUNCTION
\STATE
\REQUIRE deque = deque data structure
\FUNCTION{peek}{deque}
    \IF{deque.itemCount = 0}
        \STATE deque underflow
    \ENDIF
    \RETURN deque.list.head
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}

\begin{algorithm}
\caption{Queue Using Two Stacks}
\begin{algorithmic}
\OUTPUT queue data structure
\FUNCTION{create}{}
    \STATE queue $\gets$ new memory allocation
    \STATE queue.inputStack $\gets$ new stack
    \STATE queue.outputStack $\gets$ new stack
    \STATE queue.itemCount = 0
    \RETURN queue
\ENDFUNCTION
\STATE
\REQUIRE queue = queue data structure
\REQUIRE value = value to add to the queue
\FUNCTION{enqueue}{queue, value}
    \STATE \CALL{StackPush}{queue.inputStack, value}
    \STATE queue.itemCount $\gets$ queue.itemCount + 1
\ENDFUNCTION
\STATE
\REQUIRE queue = queue data structure
\FUNCTION{dequeue}{queue}
    \IF{stack.itemCount = 0}
        \STATE stack underflow
    \ENDIF
    \IF{\CALL{StackIsEmpty}{queue.outputStack} = TRUE}
        \WHILE{\CALL{StackIsEmpty}{queue.inputStack} = FALSE}
            \STATE value $\gets$ \CALL{StackPop}{queue.inputStack}
            \STATE \CALL{StackPush}{queue.outputStack, value}
        \ENDWHILE
    \ENDIF
    \STATE queue.itemCount $\gets$ queue.itemCount - 1
    \RETURN{\CALL{StackPop}{queue.outputStack}}
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}