當前位置：首頁 » 編程語言 » java優先順序隊列

java優先順序隊列

發布時間: 2021-03-18 17:58:38

A. 什麼是java優先順序隊列(PriorityQueue)

PriorityQueue是一個基於優先順序堆的無界隊列，它的元素是按照自然順序(naturalorder)排序的。在創建的時候，可以給它提供一個負責給元素排序的比較器。PriorityQueue不允許null值，因為他們沒有自然順序，或者說他們沒有任何的相關聯的比較器。最後，PriorityQueue不是線程安全的，入隊和出隊的時間復雜度是O(log(n))。

B. 什麼是java優先順序隊列

樓主您好
PriorityQueue是一個基於優先順序堆的無界隊列，它的元素是按照自然順序(naturalorder)排序的。在創建的時候，可以給它提供一個負責給元素排序的比較器。PriorityQueue不允許null值，因為他們沒有自然順序，或者說他們沒有任何的相關聯的比較器。最後，PriorityQueue不是線程安全的，入隊和出隊的時間復雜度是O(log(n))。

C. java 優先隊列（priority queue）中，提取第二優先順序的值並刪除，但是不刪除第一優先值的數，怎麼實現

你要的是這樣的效果么

publicstaticvoidmain(String[]args){
PriorityQueue<Integer>pq=newPriorityQueue<Integer>();
pq.add(5);
pq.add(2);
pq.add(3);
pq.add(4);
System.out.println("取出了"+pq.poll()+",隊列剩餘"+Arrays.toString(pq.toArray()));

/**
*假設3是我不滿意的值，我要取到3後面的值
*/
if(pq.peek()==3){
System.out.println("3真不是我想要的，我可以接著往下處理么?ok,將3先保留吧");
inta=pq.poll();//將當前的第一級優先的值暫存下來，等第二級優先的值取出後再將其加入
pq.poll();
pq.add(a);
System.out.println("隊列剩餘"+Arrays.toString(pq.toArray()));
}

System.out.println("取出了"+pq.poll()+",隊列剩餘"+Arrays.toString(pq.toArray()));

}

列印效果:

取出了2,隊列剩餘[3, 4, 5]
3真不是我想要的，我可以接著往下處理么?ok,將3先保留吧
隊列剩餘[3, 5]
取出了3,隊列剩餘[5]

我覺得這個是優先隊列，雖然poll時候會將優先順序高的數據先取出，但是同樣的，如果加進去是高優先順序的數據下次取的時候它依然還是高優先順序的數據。

D. Java ！幫我定義一個優先隊列（priority queue）

PriorityQueue<String> queue= new PriorityQueue<String>();
//定義優先隊列，此處用了泛型.下面是添加元素：
queue.add("1");
queue.add("2");
queue.add("3");

E. java,優先順序隊列和有序數組區別

數組是有序的，訪問和修改都要按下標一個個地去找。
優先順序隊列，是要看優先順序的，誰的優先順序更高，誰就先得到許可權。不分排隊的順序。

F. 如何使用Java 5中的ExecutorService的我實現了任務優先順序

任務擴展Runnable或Callable<T>和Comparable。然後換一個ThreadPoolExecutor與PriorityBlockingQueue作為隊列，並且只接受任務，你的界面。以你的考慮，它看起來像一個選項是延長ThreadPoolExecutor，並重寫submit()方法。請參閱AbstractExecutorService看什麼默認的樣子，他們做的是包裹Runnable或Callable在FutureTask和execute()它。我想通過寫一個包裝類可能做到這一點，ExecutorService並委託給一個內ThreadPoolExecutor。包裝在有你的優先順序，從而使您的Comparator可以得到它

G. 問個java中有關優先隊列的問題，求高手！

pq.offer(new PriorityQData(alist[i],blist[i]));這個是向優先隊列中的插入語句

你插入的是PriorityQData數據類型，這個應該是你自己定義的數據類型吧
那麼pq.poll()返回的也應該是PriorityQData，而不是char，所以會出現：不兼容的類型

H. 優先順序調度演算法如何用JAVA實現

沒java的發段源代碼給你有興趣自己慢慢理解

#include <time.h>
#include <dos.h>
#include <math.h>
#include <conio.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <graphics.h>

#define ESC 0x1b
#define ENTER 0x0d
#define TRUE 1
#define FALSE 0
/*每隔TIME秒就變換一次優先順序*/
#define TIME 5

