(a) (4 points) Implement a queue using a singly-linked list. The ENQUEUE and DEQ

Question

(a) (4 points) Implement a queue using a singly-linked list. The ENQUEUE
and 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); cout

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

---