A double-ended queue is a data structure that supports insertion and deletion at

Question

A double-ended queue is a data structure that supports insertion and deletion at both ends of the queue.
Suppose we add the findMin operation to the double-ended queue; findMin returns (but does not remove) the smallest item in the double-ended queue. Design a data structure that implements the double-ended queue in O(1) amortized cost for all operations. You must prove your time bound.

Explanation / Answer

Implement various operations of a double ended queue (Deque). Deque is a data structure where items can be inserted and removed from both ends. Operations :- insertToLeft(), removeFromLeft(), insertToRight(),removeFromRight(). This differs from the queue abstract data type or First-In-First-Out List (FIFO), where elements can only be added to one end and removed from the other. This general data class has some possible sub-types: * An input-restricted deque is one where deletion can be made from both ends, but insertion can only be made at one end. * An output-restricted deque is one where insertion can be made at both ends, but deletion can be made from one end only. Both the basic and most common list types in computing, queues and stacks can be considered specializations of deques, and can be implemented using deques. Implementations There are at least two common ways to efficiently implement a deque: with a modified dynamic array or with a doubly linked list. 1st Method using Doubly Linked List it works because we wants to do both operation start & end as DLL as prev & next pointers . it always possible to do above operation in O(1) 2nd Method Dynamic array implementation uses a variant of a dynamic array that can grow from both ends, sometimes called array deques. These array deques have all the properties of a dynamic array, such as constant time random access, good locality of reference, and inefficient insertion/removal in the middle, with the addition of amortized constant time insertion/removal at both ends, instead of just one end. Three common implementations include: * Storing deque contents in a circular buffer, and only resizing when the buffer becomes completely full. This decreases the frequency of resizings, but requires an expensive branch instruction for indexing. * Allocating deque contents from the center of the underlying array, and resizing the underlying array when either end is reached. This approach may require more frequent resizings and waste more space, particularly when elements are only inserted at one end. * Storing contents in multiple smaller arrays, allocating additional arrays at the beginning or end as needed. Indexing is implemented by keeping a dynamic array containing pointers to each of the smaller arrays. 1st Method - using Doubly Linked List #include #include /* Implement various operations of a double ended queue (Deque). Deque is a data structure where items can be inserted and removed from both ends. Operations :- insertToLeft(), removeFromLeft(), insertToRight(),removeFromRight(). */ using namespace std; class dequeu; struct node { int data; struct node *next; struct node *prev; friend class dequeue; }; typedef struct node* Node; class dequeue { Node head; Node tail; Node createNode(int data); public: dequeue():head(NULL),tail(NULL){} ~dequeue() { Node cur = head; Node temp = NULL; while(cur) { temp = cur; cur=cur->next; delete temp; temp =NULL; } head = tail = NULL; } void insertToLeft(int data); void insertToRight(int data); int removeFromLeft(); int removeFromRight(); void print(); }; Node dequeue::createNode(int data) { Node temp = new struct node; temp->data = data; temp->prev = NULL; temp->next = NULL; return temp; } void dequeue::insertToLeft(int data) { Node temp = createNode(data); if(head == NULL) { head= tail = temp; } else { temp->next = head; head->prev = temp; head = temp; } } void dequeue::insertToRight(int data) { Node temp = createNode(data); if(head == NULL) { head = tail = temp; } else { tail->next = temp; temp->prev = tail; tail = temp; } } int dequeue::removeFromLeft() { if(head == NULL) { coutprev= NULL; } delete temp; temp = NULL; } return 1; } int dequeue::removeFromRight() { if(tail == NULL) { coutnext = NULL; } delete temp; temp = NULL; } return 1; } void dequeue::print() { Node cur = head; while(cur) { cout

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

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