1. Engineering
  2. Computer Science
  3. 5 list and explain the bigoh runtimes of enqueue dequeue...

Question: 5 list and explain the bigoh runtimes of enqueue dequeue...

Question details

5. List and explain the Big-Oh runtimes of enqueue, dequeue, and getFront for 2 different implemenations of a queue. Both implementaions use a node-based implementation (single-link) that has pointers to both the head and tail nodes:

Implementation 1: enqueues at the head and dequeues at the tail
Implementation 2: enqueues at the tail and dequeues at the head

6. Suppose you have a circular array-based implementation of a Queue (as shown in the slides) and the array has a size of 100. If the data field front has the value 98 and the data field rear has the value 1, what will the values of front and rear be if 3 dequeue operations are performed, followed by 1 enqueue operation?

7. What is the Big-Oh runtime for a function that passes in an STL list of strings and then removes all strings in this list that have a size of 10 or larger. The function uses an iterator that steps through the list one item (string) at a time, calling erase on each string that it finds that has a size of 10 or larger. The string’s size function has a runtime of O(1).

8. If instead of the erase function, the programmer uses the STL list’s remove function in the previous question, what is the function's Big-Oh runtime now?

please explain each questions

Solution by an expert tutor
Blurred Solution
This question has been solved
Subscribe to see this solution