(a) (4 points) Implement a queue using a singly-linked list. The ENQUEUE and DEQ
ID: 3634750 • Letter: #
Question
(a) (4 points) Implement a queue using a singly-linked list. The ENQUEUEand DEQUEUE should take O(1) (i.e., constant) time.
(b) (4 points) Implement a stack using a singly-linked list. The PUSH and
POP should take O(1) (i.e., constant) time.
(c) (4 points) What is the difference between a binary search tree and a
heap?
Explanation / Answer
class Queue { // create List node with struct. struct ListNode { int data; ListNode* next; }; ListNode *first, *last; public: // create queue here. Queue() : first(NULL), last(NULL) { } void enqueue(int data); int dequeue(); }; // enquue the data.... void Queue::enqueue(int data) { ListNode *n = new ListNode; n->data = data; if(first == NULL && last == NULL) { first = last = n; } last->next = n; n->next = NULL; last = n; } // dequeue the data.... int Queue::dequeue() { if(first == NULL && last == NULL) return -1; int data = first->data; ListNode* next = first->next; if(first == last) { free(last); last = NULL; } else { free(first); } first = next; return data; } // call driver fucntion here void main() { Queue obj; obj.enqueue(20); obj.enqueue(200); obj.enqueue(37); obj.enqueue(45); coutRelated Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.