/*數據結構*/
/****************************************************************/
enum _Status/*進程狀態枚舉*/
{
READY =0,/*就緒*/
RUN,/*執行中*/
SUSPEND,/*掛起*/
};
typedef enum _Status Status;
/****************************************************************/
struct _Pcb/*進程結構*/
{
int PID;/*進程ID，ID為負數的進程為系統後備隊列的作業*/
int Time;/*進程運行需要的時間*/
int Prior;/*進程的優先順序，越大越優先*/
Status Sts;/*狀態*/
struct _Pcb *Next;/*指向本進程隊列中下個進程的PCB*/
};
typedef struct _Pcb PCB;
/****************************************************************/
struct _Batch/*多道處理中的道結構*/
{
PCB *pcb;/*該道當前正在處理的進程*/
struct _Batch *Next;/*下一道*/
};
typedef struct _Batch Batch;
/****************************************************************/
/*多道系統相關全局變數*/
PCB *ProcQueue = NULL;/*進程鏈表，按優先順序從大到小排列*/
Batch *BatchQueue = NULL;/*系統多道鏈表*/
/****************************************************************/

/*動態優先權搶占式調度演算法及相關函數聲明*/
/****************************************************************/
int InitBatchs(int n);/*初始化多道系統，n為道數*/
int InsertProc(int prior, int time);/*向進程鏈表中按優先順序大小插入一個新進程*/
int InsertIDLE();/*向進程隊列中加入後備進程，當系統空閑時將被調入*/
int SortProcQueue();/*將進程鏈表按優先順序從大到小排列*/
int AddBatch();/*增加系統道數*/
int DeleteBatch();/*減少系統道數*/
int UnSuspendProc(int id);/*解除ID為id的進程的掛起狀態*/
int UpdateBatchs();/*多道系統根據進程鏈表進行更新，並將執行完畢的進程刪除*/
int PassSeconds(int n);/*系統經過n秒後計算數據並進行優先順序調度*/
/****************************************************************/

/*各函數的定義*/
/****************************************************************/
int InitBatchs(int n)
{
int i;
for (i=0; i<n; ++i)
{
AddBatch();
}
return (UpdateBatchs());
}

int InsertProc(int prior, int time)
{
static int sysid = 0;/*該系統已經加入過多少進程，此值將是新進程的ID*/
PCB *last,*now,*pcb;
pcb = (PCB*)malloc(sizeof(PCB));
if (pcb == NULL) return FALSE;
pcb->Prior = prior;
pcb->Time = time;
pcb->PID = (++sysid);
pcb->Sts = READY;
if (ProcQueue == NULL)/*如果進程隊列為空*/
{
ProcQueue = pcb;
pcb->Next = NULL;
return TRUE;
}
last = ProcQueue;
now = last->Next;

if (pcb->Prior > last->Prior)/*pcb將排在隊頭*/
{
pcb->Next = ProcQueue;
ProcQueue = pcb;
return TRUE;
}
while ((now != NULL) && (pcb->Prior < now->Prior))/*尋找插入位置*/
{
last = now;
now = last->Next;
}
last->Next = pcb;
pcb->Next = now;
return TRUE;
}

int InsertIDLE()
{
PCB *now = ProcQueue;
PCB *idle = (PCB*)malloc(sizeof(PCB));
if (idle == NULL) return FALSE;
idle->PID = -1;
idle->Prior = -1;
idle->Sts = SUSPEND;
idle->Time = -1;
idle->Next = NULL;
if (ProcQueue == NULL)
{
ProcQueue = idle;
return TRUE;
}
while(now->Next != NULL)
{
now = now->Next;
}
now->Next = idle;
return TRUE;
}

int SortProcQueue()
{ /*冒泡排序*/
PCB *last, *now;
int b = FALSE;/*上次遍歷是否無交換產生*/
if (ProcQueue==NULL || ProcQueue->Next==NULL)/*如果鏈表中無進程或只有一個進程*/
return FALSE;
while (!b)
{
b = TRUE;
last=ProcQueue;
now=last->Next;
if (last->Prior < now->Prior)
{
ProcQueue = now;
last->Next = now->Next;
now->Next = last;
b = FALSE;
last = ProcQueue;
now = last->Next;
}
while (now->Next!=NULL)
{
if ((now->Prior)<(now->Next->Prior))
{
last->Next = now->Next;
now->Next = now->Next->Next;
last->Next->Next = now;
b = FALSE;
}
else
last = last->Next;
now = last->Next;
}
}
return TRUE;
}

