【数据结构与算法】-- 5. 如何实现一个队列（顺序队列和链式队列）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
package com.anomalous.array;

/**
 * 基于数组实现的队列
 *
 * @author 天赋吉运-杨晓慧
 * @create 2019-04-27 15:27
 */
public class ArrayQueue {

    //定义数组，数组大小，两个指针（头和尾）
    private String items[];     // 队列
    private int n;          // 队列内元素数量
    private int head;       // 队列内头指针位置
    private int tail;       // 队列内尾指针位置

    /**
     * 构造一个基于数组实现的队列
     * @param n 容量
     */
    public ArrayQueue(int n){
        //定义长度为n的数组
        this.items=new String[n];

        this.n=n;
        // 数组中头指针和尾指针
        this.head=0;
        this.tail=0;
    }

    /**
     * 入队操作
     * @param item 入队元素
     * @return 是否入队成功
     */
    public boolean inqueue(String item){

        // 判断队列是否满了，如果队列已满不能再进行入队操作
        if (this.tail==n) {
           if (head==0) {
               // tail=n && head=0表示整个队列都已经满了，前后都没有空位置了
               return false;
            }
            // 只有tail=0表示队尾已经满了，但队首还有空位置
            // 需要数据搬移，将后面的数据往前移动，为队列腾出位置，然后新入队的数据才能放入队尾
            for (int i = head; i < tail; i++) {
                //从队首开始，依次往前移动head位
                 this.items[i-head]= this.items[i];
            }

            // 数据搬移完之后需要更新head和tail指针的位置
            // head指向0位，tail往前移动head个位置；
            head=0;
            tail-=head;
        }

        // 放在队列的最后一位
        this.items[tail]=item;
        // 头指针不变，尾指针的位置后移一位
        ++tail;
        return true;
    }

    /**
     * 出队操作
     * @return 出队元素
     */
    public String outqueue(){
        //判断对内是否有元素
        if (this.head==this.tail) {
            // 队首指针与队尾指针在同一位置表示队列为空
            return null;
        }
        // 取出队首元素放入临时变量
        String temp=items[head];

        // 从head指针部分出队，head后移一位
        ++head;
        return temp;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
/**
 * 基于链表实现的队列
 *
 * @author 天赋吉运-杨晓慧
 * @create 2019-04-30 9:39
 */
public class LInkedListQueue {

    //定义队列的队首和队尾（队首出队，队尾入队）
    private Node head;
    private Node tail;

    /**
     * 入队操作
     * @param value  待入队元素
     */
   public void inQueue(int value){
       // 判断队列是否为空
       if (this.tail==null) {
           // 队列为空时
           Node node =new Node(value,null);
           // 当前节点既是队首也是队尾
           this.head = node;
           this.tail = node;
       } else {
           // 队列不为空，新节点入队从队尾入
           this.tail.next=new Node(value,null);
           // 尾指针后移一位
           this.tail=this.tail.next;
       }
   }

    /**
     * 出队操作
     * @return 返回队首节点data
     */
   public Integer outQueue(){
       // 队列为空时
       if (head == null) return null;

       // 出队从队首出
       Integer value=this.head.data;
       // 队首指针后移一位
       this.head=this.head.next;
       if (this.head==null) {
           // 只有一个节点时候,出队后队列为空
           this.tail =null;
       }
       return value;

   }

    /**
     * 定义链表结构
     */
    private static class Node {
        private int data;
        private Node next;

        public Node(int data, Node next) {
            this.data = data;
            this.next = next;
        }

        public Integer getData() {
            return data;
        }
    }
}