Antoun J. Yaacoub Ph.D.

Complete the following abstract data type \(\texttt{Q2En}\) (Queue with 2 ends), which is a linked structure of elements supporting the insertion and removal of elements at the beginning and at the end, by including operators allowing to: create a \(\texttt{Q2En}\), add an element to the top of a \(\texttt{Q2En}\), add an element at the end of a \(\texttt{Q2En}\), remove the element placed at the top of a \(\texttt{Q2En}\), remove the element placed at the end of a \(\texttt{Q2En}\), return the element placed at the beginning of a \(\texttt{Q2En}\), return the element placed at the end of a \(\texttt{Q2En}\), number of elements in a \(\texttt{Q2En}\), testing whether a \(\texttt{Q2En}\) is empty.

Type: \(\texttt{Q2En}\)
Parameter: \(\texttt{Element}\)
Use: \(\texttt{Boolean, Integer}\)
Functions:
\(\begin{array}{p{1cm} l l l} & \textbf{Create}: & & \rightarrow \texttt{Q2En}\\
& \textbf{Add_top}: & \texttt{Q2En} \times \texttt{Element} & \rightarrow \texttt{Q2En}\\ & \textbf{Add_end}: & \texttt{Q2En} \times \texttt{Element} & \rightarrow \texttt{Q2En}\\ & \textbf{Delete_top}: & \texttt{Q2En} & \rightarrow \texttt{Q2En}\\ & \textbf{Delete_end}: & \texttt{Q2En} & \rightarrow \texttt{Q2En}\\ & \textbf{Top}: & \texttt{Q2En} & \rightarrow \texttt{Element}\\ & \textbf{End}: & \texttt{Q2En} & \rightarrow \texttt{Element}\\ & \textbf{Number_of_elements}: & \texttt{Q2En} & \rightarrow \texttt{Integer}\\ & \textbf{Is_empty}: & \texttt{Q2En} & \rightarrow \texttt{Boolean}\\ \end{array}\)

Constructors: \(\texttt{Create, Add_end}\)
Preconditions: ...
Axioms: ...

Fill in missing paragraphs.

Difficulty level

This exercise is mostly suitable for students

Preconditions :
Let q be a Q2En
	* Delete_top(q) is defined iff !is_empty(q)
	* Delete_end(q) is defined iff !is_empty(q)
	* Top(q) is defined iff !is_empty(q)
	* End(q) is defined iff !is_empty(q)
Axioms:
Let q be a Q2En, and e, e1 be 2 elements
	* Add_top(Create(),e) = Add_end(Create(),e)
	* Add_top(Add_end(q,e),e1) = Add_end(Add_top(q,e1),e)
	* Delete_top(Add_end(q,e)) = if (!empty(q)) Add_end(Delete_top(q),e) else Create()
	* Delete_end(Add_end(q,e)) = q
	* Top(Add_end(q,e))= if (!empty(q)) Top(q) else e
	* End(Add_end(q,e))=e
	* Number_of_element(Create())=0
	* Number_of_element(Add_end(q,e))= Number_of_element(q)+1
	* Is_empty(Create())= true
	* Is_empty(Add_end(q,e))= false

Back to the list of exercises

Looking for a more challenging exercise, try this one !!

Cycles

ADT for a Deque