creation of a queue

Posted on 2000-04-26
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
LVL 16

Accepted Solution

imladris earned 10 total points
Comment Utility
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

Comment Utility
that sums it all up very well!!! thank you

Featured Post

How to run any project with ease

Manage projects of all sizes how you want. Great for personal to-do lists, project milestones, team priorities and launch plans.
- Combine task lists, docs, spreadsheets, and chat in one
- View and edit from mobile/offline
- Cut down on emails

Join & Write a Comment

Suggested Solutions

Title # Comments Views Activity
memory leak detection 9 51
Programming Arduino to control a Max7219 using C 2 97
why "." vs "->" 23 115
Passing a array as parameter - C 2 77
Preface I don't like visual development tools that are supposed to write a program for me. Even if it is Xcode and I can use Interface Builder. Yes, it is a perfect tool and has helped me a lot, mainly, in the beginning, when my programs were small…
Windows programmers of the C/C++ variety, how many of you realise that since Window 9x Microsoft has been lying to you about what constitutes Unicode ( They will have you believe that Unicode requires you to use…
Video by: Grant
The goal of this video is to provide viewers with basic examples to understand and use for-loops in the C programming language.
Video by: Grant
The goal of this video is to provide viewers with basic examples to understand and use while-loops in the C programming language.

772 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

Need Help in Real-Time?

Connect with top rated Experts

10 Experts available now in Live!

Get 1:1 Help Now