>  기사  >  백엔드 개발  >  대기열을 구현하는 방법에는 몇 가지가 있습니까?

대기열을 구현하는 방법에는 몇 가지가 있습니까?

coldplay.xixi
coldplay.xixi원래의
2020-06-28 11:24:164724검색

큐를 구현하는 방법에는 세 가지가 있습니다. 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 MyQueue {
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;
}
 
}

2.

를 사용하여 큐를 구현합니다

이 방법은 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 중국어 웹사이트의 기타 관련 기사를 참조하세요!

성명:
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.