대기열을 구현하는 방법에는 몇 가지가 있습니까?
- coldplay.xixi원래의
- 2020-06-28 11:24:164755검색
큐를 구현하는 방법에는 세 가지가 있습니다. 1. 연결된 목록을 기반으로 큐를 구현합니다. 2. linkedList를 사용하여 큐를 구현합니다. 3. 두 개의 스택을 사용하여 큐를 구현합니다.
큐를 구현하는 방법에는 3가지가 있습니다. 구현 방법은 다음과 같습니다.
1. 연결된 목록을 기반으로 큐를 구현합니다.
먼저 노드 클래스를 큐에 노드 요소로 추가합니다
public class Node {//链表中的一个节点
Node next = null;
int data;
//构造函数，用于添加链表时候使用
public Node(int d) {
this.data = d;
};
} 새 항목 만들기 클래스로서, 대기열로서, 이 범주에서는 대기열의 등록 및 팀과 대기열의 길이 및 대기열의 길이가 전달된 데이터에 따라 비어 있습니다. enqueue 메소드에서는 큐가 비어 있는지 여부를 판단합니다(head==tail). enqueue된 노드는 head와 tail입니다. 큐가 비어 있지 않으면 꼬리 노드의 다음 포인터가 요소를 가리키고 꼬리 노드가 노드를 가리킵니다.
public void put(Integer data) {
Node newNode = new Node(data);//构造一个新节点
if(head == null && tail == null) {//队列为空
head = newNode;
tail = newNode;
}else {
tail.next = newNode;
tail = newNode;
}
}② Dequeue 작업:
큐가 비어 있으면 비어 있음을 반환합니다. 큐가 비어 있지 않으면 큐의 헤드 노드를 반환하고 헤드 노드의 다음 요소를 헤드 노드로 재사용합니다.
public Integer pop() {
if(this.isEmpty()) {
return null;
}
int data = head.data;
head = head.next;
return data;
}3 큐 비어 있음과 큐 길이를 판단하는 것은 매우 간단합니다. 추가 설명 없이 코드를 직접 붙여넣으세요.
public int size() {
int count = 0;
Node tmp = head;
while(tmp != null) {
count++;
tmp = tmp.next;
}
return count;
}4상세 코드 구현:
package com.wp.datastruct; /** * 利用链表来实现队列 * */ public class MyQueue2.{ Node head = null;//队列头 Node tail = null;//队列尾 /** * 入队操作： * 若该队列尾空，则入队节点既是头结点也是尾节点 * 若队列不为空，则先用tail节点的next指针指向该节点 * 然后将tail节点指向该节点 * */ public void put(Integer data) { Node newNode = new Node(data);//构造一个新节点 if(head == null && tail == null) {//队列为空 head = newNode; tail = newNode; }else { tail.next = newNode; tail = newNode; } } /** * 判断队列是否为空：当头结点等于尾节点的时候该队列就为空 * */ public boolean isEmpty() { return head == tail; } /** * 出队操作： * 若队列为空，则返回null * 否则，返回队列的头结点，并将head节点指向下一个 * */ public Integer pop() { if(this.isEmpty()) { return null; } int data = head.data; head = head.next; return data; } public int size() { int count = 0; Node tmp = head; while(tmp != null) { count++; tmp = tmp.next; } return count; } }
를 사용하여 큐를 구현합니다
이 방법은 Java에서 linkedList 컬렉션을 사용하여 큐를 구현하고, 메소드를 호출하여 큐의 진입 및 종료를 구현하는 것입니다. linkedList에서 빈 판단 및 기타 작업 linkedList먼저 대기열로 새 클래스를 만듭니다. 이 클래스에는 두 가지 속성이 포함되어 있습니다. 하나는 대기열의 길이를 계산하는 데 사용되며 다른 하나는 LinkedList 개체입니다.
우리 대기열.
private LinkedList<E> list = new LinkedList<>(); private int size = 0;//用于统计队列的长度
① 대기열 작업:
linkedList 컬렉션에 추가 및 삭제 작업이 구현되어 있어야 합니다. 여기서는 대기열 관련 작업을 구현하기 위한 메서드만 호출하면 됩니다. 이는 매우 간단하고 쉽습니다. 이해하다.
public synchronized void put(E data) {//保证线程安全，实现同步操作
list.add(data);
size++;
}② Dequeue 작업:
public synchronized E pop() {
size--;
return list.removeFirst();//从头取出
}3 세부 코드:
public class MyQueue2{ private LinkedList<E> list = new LinkedList<>(); private int size = 0;//用于统计队列的长度 public synchronized void put(E data) {//保证线程安全，实现同步操作 list.add(data); size++; } public synchronized E pop() { size--; return list.removeFirst();//从头取出 } public synchronized int size() { return size; } public boolean isEmpty() { return size == 0; } }
3. 두 개의 스택을 사용하여 대기열을 구현합니다.
두 개의 구현된 스택을 사용하여 대기열을 구현할 수도 있습니다(이 질문은 필기 테스트 중에 나올 수 있음). 구현 방법은 다음과 같습니다.
두 개의 스택 s1과 s2를 만듭니다. 대기열에 합류하면 스택에 s1로만 푸시됩니다.
큐 제거에는 두 가지 경우가 있습니다. 1. s2가 비어 있지 않으면 스택의 최상위 요소가 큐 제거 요소로 팝됩니다.于 2. S2가 비어 있을 때 먼저 S1의 요소를 S2로 pop up하고, 그 다음 S2의 최상위 요소를 팀의 요소로 pop up합니다.
① 팀 합류:
public synchronized void put(E data) {//使用同步处理，保证线程安全
s1.push(data);
}② 팀 탈퇴:
public synchronized E pop() {
if(!s2.isEmpty()) {
return s2.pop();
}else {
s2.push(s1.pop());
return s2.pop();
}
}3. 세부 코드 구현:
package com.wp.datastruct;
import java.util.Stack;
/**
* 利用两个栈来模拟队列操作
* 入队操作就只是想栈s1中添加，
* 出栈操作分为两部分：
* 1.当s2中不为空的时候，就直接弹出s2中的栈顶数据
* 2.当s2中为空的时候，就先把s1中的数据全部弹出到s2中然后将栈顶数据出栈
*
* */
public class MyQueue3<E> {
Stack<E> s1 = new Stack<>();
Stack<E> s2 = new Stack<>();
public synchronized void put(E data) {//使用同步处理，保证线程安全
s1.push(data);
}
public synchronized E pop() {
if(!s2.isEmpty()) {
return s2.pop();
}else {
s2.push(s1.pop());
return s2.pop();
}
}
public synchronized boolean isEmpty() {
return s1.isEmpty() && s2.empty();
}
}추천 튜토리얼: "
php 비디오 튜토리얼"
위 내용은 대기열을 구현하는 방법에는 몇 가지가 있습니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!