(3) 파 트 2 대기 열

1. 대기 열 큐
대열 도 일종 의 선형 구조 이다
배열 에 비해 대기 열 에 대응 하 는 동작 은 배열 의 부분 집합 입 니 다.
한 끝 (팀 끝) 에서 만 요 소 를 추가 할 수 있 고 다른 한 끝 (팀 첫 번 째) 에서 만 요 소 를 추출 할 수 있 습 니 다.  
(줄 서기)
대기 열 은 선진 적 인 데이터 구조 (선착순) FIFO (First In First Out) 입 니 다.
2. 배열 대기 열의 실현 (동적 배열 기반)
인터페이스 Queue 인터페이스 설정 5 가지 방법
void enqueue(E e)   대열 에 들어가다  O (1) 균등 하 게 분담
E dequeue () 가 팀 을 나 갑 니 다.  O (n) (팀 을 나 간 후 후속 요 소 를 한 단위 앞으로 옮 기기 때문에 팀 을 나 가 는 작업 에 있어 성능 이 비교적 떨어진다)
E getFront()  팀 의 첫 번 째 요소 보기 (팀 의 첫 번 째 요소 에 만 관심 이 있 음) O (1)
int getSize()  대기 열 에 있 는 요소 개수   O(1)
boolean isEmpty () 대기 열 이 비어 있 는 지 여부   O(1)

public interface Queue {
    int getSize();
    boolean isEmpty();
    void enqueue(E e);
    E dequeue();
    E getFront();
}

ArrayQueue 인터페이스 구현

public class ArrayQueue implements Queue 

1. 기본 적 인 구조 방법

    private Array array;
    public ArrayQueue(int capacity){
        array = new Array<>(capacity);
    }

    public ArrayQueue(){
        array = new Array<>();
    }

    @Override
    public int getSize() {
        return array.getSize();
    }

    @Override
    public boolean isEmpty() {
        return array.isEmpty();
    }

    public int getCapacity(){
        return array.getCapacity();
    }

2. 입대

 @Override
    public void enqueue(E e) {
        array.addLast(e);
    }

3. 출전

@Override
    public E dequeue() {
        return array.removeFirst();
    }

4. 첫 번 째 원소 보기

   @Override
    public E getFront() {
        return array.getFirst();
    }

5. toString () 방법 을 재 작성 하여 출력 을 더욱 가 독성 있 게 합 니 다.

  @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        res.append("Queue:");
        res.append("front [");
        for( int i = 0 ; i < array.getSize() ; i ++){
            res.append(array.get(i));
            if(i != array.getSize() - 1)
                res.append(", ");
        }
        res.append("]");
        return res.toString();
    }

