构建队列--使用数组方式

118 阅读 0 评论 78 点赞

我是靠谱客的博主踏实烧鹅，这篇文章主要介绍构建队列--使用数组方式，现在分享给大家，希望可以做个参考。

使用数组方式创建一个队列，该队列有：

- enqueue() 该方法在队列末尾添加元素 O(1)

- dequeue() 从队列开头移出一项 O(1)

- peek()得到队列第一项，但不删除 O(1)

- isEmpty()

- isFull

准备工作

创建两个指针用来标记下标位置，一个为front，一个为rear，当添加元素时，指针rear后移一位，由于要提高内存效率，于是产生了循环队列，rear并不是一味的自增，而是通过 (rear+1)%数组长度的关系循环索引。

复制代码

1
2
3
4
5
6
7
8
   int[] item;
   int count;
   int rear;
   int front;
   public ArrayQueue(int length){
      item = new int[length];
  }

enqueue

复制代码

1
2
3
4
5
6
7
8
9
public void enqueue(int input){
    if(isFull())
        throw new IllegalStateException();
    //每添加一个元素，指针rear向后移动
    item[rear] = input;
    rear = (rear+1)%item.length;
    count++;
}

dequeue

复制代码

1
2
3
4
5
6
7
8
9
10
11
public int dequeue (){
      if(isEmpty())
          throw new IllegalStateException();
      var it = item[front];
       item[front]=0;
       front = (front+1)%item.length;
       count--;
      return it;

  }

peek

复制代码

1
2
3
4
5
6
7
8
9
10
11
//得到队列中第一项元素，但不删除元素
public int peek(){
    if(isEmpty())
        throw new IllegalStateException();
    rear = (rear+1)%item.length;
    var pe =  item[rear-1];

    count--;
    return pe;
}

isEmpty

复制代码

1
2
3
4
 public boolean isEmpty(){
        return count==0;
    }

isFull

复制代码

1
2
3
4
public  boolean isFull(){
        return item.length==count;
    }

toString

复制代码

1
2
3
4
5
6
@Override
    public  String toString(){
        return Arrays.toString(item);
    }
}

show

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
ArrayQueue aq = new ArrayQueue(5);
        aq.enqueue(10);
        aq.enqueue(20);
        aq.enqueue(30);
        aq.enqueue(40);
        aq.dequeue();
        aq.dequeue();
        aq.enqueue(50);
        aq.enqueue(60);
        aq.enqueue(70);
        aq.dequeue();
        System.out.println(aq);