カスタムリニアおよび非線形ストレージのキュー実装

通常のプログラミングでは,キューは多くの面で応用できる.生活の中で私达は同様に随所にその影を见ることができて、例えば私达は列に并んで、先に并んだ人は先にサービスを得て、后に入った人は后でサービスを受けます.これがキューです.はっきり言って、FIFO原則(First in First out、先進先出)です.キューの実装は、ストレージ構造によって異なり、通常は2つの方法でストレージされます.リニアストレージまたは非ラインストレージ.
1、リニアストレージ.配列などの長さ固定の記憶方式に基づいて実現される.ここではまずインタフェースを定義し、インタフェースに基づいて実現します.コードを見てください.

package simple;

interface queue {
    boolean isEmpty();

    void in(Object value);

    Object top();

    void out();

    boolean isFull();

    int getSize();
}

public class ArrayBase implements queue {
    private static final int MAXSIZE = 100;
    int front;
    int rear;
    int number;
    Object[] data;

    ArrayBase() {
        front = rear = -1;
        number = 0;
        data = new Object[MAXSIZE];
    }

    @Override
    public void in(Object value) {
        // TODO Auto-generated method stub
        if (this.isFull()) {
            System.out.println("Sorry, the queue is full!");
        } else {
            this.rear = (this.rear + 1) % MAXSIZE;
            number++;
            this.data[this.rear] = value;
        }
    }

    @Override
    public Object top() {
        // TODO Auto-generated method stub
        if (this.isEmpty()) {
            System.out.println("Sorry, the queue is empty!");
        }
        int p = (this.front + 1) % MAXSIZE;
        return data[p];
    }

    @Override
    public void out() {
        // TODO Auto-generated method stub
        if (this.isEmpty()) {
            System.out.println("Sorry, the queue is empty!");
        }
        this.front = (this.front - 1) % MAXSIZE;
        number--;

    }

    @Override
    public boolean isFull() {
        // TODO Auto-generated method stub
        if (this.rear == MAXSIZE - 1) {
            return true;
        }
        return false;
    }

    public boolean isEmpty() {
        if (number == 0) {
            return true;
        }
        return false;
    }

    @Override
    public int getSize() {
        // TODO Auto-generated method stub
        return this.number;
    }

}

次はテストクラスです.

package simple;

public class MyQueueTest {

    public static void main(String []args){
        ArrayBase myQueue=new ArrayBase();
        System.out.println(((ArrayBase) myQueue).isEmpty());
        myQueue.in(false);
        myQueue.in(1);
        myQueue.in('T');
        myQueue.in("Biao");
        System.out.println("Now there are "+myQueue.getSize()+" items!");
        System.out.println("Top Item is: "+ myQueue.top());
        myQueue.out();
        System.out.println("After the out operation,there are "
                            +myQueue.getSize()+" items in this queue!");
    }

}

テストの結果です

true
Now there are 4  items!
Top Item is: false
After the out operation,there are 3 items in this queue!

2、もちろん非線形のストレージ構造を用いてキューを実現することも可能であり、利点は「偽オーバーフロー」現象を回避し、空間に十分に利用できることである.コード実装は次のとおりです.

package simple;

interface queueListBase {
    boolean isEmpty();

    void in(Object value);

    Object top();

    Object out();

    int getSize();
}

class Node{
    Object data;
    Node next;
    Node(){
        data=null;
        next=null;
    }

}

public class ListBase implements queueListBase{

    int number;
    Node front;
    Node rear;

    public ListBase(){
        number=0;
        front=rear=null;
    }

    @Override
    public boolean isEmpty() {
        // TODO Auto-generated method stub
        if(this.front==this.rear){
            return true;
        }
        return false;
    }

    /* * (non-Javadoc)                    *         front   ，           NullPointerException   ！ * @see simple.queueListBase#in(java.lang.Object) */
    @Override
    public void in(Object value) {
        // TODO Auto-generated method stub
        if (rear == null && front == null) {  
            rear = new Node();
            rear.data=value;
            front = rear;  
        } else {  
            Node node = new Node();
            node.data=value;
            rear.next = node;  
            rear = node;
            number++;
        }  
    }

    @Override
    public Object top() {
        // TODO Auto-generated method stub
        Node temp=new Node();
        temp.data=this.front.data;
        return temp;
    }

    @Override
    public Object out() {
        // TODO Auto-generated method stub
        Object temp=null;
        if(this.isEmpty()){
            System.out.println("Sorry,the queue is Empty!");
            return false;
        }else{
            temp=this.front.data;
            this.front=this.front.next;
            if(front.next==null){
                this.rear=this.front;
            }
            number--;
        }
        return temp;
    }

    @Override
    public int getSize() {
        // TODO Auto-generated method stub
        return number;
    }

}

次は私のテストコードです.

package simple;

public class MyQueueTest {

    public static void main(String []args){
// ArrayBase myQueue=new ArrayBase();
        ListBase myQueue=new ListBase();
        System.out.println(((ListBase) myQueue).isEmpty());
        myQueue.in(false);
        myQueue.in(1);
        myQueue.in('T');
        myQueue.in("Biao");
        System.out.println(myQueue.out());
        System.out.println(myQueue.out());
        System.out.println(myQueue.out());
        System.out.println(myQueue.out());
        System.out.println("Now there are "+myQueue.getSize()+" items!");
        System.out.println("Top Item is: "+ myQueue.top());
        myQueue.out();
        System.out.println("After the out operation,there are "
                            +myQueue.getSize()+" items in this queue!");
    }

}

テストの結果は次のとおりです.

true
false
1
T
Sorry,the queue is Empty!
false
Now there are 0  items!
Top Item is: simple.Node@659e0bfd
Sorry,the queue is Empty!
After the out operation,there are 0 items in this queue!

結果分析:チェーンキューに値が格納されている場合、文字列タイプは正常に格納されていないことがわかります.しかし、これはキューが文字列タイプのデータを格納できないわけではないので、注意してください.そうでなければ、今後のソフトウェアのエラーを引き起こす可能性があります.次はもっと完全な非線形のキューの実現コードで、私が入隊して操作に失敗した後に修正されたブログでもあります.あなたと一緒に勉強して、一緒に進歩しましょう.非線形キューの実装