Consider a queue data structure

Assignment Help Data Structure & Algorithms

Reference no: EM13163613

Consider a queue data structure, where the two operations of interest are enqueue (at the back of the queue) and dequeue (from the front of the queue). A queue is thus a FIFO (first in-first out) structure. Suppose we implement a queue by using two stacks, A and B, which support operations of push and pop, as follows:

enqueue(x): push x onto stack A

dequeue: if B is not empty return x = pop B

if B is empty

repeat until A is empty

x = pop A

push x onto stack B

return x = pop B

a) This implementation seems to correctly emulate a queue. Illustrate (by drawing the two stacks) how it works for the following sequence of enqueue and dequeue operations:

enqueue 5

enqueue 7

dequeue

enqueue 3

enqueue 6

enqueue 9

dequeue

b) The actual cost of a push or a pop operation is1. What is the worst-case single operation possible after a sequence of n enqueue and dequeue operations, and what is its cost?

c) Explain how a simplistic worst-case analysis would lead to the conclusion that this algorithm would be O(n2).

d) Using the accounting method, assign the lowest (integer) amortized cost possible to the enqueue operation and to the dequeue operation so that after any sequence of n1 enqueues and n2 dequeues, n1?n2, the amortized cost is ? the actual cost. Explain why this works.

e) Show that the total amortized cost, which is an upper bound for the actual cost, over a sequence of n operations is O(n).

Reference no: EM13163613

Questions Cloud

With replacement order matters : Given an alphabet of size N=9. Write a c++ program that compares the number of possible sequences of the length L that can be generated inder the following assumptions: With replacement order matters, without replacement order matters, and without..

Write a program to keep track of a cd or dvd collection. : write a program to keep track of a CD or DVD collection. This can only work exclusively with either CDs or DVDs since some of the data is different. The data will be stored ina file. The data from the file will be stored ina text file as records. Eac..

Consider a 2-dimensional mesh : Consider a 2-dimensional mesh with n^2 nodes. The shortest distance that a message travels in the mesh is 1 link; the longest distance is 2(n-1) link

Convert meters to feet and inches. : 1. Write a program that can be used to convert meters to feet and inches. Allow the user to enter a metric meter value in a method .

Consider a queue data structure : Consider a queue data structure, where the two operations of interest are enqueue (at the back of the queue) and dequeue (from the front of the queue). A queue is thus a FIFO (first in-first out) structure. Suppose we implement a queue by using tw..

Find all irreducible polynomials : Find all irreducible polynomials

Consider the predator-prey models : Consider the predator-prey models developed early part of the 20 th century in which the number of predators and preys may be predicted using the pair of ODEs

Create a crow''s foot erd using a specialization hierarchy : Given the following business scenario, create a Crow's Foot ERD using a specialization hierarchy if appropriate. Tiny Hospital keeps information on patients and hospital rooms

Define a certain reaction has an activation energy : A certain reaction has an activation energy of 60.0 kj/mol and a frequency factor of A= 3.10×1012 M^-1s^-1 . What is the rate constant k , of this reaction at 30.0 Deg celsius?

User Account

All Pages