• 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏搜讯息吧

队列有几种实现方式?_php教程,队列,实现方式

PHP ytg3114 3个月前 (06-27) 145次浏览 0个评论 扫描二维码

队列具有什么特点?_php教程

队列具有的特点是:1、只允许在表的前端【front】进行删除操作,而在表的后端【rear】进行插入操作;2、进行插入操作的端称为队尾,进行删除操作的端称为队头;3、队列中没有元素时,称为空队列。

队列有3种实现方式,实现方式为:1、基于链表来实现队列;2、使用linkedList来实现队列;3、使用两个栈来实现一个队列。

队列有几种实现方式?_php教程,队列,实现方式

队列有3种实现方式,实现方式为:

1、基于链表来实现队列:

首先添加一个节点类,作为队列中的节点元素

public class Node {//链表中的一个节点
Node next = null;
int data;
//构造函数,用于添加链表时候使用
public Node(int d) {
this.data = d;
};
}

再新建一个类作为我们的队列,在该类中实现队列的入队和出队以及求队列的长度和判断队列是否为空等方法

①入队操作:

首先通过函数参数传入要入队的数据,根据传入的参数,新增一个节点Node,在入队方法中判断该队列是否为空,若该队列为空(head==tail),则该入队的节点既是队头也是队尾。若队列不为空,则将尾节点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 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;
}

④详细代码实现:

package com.wp.datastruct;
 
/**
 * 利用链表来实现队列
 * */
public class MyQueue<E> {
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、使用linkedList来实现队列

该方法是使用java中的linkedList集合来实现一个队列,通过调用linkedList中的方法来实现队列的入队出队,判空等操作

首先new一个类来作为我们的队列,该类中包含两个属性,一个是size:用来统计该队列的长度,另一个是LinkedList对象,

代表我们的队列。

如何使用PHP_CodeSniffer检查代码规范(详解)_php教程

PHP_CodeSniffer是一个代码风格检测工具。它包含两类脚本,phpcs和phpcbf(GitHub地址)。phpcs 脚本对PHP、JS、CSS文件定义了一系列的代码规范;phpcbf 脚本能自动修正代码格式上不符合规范的部分。

private LinkedList<E> list = new LinkedList<>();
private int size = 0;//用于统计队列的长度

①入队操作:

应为linkedList集合中已经实现好了添加删除操作,在这里我们只需要简单的调用方法就可以实现队列的相关操作了,非常简单而且容易理解。

public synchronized void put(E data) {//保证线程安全,实现同步操作
list.add(data);
size++;
}

②出队操作:

public synchronized E pop() {
size--;
return list.removeFirst();//从头取出
}

③详细代码:

public class MyQueue2<E> {
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中,再从s2中弹出栈顶元素作为出队元素。

①入队:

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();
}
}

③.详细代码实现:

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视频教程》

以上就是队列有几种实现方式?的详细内容,更多请关注ki4网其它相关文章!

php如何使用PHPAnalysis提取关键字中文分词_php教程

需求:做SEO的keywords时,需要从标题或者正文里提取关键字,下载后解压放到extend目录下(以tp5为例,其他目录也行)。


搜讯息 , 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权
转载请注明原文链接:队列有几种实现方式?_php教程,队列,实现方式
喜欢 (0)
[1353713598@qq.com]
分享 (0)
表情 贴图 加粗 删除线 居中 斜体 签到

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址