데이터 구조 - 3 - 대기 열
38130 단어 데이터 구조
1. 개념
대기 열 은
FIFO
(first - in - first - out) 의 집합 데이터 구 조 를 따 르 는 것 입 니 다. 즉, 대기 열 에 가장 먼저 놓 인 요소 이자 가장 먼저 얻 은 것 입 니 다.그것 의 밑바닥 은 수조 로 이 루어 질 수도 있 고 체인 시계 로 이 루어 질 수도 있다.이 는 두 개의 지침 이 있 는데 각각 머리 노드 와 꼬리 노드 를 가리 키 고 요 소 를 추가 할 때 꼬리 노드 를 뒤로 이동 하 며 요 소 를 제거 할 때 머리 노드 를 뒤로 이동 합 니 다.
2. 상용 방법
1) 배열 대기 열
class ArrayQueue<T> {
private final int length;
private Object[] array;
private int head; //
private int tail; //
public ArrayQueue(int length) {
this.length = length;
this.array = new Object[this.length];
this.head = -1;
this.tail = -1;
}
public void put(T element) {
if (isFull()) {
return;
}
this.tail++;
array[tail] = element;
}
public T take() {
if (isEmpty()) {
return null;
}
this.head++;
@SuppressWarnings("unchecked")
T element = (T)array[head];
if (head == tail) {
head = -1;
tail = -1;
}
return element;
}
@SuppressWarnings("unchecked")
public T peek() {
if (isEmpty()) {
return null;
}
return (T)array[head + 1];
}
public int size() {
return tail - head;
}
@Override
public String toString() {
if (isEmpty()) {
return "[]";
}
StringBuilder sBuilder = new StringBuilder("[");
for (int i = head + 1, size = i + size(); i < size; i++) {
sBuilder.append(array[i]);
if (i != size - 1) {
sBuilder.append(", ");
} else {
sBuilder.append("]");
}
}
return sBuilder.toString();
}
public boolean isFull() {
return tail == length - 1;
}
public boolean isEmpty() {
return -1 == head && head == tail;
}
}
2) 링크 대기 열
class LinkedQueue<T> {
private final int length;
private Node<T> head; //
private Node<T> tail; //
private int size;
public LinkedQueue(int length) {
this.length = length;
this.head = null;
this.tail = null;
this.size = 0;
}
public void put(T element) {
if (isFull()) {
return;
}
Node<T> add = new Node<T>(element);
if (null == head) {
this.head = add;
}
if (null != tail) {
tail.next = add;
}
this.tail = add;
this.size++;
}
public T take() {
if (isEmpty()) {
return null;
}
T element = head.element;
if (head == tail) { // ,
this.tail = null;
}
this.head = head.next;
this.size--;
return element;
}
public T peek() {
if (isEmpty()) {
return null;
}
return head.element;
}
public int size() {
return size;
}
@Override
public String toString() {
if (isEmpty()) {
return "[]";
}
StringBuilder sBuilder = new StringBuilder("[");
Node<T> node = this.head;
while (true) {
sBuilder.append(node.element);
if (null == node.next) {
break;
}
sBuilder.append(", ");
node = node.next;
}
sBuilder.append("]");
return sBuilder.toString();
}
public boolean isFull() {
return size == length;
}
public boolean isEmpty() {
return 0 == size;
}
private static class Node<T> {
private final T element;
private Node<T> next;
private Node(T element) {
this.element = element;
}
@Override
public String toString() {
return (null != element) ? element.toString() : "null";
}
}
}
3) 순환 대기 열
class CircleQueue<T> {
private final int length;
private Object[] array;
private int head; //
private int tail; //
public CircleQueue(int length) {
this.length = length + 1; // , 。
this.array = new Object[this.length];
this.head = 0;
this.tail = 0;
}
public void put(T element) {
if (isFull()) {
return;
}
array[tail] = element;
tail = (tail + 1) % length;
}
public T take() {
if (isEmpty()) {
return null;
}
@SuppressWarnings("unchecked")
T element = (T)array[head];
head = (head + 1) % length;
return element;
}
@SuppressWarnings("unchecked")
public T peek() {
if (isEmpty()) {
return null;
}
return (T)array[head];
}
public int size() {
return (tail + length - head) % length;
}
public boolean isFull() {
return (tail + 1) % length == head;
}
public boolean isEmpty() {
return head == tail;
}
@Override
public String toString() {
if (isEmpty()) {
return "[]";
}
StringBuilder sBuilder = new StringBuilder("[");
for (int i = head, size = i + size(); i < size; i++) {
sBuilder.append(array[i % length]);
if (i != size - 1) {
sBuilder.append(',').append(' ');
}
}
sBuilder.append(']');
return sBuilder.toString();
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.