creation of a queue

Posted on 2000-04-26
Medium Priority
Last Modified: 2010-04-15
if i create a queue and a sequence of M insertions and N deletions are executed (in any order), then the queue will contain which elements? I say it is the smaller of M-N and MaxQueue. Am i right or wrong on this?
Question by:beachbumm
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
LVL 16

Accepted Solution

imladris earned 40 total points
ID: 2752523
Some constraints need to be indicated. I assume you are considering a FIFO queue (first in, first out) which is what happens at a cash register.
In this case one would normally also assume there will never be a deletion, unless there is something in the queue.

Now, if there is no maximum to the queue then M-N is the number of elements in the queue after M insertions and N deletions. And they are the M-N elements that were inserted LAST.

If there is a maximum size to the queue, an insertion can fail. For each failed insertion you will have one less element left in the queue at the end. However, the order now matters a lot. For instance, if insertions and deletions occur alternating, the queue will contain 0 or 1 elements until deletions run out, and then insertions will (potentially) fill up the queue. At that point you would indeed have the lesser of M-N or MaxQueue.

On the other hand, if all the insertions happen first, and then all the deletions, you would have the lesser of M-N or MaxQueue-N (depending on whether the insertions filled the queue or not).

Of course, if it isn't a FIFO queue, or deletions can happen on an empty queue, the results are different, or even less defined.

Author Comment

ID: 2752591
that sums it all up very well!!! thank you

Featured Post

Independent Software Vendors: We Want Your Opinion

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Have you thought about creating an iPhone application (app), but didn't even know where to get started? Here's how: ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ Important pre-programming comments: I’ve never tri…
This is a short and sweet, but (hopefully) to the point article. There seems to be some fundamental misunderstanding about the function prototype for the "main" function in C and C++, more specifically what type this function should return. I see so…
The goal of this video is to provide viewers with basic examples to understand and use structures in the C programming language.
The goal of this video is to provide viewers with basic examples to understand opening and writing to files in the C programming language.

719 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question