Question
CS 103 Lab - The Adventure of Links 1 Introduction In this lab you will implement a double-ended queue using a doubly-linked list. 2 What you will learn After completing this lab you should be able to Implement an efficient doubly-linked list Understand the APls for different kinds of lists . Work with pointers to objects Dynamically allocate memory Write a destructor to prevent memory leaks 3 Whatthe deque? There are many useful linear data structures, with different APIs. E.g., A stack is a sequence that supports insertion at one end, and deletion at the same end (so you always delete the newest item) A queue is a sequence that supports insertion at one end, and deletion at the opposite end (so you always delete the oldest item) . The most natural generalization is a sequence where you can insert or delete from either of the two ends. The C++ standard library calls this a double-ended queue, or a deque (pronounced "deck") for short. In this lab, you will create your own double- ended queue implementation How can we create a deque class? Linked lists are a flexible kind of data structure their contents can be spread out all over memory and re-spliced together without having to physically move the contents up/down in sequence. They have many applications. For example, in The Human Genome Project they were used because of their efficiency to perform essential operations. This may not be that surprising the natural process of meiotic recombination, crossing two sequences, strongly resembles what would result if two linked lists exchanged pointers In lecture we worked through many examples of singly-linked lists, which are capable of simulating stacks and queues efficiently (with constant time per operation, meaning no loops are necessary). However, in order to efficiently support both insertion and deletion from both the front and back, it is necessary that each list item both remembers its predecessor and its successor. This doubly- linked list approach is the one you will follow in order to implement your double- ended queue. (Note: it turns out the C++ deque class actually uses a completely different implementation. Stay tuned to learn more if you take CSCI 104.)
Explanation / Answer
code to implement doubly ended queue. #include #include #include using namespace std; class node { public: int data; class node *next; class node *prev; }; class dqueue: public node { node *head,*tail; int top1,top2; public: dqueue() { top1=0; top2=0; head=NULL; tail=NULL; } void push(int x){ node *temp; int ch; if(top1+top2 >=5) { cout next=NULL; head->prev=NULL; tail=head; top1++; } else { cout ch; if(ch==1) { top1++; temp=new node; temp->data=x; temp->next=head; temp->prev=NULL; head->prev=temp; head=temp; } else { top2++; temp=new node; temp->data=x; temp->next=NULL; temp->prev=tail; tail->next=temp; tail=temp; } } } void pop() { int ch; cout ch; if(top1 + top2 prev; tail->next=NULL; } } void display() { int ch; node *temp; cout ch; if(top1+top2