필기 데이터 구조 - 링크 기반 대기 열
구조 특성: 선진 선 출
실현 원리: 쌍 지침 을 사용 하여 하나의 지침 이 팀 의 끝 을 가리 키 고 꼬리 부분 에 조작 시간 복잡 도 를 추가 하면 O (1) 로 변 합 니 다.
2. 핸드 메 이 드 는 링크 를 바탕 으로 하 는 대기 행렬 과 복잡 도 분석 (동적 배열 을 바탕 으로 하 는 순환 대기 행렬 과 비교)
package com.tc.javabase.datastructure.linklist.queue;
import com.tc.javabase.datastructure.queue.Queue;
/**
* @Classname LinkedListQueue
* @Description
*
*
*
* :
* * :O(1)
* * :O(1)
* * :O(1)
*
*
* @Date 2020/7/18 18:42
* @Created by zhangtianci
*/
public class LinkedListQueue implements Queue {
private class Node{
public E e;
public Node next;
public Node(E e, Node next) {
this.e = e;
this.next = next;
}
public Node(E e){
this(e,null);
}
public Node(){
this(null,null);
}
}
private Node head,tail;
private int size;
@Override
public int getSize() {
return size;
}
@Override
public boolean isEmpty() {
return size == 0 ? true : false;
}
/**
*
*
* :O(1)
* @param e
*/
@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++;
}
/**
*
* :O(1)
* @return
*/
@Override
public E dequeue() {
if (isEmpty()){
throw new IllegalArgumentException(" !");
}
Node retn = head;
head = head.next;
retn.next = null;
if (head == null){
tail = null;
}
size--;
return retn.e;
}
/**
*
* :O(1)
* @return
*/
@Override
public E getFront() {
if (isEmpty()){
throw new IllegalArgumentException(" !");
}
return head.e;
}
@Override
public String toString() {
StringBuilder builder = new StringBuilder();
builder.append("Queue head");
Node curr = head;
while (curr != null){
builder.append(curr.e);
builder.append("->");
curr = curr.next;
}
builder.append("NULL tail");
return builder.toString();
}
public static void main(String[] args) {
LinkedListQueue queue = new LinkedListQueue<>();
for(int i = 0 ; i < 10 ; 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에 따라 라이센스가 부여됩니다.