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.
Here is my C++ code so far, I am getting errors unitialized variable d, and newPtr.
#include "stdafx.h"
# include
# include
using namespace std;
/*----------------------------------------------*/
/* 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\n", isEmpty(d));
printf("Here is the deque, front to end: ");
printFrontToEnd(d);
printf(". Listing completed.\n");
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.\n");
printf("%d\n", isEmpty(d));
printf("%d\n", rmFront(d));
printFrontToEnd(d);
return 0;
}
/*----------------------------------------------*/
deque newEmptyDeque(void)
{
deque d;
d.front = (d.front);malloc(sizeof(node));
d.end = (d.end);malloc(sizeof(node));
d.size = (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 = (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;
}