快捷導(dǎo)航

Java利用跳躍表解決雙重隊(duì)列問(wèn)題詳解

更新時(shí)間：2022年12月28日 11:02:26 作者：chengqiuming

這篇文章主要為大家詳細(xì)介紹了Java如何利用跳躍表來(lái)解決雙重隊(duì)列的問(wèn)題。本文通過(guò)一個(gè)簡(jiǎn)單的例題進(jìn)行了講解，感興趣的小伙伴可以了解一下

一問(wèn)題描述

銀行的每個(gè)客戶(hù)都有一個(gè)正整數(shù)標(biāo)識(shí) K，到銀行請(qǐng)求服務(wù)時(shí)將收到一個(gè)正整數(shù)的優(yōu)先級(jí) P 。銀行經(jīng)理提議打破傳統(tǒng)，在某些時(shí)候調(diào)用優(yōu)先級(jí)最低的客戶(hù)，而不是優(yōu)先級(jí)最高的客戶(hù)。系統(tǒng)將收到以下類(lèi)型的請(qǐng)求：

① 0，系統(tǒng)需要停止服務(wù)。

② 1 K P，將客戶(hù) K 及優(yōu)先級(jí) P 添加到等待列表中。

③ 2，為優(yōu)先級(jí)最高的客戶(hù)提供服務(wù)，并將其從等待名單中刪除。

④ 3，為優(yōu)先級(jí)最低的客戶(hù)提供服務(wù)，并將其從等待名單中刪除。

二輸入

輸入的每一行都包含一個(gè)請(qǐng)求，只有最后一行包含停止請(qǐng)求（代碼0）。假設(shè)有請(qǐng)求在列表中包含新客戶(hù)（代碼1），在同一客戶(hù)的列表中沒(méi)有其他請(qǐng)求或有相同的優(yōu)先級(jí)，標(biāo)識(shí)符 K 總是小于10^6 ，優(yōu)先級(jí) P 總是小于10^7 。一個(gè)客戶(hù)可以多次到銀行請(qǐng)求服務(wù)，但是每次都獲得不同的優(yōu)先級(jí)。

三輸出

對(duì)代碼為 2 或 3 的每個(gè)請(qǐng)求都單行輸出所服務(wù)客戶(hù)的標(biāo)識(shí)。若請(qǐng)求在等待列表為空時(shí)到達(dá)，則輸出 0。

四輸入和輸出樣例

1 輸入樣例

2
1 20 14
1 30 3
2
1 10 99
3
2
2
0

2 輸出樣例

0
20
30
10
0

五分析和設(shè)計(jì)

本問(wèn)題包括插入、刪除優(yōu)先級(jí)最高元素和刪除優(yōu)先級(jí)最低元素等3種操作，可以使用跳躍表解決。

六代碼

package com.platform.modules.alg.alglib.poj3481;
 
import java.util.Random;
 
public class Poj3481D {
    private int INF = 0x7fffffff;
    private int MAX_LEVEL = 16;
    public String output = "";
 
    public String cal(String input) {
        Init();
        int op, num, val;
        String[] line = input.split("\n");
        int count = 0;
        while (true) {
            String commad[] = line[count++].split(" ");
            op = Integer.parseInt(commad[0]);
            if (op == 1) {
                num = Integer.parseInt(commad[1]);
                val = Integer.parseInt(commad[2]);
                Insert(num, val);
            } else if (op == 0) {
                return output;
            } else if (op == 2)
                Delete(true);
            else
                Delete(false);
        }
    }
 
    class Node {
        int num, val;
        Node forward[] = new Node[MAX_LEVEL];
    }
 
    public Poj3481D() {
        for (int i = 0; i < updata.length; i++) {
            updata[i] = new Node();
        }
    }
 
    Node head;
    Node updata[] = new Node[MAX_LEVEL];
 
    int level, max_k, min_k;
 
    void Init() {
        level = 0;
        max_k = -INF;
        min_k = INF;
        head = new Node();
        for (int i = 0; i < MAX_LEVEL; i++)
            head.forward[i] = null;
        head.val = -INF;
    }
 
    // 按規(guī)則選擇數(shù)據(jù)應(yīng)該在哪層插入
    int RandomLevel() {
        int lay = 0;
        while (new Random().nextInt(100) % 2 == 0 && lay < MAX_LEVEL - 1)
            lay++;
        return lay;
    }
 
    // 查找最接近val的元素
    Node Find(int val) {
        Node p = head;
        for (int i = level; i >= 0; i--) {
            while (p.forward[i] != null && p.forward[i].val < val)
                p = p.forward[i];
            updata[i] = p; // 記錄搜索過(guò)程中各級(jí)走過(guò)的最大節(jié)點(diǎn)位置
        }
        return p;
    }
 
    void Insert(int num, int val) {
        if (val > max_k) max_k = val;
        if (val < min_k) min_k = val;
        Node s;
        int lay = RandomLevel();
        if (lay > level) // 要插入的層 > 現(xiàn)有層數(shù)
            level = lay;
        Find(val); //查詢(xún)
        s = new Node(); // 創(chuàng)建一個(gè)新節(jié)點(diǎn)
        s.num = num;
        s.val = val;
        for (int i = 0; i < MAX_LEVEL; i++)
            s.forward[i] = null;
        for (int i = 0; i <= lay; i++) { // 插入操作
            s.forward[i] = updata[i].forward[i];
            updata[i].forward[i] = s;
        }
    }
 
    // flag=false 表示刪除最小值，true 表示刪除最大值
    void Delete(boolean flag) {
        int d;
        if (flag) d = max_k;
        else d = min_k;
        if (d == -INF || d == INF) { // 說(shuō)明還沒(méi)有插入元素
            output += "0\n";
            return;
        }
        Node p = Find(d);
        if (p.forward[0] != null && p.forward[0].val == d) {
            output += String.format("%d\n", p.forward[0].num);
 
            if (p.val == -INF && p.forward[0].forward[0] == null) // 刪除唯一節(jié)點(diǎn)
            {
                max_k = -INF;
                min_k = INF;
            } else {
                if (flag) max_k = p.val;
                else min_k = p.forward[0].forward[0].val;
            }
            for (int i = level; i >= 0; i--) { // 刪除操作
                if (updata[i].forward[i] != null && updata[i].forward[i].val == d)
                    updata[i].forward[i] = updata[i].forward[i].forward[i];
            }
        }
    }
}