대열 의 실현 원리 와 분석
github 주소
대열 은 일종 의 선형 구조 이다
배열 에 비해 대기 열 에 대응 하 는 동작 은 배열 의 부분 집합 입 니 다.
한 끝 (팀 끝) 에서 만 요 소 를 추가 할 수 있 고 다른 한 끝 (팀 첫 번 째) 에서 만 요 소 를 추출 할 수 있 습 니 다.
대기 열 은 먼저 나 온 데이터 구조 로 First In First Out (FIFO)
활용 단어 참조
운영 체제 에서 임 무 를 수행 하 는 줄 서기 등;
시간 복잡 도 분석
Array Queue 배열 대기 열
배열 대기 열 VS 순환 대기 열
배열 대기 열:
순환 대기 열:
고정 배열 순환 대기 열 구현 방식 2:
이루어지다
Queue
public class ArrayQueue implements Queue {
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();
}
@Override
public void enqueue(E e){
array.addLast(e);
}
@Override
public E dequeue(){
return array.removeFirst();
}
@Override
public E getFront(){
return array.getFirst();
}
@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("] tail");
return res.toString();
}
public static void main(String[] args){
ArrayQueue queue = new ArrayQueue<>();
for(int i = 0 ; i < 10 ; i ++){
queue.enqueue(i);
System.out.println(queue);
if(i % 3 == 2){
queue.dequeue();
System.out.println(queue);
}
}
}
}
순환 대기 열
public class LoopQueue<E> implements Queue<E> {
private E[] data;
private int front, tail;
private int size; // ， ， ：
// LoopQueue size， ？
// ：）
public LoopQueue(int capacity){
data = (E[])new Object[capacity + 1];
front = 0;
tail = 0;
size = 0;
}
public LoopQueue(){
this(10);
}
public int getCapacity(){
return data.length - 1;
}
@Override
public boolean isEmpty(){
return front == tail;
}
@Override
public int getSize(){
return size;
}
@Override
public void enqueue(E e){
if((tail + 1) % data.length == front)
resize(getCapacity() * 2);
data[tail] = e;
tail = (tail + 1) % data.length;
size ++;
}
@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;
}
@Override
public E getFront(){
if(isEmpty())
throw new IllegalArgumentException("Queue is empty.");
return data[front];
}
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];
data = newData;
front = 0;
tail = size;
}
@Override
public String toString(){
StringBuilder res = new StringBuilder();
res.append(String.format("Queue: size = %d , capacity = %d
", size, getCapacity()));
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(", ");
}
res.append("] tail");
return res.toString();
}
public static void main(String[] args){
LoopQueue<Integer> queue = new LoopQueue<>();
for(int i = 0 ; i < 10 ; i ++){
queue.enqueue(i);
System.out.println(queue);
if(i % 3 == 2){
queue.dequeue();
System.out.println(queue);
}
}
}
}
배열 대기 열 VS 순환 대기 열
import java.util.Random;
public class Main {
// q opCount enqueueu dequeue ， ：
private static double testQueue(Queue<Integer> q, int opCount){
long startTime = System.nanoTime();
Random random = new Random();
for(int i = 0 ; i < opCount ; i ++)
q.enqueue(random.nextInt(Integer.MAX_VALUE));
for(int i = 0 ; i < opCount ; i ++)
q.dequeue();
long endTime = System.nanoTime();
return (endTime - startTime) / 1000000000.0;
}
public static void main(String[] args) {
int opCount = 100000;
ArrayQueue<Integer> arrayQueue = new ArrayQueue<>();
double time1 = testQueue(arrayQueue, opCount);
System.out.println("ArrayQueue, time: " + time1 + " s");
LoopQueue<Integer> loopQueue = new LoopQueue<>();
double time2 = testQueue(loopQueue, opCount);
System.out.println("LoopQueue, time: " + time2 + " s");
}
}
Leetcode 102. Binary Tree Level Order Traversal
import java.util.ArrayList;
import java.util.List;
import javafx.util.Pair;
/// Leetcode 102. Binary Tree Level Order Traversal
/// https://leetcode.com/problems/binary-tree-level-order-traversal/description/
///
///
/// 。
/// Leetcode LoopQueue。
/// ， 。
/// ， 。
/// ， ：）
class Solution {
/// Definition for a binary tree node.
private class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
private interface Queue<E> {
int getSize();
boolean isEmpty();
void enqueue(E e);
E dequeue();
E getFront();
}
private class LoopQueue<E> implements Queue<E> {
private E[] data;
private int front, tail;
private int size; // ， ， ：
// LoopQueue size， ？
// ：）
public LoopQueue(int capacity){
data = (E[])new Object[capacity + 1];
front = 0;
tail = 0;
size = 0;
}
public LoopQueue(){
this(10);
}
public int getCapacity(){
return data.length - 1;
}
@Override
public boolean isEmpty(){
return front == tail;
}
@Override
public int getSize(){
return size;
}
@Override
public void enqueue(E e){
if((tail + 1) % data.length == front)
resize(getCapacity() * 2);
data[tail] = e;
tail = (tail + 1) % data.length;
size ++;
}
@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;
}
@Override
public E getFront(){
if(isEmpty())
throw new IllegalArgumentException("Queue is empty.");
return data[front];
}
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];
data = newData;
front = 0;
tail = size;
}
@Override
public String toString(){
StringBuilder res = new StringBuilder();
res.append(String.format("Queue: size = %d , capacity = %d
", size, getCapacity()));
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(", ");
}
res.append("] tail");
return res.toString();
}
}
public List<List<Integer>> levelOrder(TreeNode root) {
ArrayList<List<Integer>> res = new ArrayList<List<Integer>>();
if(root == null)
return res;
// LinkedList
LoopQueue<Pair<TreeNode, Integer>> queue = new LoopQueue<Pair<TreeNode, Integer>>();
queue.enqueue(new Pair<TreeNode, Integer>(root, 0));
while(!queue.isEmpty()){
Pair<TreeNode, Integer> front = queue.dequeue();
TreeNode node = front.getKey();
int level = front.getValue();
if(level == res.size())
res.add(new ArrayList<Integer>());
assert level < res.size();
res.get(level).add(node.val);
if(node.left != null)
queue.enqueue(new Pair<TreeNode, Integer>(node.left, level + 1));
if(node.right != null)
queue.enqueue(new Pair<TreeNode, Integer>(node.right, level + 1));
}
return res;
}
}
레 퍼 런 스
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 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에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
