Suppose you have a deque D containing the numbers(1,2,3,4,5,6,7,8),in this order

Question

Suppose you have a deque D containing the numbers(1,2,3,4,5,6,7,8),in this order. Suppose further that you have an initially empty queue Q. Give a pseudo-code description of a function that uses only D and Q(and no other variables or objects) and results in D storing the elements(1,2,3,5,4,6,7,8), in this order

Explanation / Answer

/*----------------------------------------------*/ /* PRECOMPILER DIRECTIVES */ # include # include /*----------------------------------------------*/ /* TYPES */ typedef int itemtype; struct node { struct node * previous; itemtype item; struct node * next; }; typedef struct node node; struct deque { node * front; /* pointer to a dummy node. */ node * end; /* pointer to a dummy node. */ int *size; }; typedef struct deque deque; /*----------------------------------------------*/ /* PROTOTYPES */ deque newEmptyDeque(void); int isEmpty(deque d); void printFrontToEnd(deque d); void insertAfterInDLL(itemtype i, node * nodePtr); /* auxiliary */ void addToFront(itemtype i, deque d); void addToEnd(itemtype i, deque d); itemtype getFront(deque d); itemtype getEnd(deque d); itemtype rmFront(deque d); /*----------------------------------------------*/ int main(void){ deque d; d = newEmptyDeque(); printf("%d ", isEmpty(d)); printf("Here is the deque, front to end: "); printFrontToEnd(d); printf(". Listing completed. "); addToFront(1,d); addToFront(2,d); addToFront(3,d); addToEnd(4,d); addToEnd(5,d); addToEnd(6,d); printf("Here is the deque, front to end: "); printFrontToEnd(d); printf(". Listing completed. "); printf("%d ", isEmpty(d)); printf("%d ", rmFront(d)); printFrontToEnd(d); return 0; } /*----------------------------------------------*/ deque newEmptyDeque(void){ deque d; d.front = malloc(sizeof(node)); d.end = malloc(sizeof(node)); d.size = malloc(sizeof(int)); *(d.size)=0; (d.front)->next = d.end; (d.front)->previous = NULL; (d.end)->previous = d.front; (d.end)->next = NULL; return d; } /*----------------------------------------------*/ int isEmpty(deque d){ return (d.front)->next == d.end; } /*----------------------------------------------*/ void printFrontToEnd(deque d){ node * aux; aux = (d.front)->next; while( (aux->next) != NULL) { printf("%d ", aux->item); aux = aux->next; } } /*----------------------------------------------*/ /* Auxiliary function to insert an item after a given node in a doubly linked list. */ void insertAfterInDLL(itemtype i, node * nodePtr){ node * nextPtr; /* next node after *nodePtr. */ node * newPtr; /* new node. */ nextPtr = nodePtr->next; newPtr = malloc(sizeof(node)); newPtr->item = i; nodePtr->next = newPtr; newPtr->previous = nodePtr; newPtr->next = nextPtr; nextPtr->previous = newPtr; } /*----------------------------------------------*/ void addToFront(itemtype i, deque d){ insertAfterInDLL(i, d.front); *(d.size)= *(d.size) +1; } /*----------------------------------------------*/ void addToEnd(itemtype i, deque d){ insertAfterInDLL(i, (d.end)->previous ); } /*----------------------------------------------*/ itemtype getFront(deque d){ return (d.front)->next->item; } itemtype getEnd(deque d){ return (d.end)->previous->item; } itemtype rmFront(deque d){ itemtype x = (d.front)->next->item; node * aux; aux = (d.front)->next->next; node * z; z = (d.front)->next; free(z); return x; }

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.