数据结构与算法_03队列

数据结构与算法_03队列

• 队列
• • 0、章节重点整理
  • 1、认识队列
  • 2、队列的应用

队列

0、章节重点整理

• 队列和堆栈都是有序表，抽象型数据类型，所有的加入删除都在不同的两端，符合FIFO特性
• 何为多重队列？定义及目的
  双向队列就是一种二重队列。只是队列的首端可在队列的左右两端。多重队列的原则是只要遵循数据的插入在rear 端，删除在front 端的原则，并将多重堆栈的T(i) 改成rear(i)、B(i) 改成front（i）即可。多重队列也可以改成多重环形队列。主要目的是让数组的有效使用率提高，因为数组的大小必须事先声明。
• 何为优先队列
  是一种不必遵守队列特性FIFO 的有序表，其中每一个元素都赋予了优先权，加入元素时可任意加入。但是拥有最高优先权的数据优先输出。

1、认识队列

1.1、 队列的工作运算

• 先进先出
• 两种基本操作，加入和删除，使用front 和rear 两个指针来分别指向队列的前端和尾端

1.2、队列的数组实现

//默认front 从-1开始，数组的索引是0开始。
    public static int front = -1,rear = -1,max = 20;
    public static int val;
    public static char ch;
    public static int queue[] = new int[max];//创建容量20的数组
    public static void main(String args[]) throws IOException {
        String strM;
        int M=0;
        BufferedReader keyin = new BufferedReader(new InputStreamReader(System.in));
        while(rear < max-1 && M != 3)
        {
            System.out.print("[1]存入一个数值[2]取出一个数值[3]结束: ");
            strM=keyin.readLine();
            M=Integer.parseInt(strM);
            switch(M)
            {
                case 1:
                    System.out.print("\n[请输入数值]: ");
                    strM=keyin.readLine();
                    val=Integer.parseInt(strM);
                    rear++;
                    queue[rear]=val;
                    break;
                case 2:
                    if(rear>front)
                    {
                        front++;
                        System.out.print("\n[取出数值为]: ["+queue[front]+"]"+"\n");
                        queue[front]=0;
                    }
                    else
                    {
                        System.out.print("\n[队列已经空了]\n");
                        break;
                    }
                    break;
                default:
                    System.out.print("\n");
                    break;
            }
        }
        if(rear == max-1) System.out.print("队列已经满了]\n");
        System.out.print("\n[目前队列中的数据]:");
        if (front >= rear) {
            System.out.print("没有\n");
            System.out.print("[队列已经空了]\n");
        }
        else {
            while (rear > front) {
                front++;
                System.out.print("["+queue[front]+"]");
            }
            System.out.print("\n");
        }
    }

1.3、队列的链表实现

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 value) {
        QueueNode node= new QueueNode(value); //建立节点
        //检查是否为空队列
        if (rear==null)
            front=node; //新建立的节点成为第一个节点
        else
            rear.next=node; //将节点加入到队列的尾端
        rear=node; //将队列的尾端指针指向新加入的节点
        return true;
    }

    //方法dequeue:队列数据的取出
    public int dequeue() {
        int value;
        //检查队列是否为空队列
        if (!(front==null)) {
            if(front==rear) rear=null;
            value=front.data; //将队列数据取出
            front=front.next; //将队列的前端指针指向下一个
            return value;
        }
        else return -1;
    }
} //队列类声明结束

public class  Test02{
    // 主程序
    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);
        System.out.println("在队列前端加入第2个数据，此数据值为3");
        queue.enqueue(3);
        System.out.println("在队列前端加入第3个数据，此数据值为5");
        queue.enqueue(5);
        System.out.println("在队列前端加入第4个数据，此数据值为7");
        queue.enqueue(7);
        System.out.println("在队列前端加入第5个数据，此数据值为9");
        queue.enqueue(9);
        System.out.println("====================================");
        while (true) {
            if (!(queue.front==null)) {
                temp=queue.dequeue();
                System.out.println("从队列前端依序取出的元素数据值为："+temp);
            }
            else
                break;
        }
        System.out.println();
    }
}

2、队列的应用

• 图形遍历的先广后深搜索法BFS，就是利用队列
• 计算机的模拟；模拟过程由于各种事件的输入时间不一定，利用队列反映真实情况
• CPU工作调度利用队列处理，可以达到先到先做的要求