int AddBatch()
{
Batch *bt = (Batch*)malloc(sizeof(Batch));
if (bt==NULL) return FALSE;
bt->Next = BatchQueue;
BatchQueue = bt;
bt->pcb = NULL;
return (InsertIDLE());
}

int DeleteBatch()
{
Batch *bt = BatchQueue;
PCB *last, *now;
if (BatchQueue==NULL || BatchQueue->Next==NULL)/*如果只剩最後一道則不刪除*/
return FALSE;
if (ProcQueue==NULL || ProcQueue->Next==NULL)/*如果只有最後一個後備空閑進程*/
return FALSE;/**/
last = ProcQueue;
now = last->Next;
while (now->Next != NULL)/*查找到最後一個進程，該進程必定是後備空閑進程*/
{
last = now;
now = last->Next;
}
if (now==NULL || now->PID>=0)/*未查找到後備進程*/
return FALSE;/**/
free(now);
last->Next = NULL;
BatchQueue = BatchQueue->Next;
free(bt);
return TRUE;
}

int UnSuspendProc(int id)
{
PCB *now = ProcQueue;
if (ProcQueue==NULL) return FALSE;
while (now != NULL)
{
if (now->PID == id)
{
now->Sts = READY;
return TRUE;
}
}
return FALSE;
}

int UpdateBatchs()
{
Batch *bt = BatchQueue;
PCB *last = ProcQueue, *now;
while (bt != NULL)
{
bt->pcb = NULL;
bt = bt->Next;
}
if (ProcQueue == NULL) return TRUE;
while (last->Sts==RUN && last->PID>=0 && last->Time<=0)
{
ProcQueue = ProcQueue->Next;
free(last);
last = ProcQueue;
}
now = last->Next;
while (now != NULL)
{
if (now->Sts==RUN && now->PID>=0 && now->Time<=0)/*如果該進程是運行中的一般進程並已執行完畢*/
{
last->Next = now->Next;
free(now);
}
else
last = last->Next;
now = last->Next;
}
bt = BatchQueue;
now = ProcQueue;
while (bt != NULL && now != NULL)
{
bt->pcb = now;
now->Sts = RUN;
bt = bt->Next;
now = now->Next;
}
while (now != NULL)
{
if (now->Sts == RUN)
{
now->Sts = SUSPEND;
}
now = now->Next;
}
return TRUE;
}

int PassSeconds(int n)
{
static int time = 0;
int i=0, ProcEnd = FALSE;
PCB *pcb = ProcQueue;
Batch *bt = BatchQueue;
if (bt == NULL) return FALSE;
time += n;
if (time>=TIME)
{
i = time/TIME;/*經過多少時間段*/
time = time%TIME;
}
while (bt != NULL)/*更新進程運行時間*/
{
if (bt->pcb->PID>=0)
{
bt->pcb->Time -= n;
if (bt->pcb->Time <= 0)/*進程結束*/
{
ProcEnd = TRUE;
}
}
bt = bt->Next;
}
if (i > 0)
{
while (pcb != NULL)/*更新進程優先權（動態優先權）*/
{
if (pcb->Sts == RUN && pcb->PID>=0)/*運行的進程優先權降低*/
{
pcb->Prior -= i;
if (pcb->Prior < 0)
pcb->Prior = 0;
}
else if (pcb->Sts == SUSPEND && pcb->PID>=0)/*掛起的進程優先權升高*/
pcb->Prior += i;
pcb = pcb->Next;
}
}
if (i>0)
SortProcQueue();/*如果優先順序有變動則重新排序*/
if (ProcEnd || i>0)
{
UpdateBatchs();/*更新多道進程*/
}
return TRUE;
}
/****************************************************************/

