# Queue - Question 3 Answers

## 3 a

\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}


## 3 b

\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}


## 3 c

\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}


Return to Exercises