Solved

How to implement the standard Queue ADT?

Posted on 2008-06-16
8
1,263 Views
Last Modified: 2009-05-23
Hello.
I have to show how to implement the standard Queue ADT using only a Priority Queue and one additional integer instance variable. Can anyone provide a text description of the process?
0
Comment
Question by:secondcup
[X]
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
8 Comments
 
LVL 53

Expert Comment

by:Infinity08
ID: 21795843
Is this an assignment ? How far did you get ? What are you unsure about ?
0
 

Author Comment

by:secondcup
ID: 21796786
I have no idea how to implement the Queue ADT using only a Priority Queue and one additional integer instance variable.  I just know we can implement it by using List...but I do not get what it means by one additional integer..
0
 
LVL 53

Accepted Solution

by:
Infinity08 earned 168 total points
ID: 21796980
A queue is a special case of a priority queue, where the priority is basically the time of insertion.
0
Free Tool: Subnet Calculator

The subnet calculator helps you design networks by taking an IP address and network mask and returning information such as network, broadcast address, and host range.

One of a set of tools we're offering as a way of saying thank you for being a part of the community.

 
LVL 3

Assisted Solution

by:Sankozi
Sankozi earned 166 total points
ID: 21797194
I think this is good solution. You just need this additional integer to determine priority of next element that will be pushed.

class Queue
{
  PQueue pQueue = new PQueue(); 
  int nextPriority = Integer.MAX_VALUE;
 
  void push(T t)
  {
    pQueue.insertWithPriority(t, nextPriority --);
 
    if(nextPriority == Integer.MIN_VALUE)
    {
      reload(); //"restart" queue
    }
  }
 
  T pop()
  {
    p.getNext();
  }
 
  void reload()
  {
    oldPQ = pQueue;
    pQueue = new PQueue();
    nextPriority = Integer.MAX_VALUE;
 
    while(!oldPQ.empty())
    {
      push(oldPQ.pop());
    }
  }
}

Open in new window

0
 
LVL 53

Expert Comment

by:Infinity08
ID: 21797260
Sankozi, be careful with posting full code solutions to what might be an assignment - that's not permitted on this site.
0
 
LVL 1

Assisted Solution

by:CCSINCOMETRUST
CCSINCOMETRUST earned 166 total points
ID: 21917134
You may want to consider implementing a circular queue depending on what it will be used for and if you don't know how much it will hold ahead of time.

Hint: Google "Java Circular Queue" or "C++ Circular Queue" - you should have no problem finding code that you can use.
0

Featured Post

Free Tool: ZipGrep

ZipGrep is a utility that can list and search zip (.war, .ear, .jar, etc) archives for text patterns, without the need to extract the archive's contents.

One of a set of tools we're offering as a way to say thank you for being a part of the community.

Question has a verified solution.

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

Okay. So what exactly is the problem here? How often have we come across situations where we need to know if two strings are 'similar' but not necessarily the same? I have, plenty of times. Until recently, I thought any functionality like that wo…
Article by: Nadia
Linear search (searching each index in an array one by one) works almost everywhere but it is not optimal in many cases. Let's assume, we have a book which has 42949672960 pages. We also have a table of contents. Now we want to read the content on p…
I've attached the XLSM Excel spreadsheet I used in the video and also text files containing the macros used below. https://filedb.experts-exchange.com/incoming/2017/03_w12/1151775/Permutations.txt https://filedb.experts-exchange.com/incoming/201…
Attackers love to prey on accounts that have privileges. Reducing privileged accounts and protecting privileged accounts therefore is paramount. Users, groups, and service accounts need to be protected to help protect the entire Active Directory …

763 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