자바 링크 응용-링크 기반 대기 열 상세 설명(꼬리 포인터 조작)

본 고의 실례 는 자바 가 체인 테이블 을 바탕 으로 대열 을 실현 하 는 것 을 서술 하 였 다.여러분 께 참고 하도록 공유 하 겠 습 니 다.구체 적 으로 는 다음 과 같 습 니 다.
스 택 의 실현 을 시작 하기 전에 우 리 는 링크 가 머리 에서 만 진행 되 는 증가,삭제,찾기 작업 을 살 펴 보 자.시간 복잡 도 는 모두 O(1)이다.


1.링크 개선 분석
대기 열 이라는 데이터 구조 에 대해 서 는 선형 구조의 한 끝 에 요 소 를 삽입 하고 다른 한 끝 에 요 소 를 삭제 해 야 합 니 다.따라서 이때 링크 를 바탕 으로 대기 열 을 실현 하면 한 끝 의 시간 복잡 도 는 O(n)이다.따라서 우 리 는 이전에 실 현 된 링크 구 조 를 사용 할 수 없 기 때문에 우 리 는 우리 의 링크 를 개선 해 야 한다.사고방식 은 다음 과 같다.
1.링크 의 머리 부분 에서 요 소 를 삭제 하고 증가 하 는 시간 복잡 도가 O(1)인 사 고 를 참고 하여 우 리 는 링크 의 끝 에 Node 형 변수 tail 을 설치 하여 링크 의 끝 이 어디 에 있 는 지 기록 합 니 다.이때 head 단 과 tail 단 에 요 소 를 추가 하 는 것 은 모두 간단 합 니 다.head 단 에서 원 소 를 삭제 하 는 것 도 간단 하지만 tail 단 에서 요 소 를 삭제 할 때시간 복잡 도가 O(1)인 상황 에서 진행 할 수 없습니다.즉,tail 에서 요 소 를 삭제 할 때 쉽 지 않 습 니 다.

2.머리 head 에서 만 요소(팀 첫 번 째)를 삭제 하고 꼬리 tail 끝 에 요소(팀 꼬리)를 추가 합 니 다.

3.링크 를 바탕 으로 대기 열 을 실현 할 때 링크 중간 요 소 를 조작 하지 않 기 때문에 이때 우리 가 개선 한 링크 에서 가상 헤 더 를 사용 하지 않 기 때문에 가상 헤 더 노드 가 없 는 상황 에서 링크 가 비어 있 을 수 있 습 니 다.
2.링크 개선 코드
앞에서 말 했 듯 이 이 소절 을 쓰기 전에 우 리 는 정적 배열 을 바탕 으로 하 는 대기 열 을 실현 했다보기 로 이동여기 서 우 리 는 링크 기반 대기 열 을 실현 합 니 다.
정적 배열 을 기반 으로 하 는 대기 열 을 실현 할 때,우 리 는 패 키 지 를 새로 만 들 었 습 니 다.이때 우 리 는 이 패키지 아래 에 LinkedListQueue 류 를 새로 만 들 었 습 니 다.Queue 인 터 페 이 스 를 실현 하 는 데 사 용 됩 니 다.디 렉 터 리 구 조 는 다음 과 같 습 니 다.

1.Queue 인터페이스 코드

package Queue;

public interface Queue<E> {
  //         
  int getSize();

  //         
  boolean isEmpty();

  //   
  void enqueue(E e);

  //   
  public E dequeue();

  //      
  public E getFront();
}

2.LinkedListQueue 클래스

package Queue;

public class LinkedListQueue<E> implements Queue<E> {

  // Node           
  private class Node<E> {
    public E e;
    public Node next;

    //         
    public Node(E e, Node next) {
      this.e = e;
      this.next = next;
    }

    //         
    public Node(E e) {
      this.e = e;
      this.next = null;
    }

    //      
    public Node() {
      this(null, null);
    }

    @Override
    public String toString() {
      return e.toString();
    }
  }

  private Node<E> head, tail;

  private int size;


  //     
  public LinkedListQueue() {
    head = null;
    tail = null;
    size = 0;
  }

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

  //       
  @Override
  public boolean isEmpty() {
    return size == 0;
  }

  //        
  @Override
  public void enqueue(E e) {
    if (tail == null) {
      tail = new Node(e);
      head = tail;
    } else {
      tail.next = new Node(e);
      tail = tail.next;
    }
    size++;
  }

  //        
  @Override
  public E dequeue() {
    if (isEmpty()) {
      throw new IllegalArgumentException("    ");
    }

    Node<E> retNode = head;
    head = head.next;
    retNode.next = null;
    if (head == null) {//          
      tail = null;
    }

    size--;
    return retNode.e;
  }

  //      
  @Override
  public E getFront() {
    if (isEmpty()) {
      throw new IllegalArgumentException("    ");
    }
    return head.e;
  }


  //      ，  object toString()  
  @Override
  public String toString() {
    StringBuilder res = new StringBuilder();
    res.append("Queue: front ");
    Node<E> cur = head;
    while (cur != null) {
      res.append(cur + "->");
      cur = cur.next;
    }
    res.append("NULL tail");
    return res.toString();
  }


}

3.테스트 에 편리 하도록 링크 드 ListQueue 클래스 에 main 함 수 를 추가 합 니 다.

 //    
  public static void main(String[] args) {
    LinkedListQueue<Integer> queue = new LinkedListQueue<Integer>();
    for (int i = 0; i < 10; i++) {
      queue.enqueue(i);
      System.out.println(queue);

      if (i % 3 == 2) {//   3        
        queue.dequeue();
        System.out.println(queue);
      }

    }

  }

4.결 과 는?

결과 분석:팀 에 들 어 갈 때마다 세 개의 요소 가 대열 에 하나씩 나온다.
이 소절 에 대해 괜 찮 고 괜찮다 고 생각 하 시 면 추천 해 주세요~감사합니다!!
이 절의 소스 코드https://github.com/FelixBin/dataStructure/blob/master/src/Queue/LinkedListQueue.java
자바 알고리즘 과 관련 된 내용 에 관심 이 있 는 독자 들 은 본 사이트 의 주 제 를 볼 수 있 습 니 다.
본 고 에서 말 한 것 이 여러분 의 자바 프로 그래 밍 에 도움 이 되 기 를 바 랍 니 다.