This is the C program. I don\'t know how to use double linked list to implement
ID: 3841059 • Letter: T
Question
This is the C program. I don't know how to use double linked list to implement it.
A deque is a data structure consisting of a list of items, on which the following operations are possible:
Push(X,D): Insert item X on the front end of deque D. Pop(D): Remove the front item from deque D and return it. Inject(X,D): Insert item X on the rear end of deque D. Eject(D): Remove the rear item from deque D and return it.
Write routines to support the deque that take O(1) time per operation. Your main program will print out the items in deque after each operation. Deque can have at most 30 items.
Sample input data format: Nop
Op X Op
...
/* Nop is the num of operations to be performed, and Op is the operation # with or without
an operand (e.g. shown below:
1 – Push, 2 – Pop, 3 – Inject, 4 – Eject). One example of input sequence is
sample output format:
5
1 3 Push: 3
3 7 Inject: 3 7
2 Pop: 7
3 2 Inject: 7 2
4 Eject: 7
Only integer operand is used.
Explanation / Answer
#ifndef_deque_h
#define_deque_h
Struct Node;
Typedef struct Node*PtrToNode;
Struct DequeRecord
{
PtrToNode Front,Rear;
};
Typedef struct DequeRecord*Deque;
void
Push(ElementType X,Deque D);
ElementType Pop(Deque D);
Void Inject(ElementType X,Deque D);
ElementType Eject(Deque D);
#endif
Struct Node
{
ElementType Element;
PtrToNode Next,Last;
};
Void Push(ElementType X,Deque D)
{
PtrToNode Newnode;
Newnode=malloc( Sizeof (Node));
If (Newnode==NULL) FatalError("The memory Is full.");
Newnode >Element=X;
Newnode >Next=D>Front >Next;
Newnode>Last=D >Front;
if( D >Front==D >Rear) D >Rear=Newnode;
else
D>Front>Next>Last=Newnode;
D >Front >Next=Newnode;
}
ElementType Pop(DequeD)
{
PtrToNode Temp;
ElementType Item;
if(D >Front==D >Rear)
return
Error("Deque is empty");
else
{
Temp=D >Front >next;
D >Front >Next=Temp >Next;
Temp >Next >Last=D >Front;
If (Temp==D >Rear)
D >Rear=D >Front;
Item=Temp >Element;
free(Temp);
return Item;
}
}
Void Inject(ElementType X,Deque D)
{
PtrToNode Newnode;
Newnode=malloc( sizeof (Node));
If (Newnode==NULL)
FatalError("The memory is full");
Newnode >Element=X; Newnode >Next=NULL;
Newnode >Last=D >Rear;
D> Rear >Next=Newnode;
D >Rear=Newnode;
}
ElementType Eject(Deque D)
{
PtrToNode Temp;
ElementType Item;
If (D >Front==D >Rear)
Return Error("Empty Deque");
else
{
Temp=D >Rear;
D >Rear=D >Rear >Last;
D >Rear >Next=NULL;
Item=Temp >Element;
free(Temp);
return Item;
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.