필기 데이터 구조 - 동적 배열 기반 순환 대기 열
동적 배열 을 기반 으로 하 는 대기 열 에서 우 리 는 팀 의 첫 번 째 요 소 를 옮 길 때 시간 복잡 도 는 O (n) 인 것 을 발견 했다. 이 문 제 를 해결 하기 위해 우 리 는 순환 대기 열 을 이 끌 었 다.
실현 원리: 더 블 포인터, 하나의 포인터 가 팀 의 첫 번 째 요 소 를 가리 키 는 것 을 유지 합 니 다. 팀 의 첫 번 째 요 소 를 옮 길 때 배열 을 바탕 으로 이 루어 진 대기 열 에 있 는 요 소 는 모두 한 위 치 를 앞으로 이동 하지 않 고 다음 요 소 를 가리 키 기만 하면 됩 니 다.
2. 동적 배열 을 바탕 으로 하 는 순환 대기 행렬 과 복잡 도 분석 (동적 배열 을 바탕 으로 하 는 일반 대기 행렬 과 비교) 을 수 동 으로 실현 합 니 다.
package com.tc.javabase.datastructure.array.queue;
import com.tc.javabase.datastructure.queue.Queue;
/**
* @Classname LoopQueue
* @Description
*
*
* front = tail , size == 0
*
* :
* :O(1)
* :O(1)
* :O(1)
*
* : , 10w
* :9s
* :0.06
*
*
*
* @Date 2020/7/17 09:39
* @Created by zhangtianci
*/
public class LoopQueue implements Queue {
private E[] data;
private int size;
private int front; //
private int tail; //
/**
* 8
*/
public LoopQueue() {
this.data = (E[])new Object[8];
size = 0;
front = 0;
tail = 0;
}
/**
* @param capacity
*/
public LoopQueue(int capacity){
this.data = (E[])new Object[capacity];
size = 0;
front = 0;
tail = 0;
}
@Override
public int getSize() {
return size;
}
@Override
public boolean isEmpty() {
return size == 0 ? true : false;
}
/**
*
*
* :O(1)
* , n+1 , 2n+1 , 2 ,
* O(1)
* @param e
*/
@Override
public void enqueue(E e) {
//
//1。
if (size == data.length){
resize(data.length * 2);
}
data[tail] = e;
tail = (tail + 1) % data.length;
size++;
}
/**
* /
* @param capacity
*/
private void resize(int capacity){
E[] newdata = (E[])new Object[capacity];
for (int i = 0;i < size;i++){
newdata[i] = data[(front + i) % data.length];
}
data = newdata;
front = 0;
tail = size;
}
/**
*
* :O(1)
*
* @return
*/
@Override
public E dequeue() {
//
//
if (isEmpty()){
throw new IllegalArgumentException(" !");
}
E e = data[front];
data[front] = null;
front = (front + 1) % data.length;
size--;
//
if (size == data.length / 4 && data.length / 2 != 0){
resize(data.length / 2);
}
return e;
}
/**
*
*
* :O(1)
* @return
*/
@Override
public E getFront() {
return data[front];
}
@Override
public String toString() {
StringBuilder res = new StringBuilder();
res.append(String.format("Queue: size = %d , capacity = %d
", size,data.length));
res.append("front = " + front + " [");
for (int i = 0;i < size;i++){
res.append(data[(front + i) % data.length]);
if ((front + i + 1) % data.length != tail){
res.append(", ");
}
}
res.append("] " + "tail=" + tail);
return res.toString();
}
public static void main(String[] args) {
LoopQueue queue = new LoopQueue<>();
for(int i = 0 ; i < 100 ; i ++){
queue.enqueue(i);
System.out.println(queue);
if(i % 3 == 2){
queue.dequeue();
System.out.println(queue);
}
}
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.