行列步队有3种完成形式,辨别为:一、基于链表来完成行列步队;二、应用linkedList来完成行列步队;三、应用两个栈来完成一个行列步队。
行列步队有3种完成形式,完成形式为:
一、基于链表来完成行列步队:
起首增加一个节点类,作为行列步队中的节点元素
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; } }
二、应用linkedList
来完成行列步队
该办法是应用java中的linkedList荟萃来完成一个行列步队,经过挪用linkedList中的办法来完成行列步队的入队出队,判空等操作
起首new一个类来作为咱们的行列步队,该类中蕴含两个属性,一个是size:用来统计该行列步队的长度,另外一个是LinkedList工具,
代表咱们的行列步队。
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; } }
三、应用两个栈来完成一个行列步队。
也能够应用两个完成好的栈来完成一个行列步队(这个成绩可能面试口试的时分回被问到)。
完成办法是:
创立两个栈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视频教程》
以上就是行列步队有几种完成形式?的具体内容,更多请存眷资源魔其它相干文章!
标签: php教程 队列 实现方式 php故障解决 php使用问题
抱歉,评论功能暂时关闭!