/*圖形界面相關函數*/
/****************************************************************/
/*表格的單位寬度和高度*/
#define WIDTH 64
#define HEIGHT 12
void *black=NULL;/*背景色方格，使用它擦出表格中的圖形*/
int InitGraph()/*初始化圖形界面*/
{
int GraphDriver; /* The Graphics device driver */
int GraphMode; /* The Graphics mode value */
int ErrorCode;
GraphDriver = DETECT; /* Request auto-detection */
initgraph( &GraphDriver, &GraphMode, "" );
ErrorCode = graphresult(); /* Read result of initialization*/
if( ErrorCode != grOk )
{ /* Error occured ring init */
printf(" Graphics System Error: %s\n", grapherrormsg( ErrorCode ) );
getch();
return FALSE;
}
cleardevice();
black = (void*)malloc(imagesize(1,1,WIDTH-1,HEIGHT-1));
getimage(1,1,WIDTH-1,HEIGHT-1,black);
DrawFrame();
DrawData();
return TRUE;
}
int DrawFrame()/*畫邊框和表頭*/
{
settextjustify(CENTER_TEXT, CENTER_TEXT);
gprintf(320, HEIGHT/2-1, "Multi-Batch System Emulation");
settextjustify(LEFT_TEXT, TOP_TEXT);
moveto(0,HEIGHT);
lineto(0,479);
lineto(639,479);
lineto(639,HEIGHT);
lineto(0,HEIGHT);
line(WIDTH*4,HEIGHT,WIDTH*4,479);
line(WIDTH*7,HEIGHT,WIDTH*7,479);
line(0,HEIGHT*2,639,HEIGHT*2);
line(0,HEIGHT*3,639,HEIGHT*3);
gprintf(HEIGHT*0+2,HEIGHT*1+2,"System Batchs");/*系統多道列表頭*/
gprintf(HEIGHT*0+2,HEIGHT*2+2,"Batch");
gprintf(WIDTH*1+2,HEIGHT*2+2,"ProcID");
gprintf(WIDTH*2+2,HEIGHT*2+2,"Time");
gprintf(WIDTH*3+2,HEIGHT*2+2,"Prior");
gprintf(WIDTH*4+2,HEIGHT*1+2,"Suspended Processes");/*掛起隊列列表頭*/
gprintf(WIDTH*4+2,HEIGHT*2+2,"ProcID");
gprintf(WIDTH*5+2,HEIGHT*2+2,"Time");
gprintf(WIDTH*6+2,HEIGHT*2+2,"Prior");
gprintf(WIDTH*7+2,HEIGHT*1+2,"Ready Processes");/*就緒隊列列表頭*/
gprintf(WIDTH*7+2,HEIGHT*2+2,"ProcID");
gprintf(WIDTH*8+2,HEIGHT*2+2,"Time");
gprintf(WIDTH*9+2,HEIGHT*2+2,"Prior");
}
int DrawData()/*繪制系統數據*/
{
int numRun=0, numSus=0, numRed=0;/*運行掛起和就緒的進程各有多少*/
PCB* now = ProcQueue;
int x=0, y=0;
while (now != NULL)
{
switch(now->Sts)
{
case RUN:
x = WIDTH*1;
y = HEIGHT*(3+(numRun++));
break;
case SUSPEND:
x = WIDTH*4;
y = HEIGHT*(3+(numSus++));
break;
case READY:
x = WIDTH*7;
y = HEIGHT*(3+(numRed++));
break;
}
if (now->Sts==RUN)/*該進程為正在運行的進程*/
{
putimage(x-WIDTH+1,y+1,black,COPY_PUT);
gprintf(x-WIDTH+2,y+2,"%d",numRun);
}
if (now->PID>=0)/*該進程不是後備進程*/
{
putimage(x+1,y+1,black,COPY_PUT);
gprintf(x+2,y+2,"%d",now->PID);
putimage(x+1+WIDTH,y+1,black,COPY_PUT);
gprintf(x+WIDTH+2,y+2,"%d",now->Time);
putimage(x+1+WIDTH*2,y+1,black,COPY_PUT);
gprintf(x+WIDTH*2+2,y+2,"%d",now->Prior);
}
else
{
putimage(x+1,y+1,black,COPY_PUT);
putimage(x+1+WIDTH,y+1,black,COPY_PUT);
putimage(x+1+WIDTH*2,y+1,black,COPY_PUT);
gprintf(x+2,y+2,"system idle process");
}
now = now->Next;
}
}
int DlgGetNum(char *buf,int l,int t,int r,int b,int gettime)
{
char ch;
int pos=0;
bar(l,t,r,b);
gprintf(l+10,t+5,"Add new Process");
if (gettime)
gprintf(l+10,t+20,"input the time:");
else
gprintf(l+10,t+20,"input the priority:");
while (1)
{
ch = getch();
if (ch == ENTER)/*如果輸入了回車鍵*/
{
if(pos!=0)/*如果位置不在第一位(回車鍵不準第一個輸入)*/
{
buf[pos]='\0';
break;
}
}
else if (ch>='0' && ch<='9')
{
buf[pos++]=ch;
buf[pos]='\0';
}
else if (ch == ESC)
{
return FALSE;
}
else/*其他按鍵均按BackSpace處理*/
{
--pos;
buf[pos]='\0';
}
if (pos<0)
{ pos=0; buf[pos]='\0';}
else if (pos>4)/*最多輸入4位數*/
{ pos=4; buf[pos]='\0';}
bar(l,t+35,r,t+47);
gprintf(l+50,t+35,buf);
}
return TRUE;
}
int NewProcDlg()
{
int l=200,t=150,r=380,b=200,pos=0,prior=0,time=0;
char buf[5],ch;
PCB *pcb;
void* bg = (void*)malloc(imagesize(l,t,r,b));
getimage(l,t,r,b,bg);
setfillstyle(1,2);
flushall();
/*******輸入優先順序**********/
if (!DlgGetNum(buf,l,t,r,b,FALSE))
goto exit;
prior = atoi(buf);
/*******輸入時間**********/
pos=0;
buf[pos]='\0';
if (!DlgGetNum(buf,l,t,r,b,TRUE))
goto exit;
time = atoi(buf);
InsertProc(prior, time);
exit:
putimage(l,t,bg,COPY_PUT);
free(bg);
return TRUE;
}
int gprintf( int xloc, int yloc, char *fmt, ... )/*圖形系統中的格式輸出*/
{
va_list argptr; /* Argument list pointer */
char str[140]; /* Buffer to build sting into */
int cnt; /* Result of SPRINTF for return */

va_start( argptr, format ); /* Initialize va_ functions */

cnt = vsprintf( str, fmt, argptr ); /* prints string to buffer */
outtextxy( xloc, yloc, str ); /* Send string in graphics mode */

va_end( argptr ); /* Close va_ functions */

return( cnt ); /* Return the conversion count */
}
/****************************************************************/