배열 대기 열의 문제: 출 대 시간 복잡 도 는 O (n) 등급 (바 텀 실현 과정: 팀 의 첫 번 째 요 소 를 꺼 내 고 후속 요 소 는 순서대로 한 자 리 를 옮 겨 야 합 니 다)
3. 순환 대기 열
초기 에 front = tail = 0, front 는 대열 의 첫 번 째 요 소 를 가리 키 고 tail 은 팀 의 마지막 요소 의 다음 요 소 를 가리킨다.대기 열 에 요소 가 없 는 경우 에 만 front 는 tail 과 같 습 니 다.
Eg:
1. 기본 상황
입대 작업 (tail 유지, 즉 tail +, front 움 직 이지 않 음)
a. 입단, front = 0 tail + 즉 tail = 1
front [a]
b. 입단, front = 0 tail + 즉 tail = 2
front [a, b]
c. 입단, front = 0 tail + 즉 tail = 3
front [a, b, c]
파티 작업 (front 유지 보수, 즉 front +, tail 움 직 이지 않 음)
a 출대, tail = 3 front + 즉 front = 1
front [b, c]
b 팀 나 가기, tail = 3 front + 즉 front = 2
front[c]
c 출대, tail = 3 front + 즉 front = 3
배열 이 비어 있 습 니 다. 이때 front = tail
2. 순환 (배열 은 하나의 고리 로 본다)
capacity = 8, 0, 1, 2, 3, 4, 5 위치 에 모두 요소 front = 0, tail = 6 이 있다 고 가정 합 니 다.
먼저 두 번 의 출전 조작 을 진행 합 니 다. 23, 45 위치 에 요소 가 있 습 니 다.  front=2，tail=6
두 번 의 입 대 를 진행 할 때 23, 4, 5, 6, 7 위치 에 요소 가 있 습 니 다. 이때 size = capacity = 8, 즉 대열 의 공간 을 가득 채 웠 지만 팀 의 첫 번 째 앞부분 에는 팀 작업 을 한 후에 비 워 진 2 개 단위 의 공간 이 있 습 니 다.
다시 입 대 를 할 때 순환 을 하면 이 요 소 는 0 위치 에 있 는 요 소 를 추가 합 니 다. 이때 front = 2, tail = 1, 이때 0, 2, 3, 4, 5, 6 위치 에 요소 가 있 고 1 위 치 는 요소 가 없습니다.
만약 에 다시 입대 작업 을 한다 면 front = tail = 2 는 위의 front = = tail 과 빈 정의 로 충돌 하기 때문에 다시 입대 작업 을 하려 면 용량 을 늘 려 야 한다. 1 위치 에 원소 가 없다. 즉, capacity 에서 의식 적 으로 공간 을 낭비 하 는 것 이다.
따라서 당 (tail + 1)% capacity = front 는 대기 열 이 가득 차 서 확장 이 필요 하지만 실제 capacity 는 공간 에 요소 가 없 음 을 낭비 합 니 다.
그래서 결론 은 다음 과 같다.
front = = tail 시 대기 열 이 비어 있 습 니 다.
(tail + 1)% capacity = = front 시 대기 열 이 가득 차 서 확장 이 필요 하지만 실제 capacity 는 공간 을 낭비 합 니 다.
4. 순환 대기 열의 실현
LoopQueue
void enqueue(E e)    O(1)  균등 하 게 분담 하 다
E dequeue()      O (1) 균등 하 게 분담
E getFront()       O(1)
int getSize()       O(1)
boolean isEmpty()       O(1)
LoopQueue 클래스 를 만 들 고 Queue 인 터 페 이 스 를 실현 합 니 다.

public class LoopQueue implements Queue

1. 기본 적 인 구조 방법
주의해 야 할 몇 가지:
a. 배열 을 초기 화 하 는 것 외 에 front 와 tail 을 첫 번 째 요소 와 마지막 요소 의 다음 방향 으로 초기 화 해 야 합 니 다. size 는 실제 front 와 size 에서 얻 을 수 있 습 니 다.
b. 사용자 가 입력 capacity 를 초기 화 할 때 구조 함수 에서 capacity 를 + 1 로 조작 해 야 합 니 다. 실제 capacity 에서 공간 을 낭비 하기 때 문 입 니 다.
c. 마찬가지 로 getCapacity () 방법 은 데이터. length 에서 - 1 작업 을 해 야 합 니 다.
d. 대기 열 이 비어 있 는 지 판단 하 는 방법 에 대한 판단 기준 은 front = tail 이다.

 private E[] data;
    private int front, tail;
    private int size;

    public LoopQueue(int capacity){
        data = (E[])new Object[capacity + 1];  //          +1
        front = 0;
        tail = 0;
        size = 0;
    }

    public LoopQueue(){
        this(10);
    }

    public int getCapavity(){
        return data.length - 1;  //          ，      -1
    }

    @Override
    public boolean isEmpty() {
        return front == tail;
    }

    @Override
    public int getSize() {
        return size;
    }