2.1、环形队列

• 是一种环形结构的队列，是Q(0:n-1)的一维数组，同时Q(0) 也是Q(n-1)的下一个元素
• 指针front 永远以逆时针方向指向队列中第一个元素的前一个位置，rear 则指向队列当前的最后位置。一开始二者都设置为-1，表示空队列，当front = rear则为空队列。

public static int front = -1,rear = -1,val;
    public static int queue[] = new int[5];
    public static void main(String args[]) throws IOException

    {
        String strM;
        BufferedReader keyin = new BufferedReader(new InputStreamReader(System.in));
        while(rear < 5 && val != -1)
        {
            System.out.print("请输入一个值以存入队列，要取出值请输入0。(结束输入-1)：");
            strM = keyin.readLine();
            val = Integer.parseInt(strM);
            if(val == 0)
            {
                if(front==rear)
                {
                    System.out.print("[队列已经空了]\n");
                    break;
                }
                front++;
                if (front == 5)
                    front = 0;
                System.out.print("取出队列值["+queue[front]+"]\n");
                queue[front] = 0;
            }
            else if(val != -1 && rear < 5)
            {
                if(rear+1 == front||rear == 4&&front <= 0)
                {
                    System.out.print("[队列已经满了]\n");
                    break;
                }
                rear++;
                if(rear == 5)
                    rear = 0;
                queue[rear] = val;
            }
        }
        System.out.print("\n队列剩余数据：\n");
        if (front == rear)
            System.out.print("队列已空!!\n");
        else
        {
            while(front != rear)
            {
                front++;
                if (front == 5)
                    front = 0;
                System.out.print("["+queue[front]+"]");
                queue[front] = 0;
            }
        }
        System.out.print("\n");

    }

2.2、双向队列

class QueueNode {              // 队列节点类
    int data;                    // 节点数据
    QueueNode next;              // 指向下一个节点

    //构造函数
    public QueueNode(int data) {
        this.data = data;
        next = null;
    }
}

public class Linked_List_Queue { //队列类
    public QueueNode front; //队列的前端指针
    public QueueNode rear;  //队列的尾端指针

    //构造函数
    public Linked_List_Queue() {
        front = null;
        rear = null;
    }

    //方法enqueue:队列数据的存入
    public boolean enqueue(int value) {
        QueueNode node = new QueueNode(value); //建立节点
        //检查是否为空队列
        if (rear == null)
            front = node; //新建立的节点成为第一个节点
        else
            rear.next = node; //将节点加入到队列的尾端
        rear = node; //将队列的尾端指针指向新加入的节点
        return true;
    }

    //方法dequeue:队列数据的取出
    public int dequeue(int action) {
        int value;
        QueueNode tempNode, startNode;
        //从前端取出数据
        if (!(front == null) && action == 1) {
            if (front == rear) rear = null;
            value = front.data; //将队列数据从前端取出
            front = front.next; //将队列的前端指针指向下一个
            return value;
        }
        //从尾端取出数据
        else if (!(rear == null) && action == 2) {
            startNode = front;  //先记下前端的指针值
            value = rear.data;  //取出目前尾端的数据
            //找寻最尾端节点的前一个节点
            tempNode = front;
            while (front.next != rear && front.next != null) {
                front = front.next;
                tempNode = front;
            }
            front = startNode;  //记录从尾端取出数据后的队列前端指针
            rear = tempNode;    //记录从尾端取出数据后的队列尾端指针
            //下一行程序是指当队列中仅剩下最后节点时,取出数据后便将front及rear指向null
            if ((front.next == null) || (rear.next == null)) {
                front = null;
                rear = null;
            }
            return value;
        } else return -1;
    }
} //队列类声明结束

public class DoublyQueue {
    // 主程序
    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);
        System.out.println("在双向队列前端加入第2个数据，此数据值为3");
        queue.enqueue(3);
        System.out.println("在双向队列前端加入第3个数据，此数据值为5");
        queue.enqueue(5);
        System.out.println("在双向队列前端加入第4个数据，此数据值为7");
        queue.enqueue(7);
        System.out.println("在双向队列前端加入第5个数据，此数据值为9");
        queue.enqueue(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();
    }
}