Java描述数据结构之双向队列（Double-ends Queues，Deque）-蒲公英云

Java描述数据结构之双向队列（Double-ends Queues，Deque）

矫情吗；* 2022-05-25 13:28 523阅读 0赞

双向队列是一种前后两端都可输入或取出数据的有序表，在双向队列中，我们仍然使用两个指针，分别指向加入及取回端，只是加入和取回数据时，各指针所扮演的角色不再是固定的加入或取回，而且两边的指针都向队列中央移动。

下面是实现双向队列的示例程序，可以在两端加入和取出数据：

// 程序名称： DequeTest.java                               
// 程序目的：输入限制性双向队列
// ===================================================
import java.io.*;
class QueueNode                 // 队列节点类
{
    int data;                    // 节点数据
    QueueNode next;              // 指向下一个节点
   //构造函数
    public QueueNode(int data){
        this.data=data;
        next=null;
    }
}
class Linked_List_Queue { //队列类
    public QueueNode front; //队列的前端指针
    public QueueNode rear;  //队列的尾端指针
//构造函数
    public Linked_List_Queue(){
        front=null;
        rear=null;
    }
    //方法enqueue:队列数据的存入
    public boolean enqueue(int action,int value) {
        QueueNode node= new QueueNode(value); //建立节点
        if(action==1){
            if(rear==null){
                front=node;
                rear=node;
            }else{
                node.next=front;
                front=node;
            }
            return true;
        }else if(action==2){
            if(rear==null){
                front=node;
                rear=node;
            }else{
                rear.next=node;
                rear=node;
            }
            return true;
        }else{
            return false;
        }
    }
    //方法dequeue:队列数据的取出
    public int dequeue(int action) {
        int value;
        QueueNode tempNode,startNode;
       //从前端取出数据
       if (!(front==null) && action==1) {
           if(front==rear){
               value=front.data; //将队列数据从前端取出
               front=null;
               rear=null;
           }else{
               value=front.data;
               front=front.next;
           }
           return value; 
       }else if (!(rear==null) && action==2){  //从尾端取出数据
           if(front==rear){
               value=rear.data;
               front=null;
               rear=null;
           }else{
               value=rear.data;
               tempNode=front;
               while (tempNode.next!=rear){
                   //tempNode=startNode.next;
                   tempNode=tempNode.next;
               }
               rear=tempNode;
           }
           return value;
       }else{
           return -1;
       }
    }
}
public class DequeTest {
// 主程序
    public static void main(String args[]) throws IOException {
        Linked_List_Queue queue =new Linked_List_Queue(); //建立队列对象
    int temp;
    System.out.println("以链表来实现双向队列");
    System.out.println("====================================");
    System.out.println("在双向队列前端加入第1个数据，此数据值为1");
    queue.enqueue(1,4);
    System.out.println("在双向队列前端加入第2个数据，此数据值为3");
    queue.enqueue(1,3);
    System.out.println("在双向队列前端加入第3个数据，此数据值为5");
    queue.enqueue(2,5);
    System.out.println("在双向队列前端加入第4个数据，此数据值为7");
    queue.enqueue(1,7);
    System.out.println("在双向队列前端加入第5个数据，此数据值为9");
    queue.enqueue(2,9);
    System.out.println("====================================");
    temp=queue.dequeue(1);
    System.out.println("从双向队列前端依序取出的元素数据值为："+temp);
    temp=queue.dequeue(2);
    System.out.println("从双向队列尾端依序取出的元素数据值为："+temp);
    temp=queue.dequeue(1);
    System.out.println("从双向队列前端依序取出的元素数据值为："+temp);
    temp=queue.dequeue(2);
    System.out.println("从双向队列尾端依序取出的元素数据值为："+temp);
    temp=queue.dequeue(1);
    System.out.println("从双向队列前端依序取出的元素数据值为："+temp);
    System.out.println();
    }
}