2. resize () 방법
입 대 를 진행 하고 팀 을 나 갈 때 순환 대기 열의 capacity 를 바 꾸 기 위해 필요 한 resize () 작업 이 필요 할 때 가 있 습 니 다.
주의:
a. new Data 를 초기 화 할 때 용량 은 new Capacity + 1 입 니 다.
b. 두 가지 스 트 리밍 방식
c.front =0；
  tail = size；

    private void resize(int newCapacity){
        E[] newData = (E[])new Object[newCapacity + 1];
        for(int i = 0 ; i < size ; i ++){
            newData[i] = data[ (i + front) % data.length ];
        }
 //       for(int i = front ; i != tail ; i = (i+1) % data.length){
 //           newData[i] = data[i];
 //       }
        data = newData;
        front = 0;
        tail = size;
    }

3. 입대
주의:
a. 우선 대기 열 이 가득 차 있 는 지 판단 하고 가득 차 면 확장 합 니 다. 확장 시 data. length 를 사용 할 수 없습니다. data. length 는 getCapacity () 방법 보다 1 이 많 기 때 문 입 니 다.
b. tail = (tail + 1)% data. length 는 tail + 가 아 닙 니 다.
c. size 유지, size + 진행

  @Override
    public void enqueue(E e) {
        if((tail + 1) % data.length == front) {
            resize(2 * getCapacity());    //    data.length，   data.length getCapacity 1
        }

        data[tail] = e;
        tail = (tail + 1) % data.length;
        size ++;
    }

4. 출전
주의:
a. 우선 대기 열 이 비어 있 는 지 여 부 를 판단 합 니 다.
b. 먼저 data [front] 를 res 에 게 꺼 내 고 data [front] = null 을 사용 하여 공간 을 낭비 하지 않도록 합 니 다.
c. front front = (front + 1)% data. length 를 이동 합 니 다. front + 가 아 닙 니 다.
d. 유지 보수 size, 진행 size --
e. 판단 축소

@Override   
public E dequeue() {
        if(isEmpty()){
            throw new IllegalArgumentException("Cannot dequeue from an empty queue");
        }
        E ret = data[front];
        data[front] = null;
        front = (front + 1) % data.length;
        size --;
        if(size == getCapacity() / 4 && getCapacity() / 2 != 0){
            resize(getCapacity() / 2);
        }
        return  ret;

    }

5. 첫 번 째 원소 보기

   @Override
    public E getFront() {
        if(isEmpty()){
            throw new IllegalArgumentException("Queue is empty");
        }
        return data[front];
    }

6. toString () 방법 을 다시 써 서 출력 을 더욱 읽 을 수 있 게 합 니 다.
주의:
a. 출력 capacity 는 data. length 가 아 닌 getCapacity () 입 니 다.
b. 두 가지 스 트 리밍 방식

    public String toString() {
        StringBuilder res = new StringBuilder();
        res.append(String.format("Queue: size = %d , capacity = %d%n", size, getCapacity())); //  getCapacity()   data.length
        res.append("front [");
        for(int i = front ; i != tail; i = (i + 1) % data.length){
            res.append(data[i]);
            if( (i + 1)% data.length != tail)
                res.append(", ");
        }
//        for(int i = 0 ; i < size ; i ++){
//            res.append(data[( i + front ) % data.length]);
//            if((i + front) % data.length != tail - 1 )
//               res.append(", ");
//       }
        res.append("] tail");
        return res.toString();
    }

요약:
순환 대기 열 이 복잡 한 것 은 주로 세 가지 점 에서 복잡 하 다.
a. getCapacity () 방법 은 data. length - 1 입 니 다.
b. 대기 열 을 링 으로 보고 순환, front 와 tail 의 변화, 특히 tail 의 변화
c. 방법 에서 전체 대기 열 을 옮 겨 다 니 는 데 순환 요소 의 영향 을 고려 해 야 한다.
그러나 팀 의 복잡 도 는 O (1) 로 순환 대열 이 팀 을 나 갈 때 좋 은 성능 을 가지 게 한다.
순환 대기 열의 논리 와 코드 에 대해 서 는 특히 부분 을 잘 이해 해 야 한다.
 
다음으로 전송:https://www.cnblogs.com/HarSong13/p/10666719.html