/*main函數*/
int main()
{
clock_t start=0, end=0;
char kb;
InitBatchs(3);/*初始化為3道系統*/
InitGraph();
while (1)
{
start = end = clock();
while (!kbhit())
{
start = clock();
if ((start-end)/18.2 >= 1)/*時間過了一秒*/
{
start = end = clock();
PassSeconds(1);
cleardevice();
DrawFrame();
DrawData();
}
}
kb = getch();
switch (kb)
{
case ESC:
closegraph();
return 0;
case 'w':
AddBatch();
UpdateBatchs();
cleardevice();
DrawFrame();
DrawData();
break;
case 's':
DeleteBatch();
UpdateBatchs();
cleardevice();
DrawFrame();
DrawData();
break;
case 'i':
NewProcDlg();
UpdateBatchs();
DrawFrame();
DrawData();
break;
}
}
return 0;
}

I. 急！！用優先順序隊列，按一位數，二位數，三位數重新排列數字，且數字相對位置不能改變。

如果不用優先順序隊列會很簡單，不過不知道是不是你們要求一定要用優先順序隊列，如果不是的話，你看看我的代碼吧：

	publicstaticvoidsort(Stringstr){
		String[]arr=str.split(",");
		
		for(inti=1;i<str.length();i++){
			for(intj=0;j<arr.length;j++){
				if(arr[j].length()==i)
					System.out.print(arr[j]+",");
			}
		}
	}

	publicstaticvoidmain(String[]args){
		//test
		Stringinput="3,12,888,564,15,9999,78";
		sort(input);//output:3,12,15,78,888,564,9999,
	}

J. java 優先順序隊列是怎麼實現的

你要的是這樣的效果么 public static void main(String[] args) { PriorityQueue pq = new PriorityQueue(); pq.add(5); pq.add(2); pq.add(3); pq.add(4); System.out.println("取出了"+pq.poll()+",隊列剩餘"+Arrays.toString(pq.toArray()));

閱讀全文

java優先順序隊列

與java優先順序隊列相關的閱讀推薦