How many ways are there to implement queues?-PHP Problem-php.cn

How many ways are there to implement queues?

coldplay.xixi

Release： 2023-03-01 17:22:01

Original

4745 people have browsed it

There are three ways to implement queues, namely: 1. Implement the queue based on a linked list; 2. Use linkedList to implement the queue; 3. Use two stacks to implement a queue.

How many ways are there to implement queues?

There are 3 ways to implement queues. The implementation methods are:

1. Implementation based on linked list Queue:

First add a node class as the node element in the queue

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

Copy after login

Then create a new class as our queue, and implement the queue entry and exit in this class The length and judgment of the team and the queue of the queue are empty. Add a node Node, and determine whether the queue is empty in the enqueue method. If the queue is empty (head==tail), then the node added to the queue is both the head and the tail of the queue. If the queue is not empty, point the next pointer of the tail node to the element, and then point the tail node to the node.

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

Copy after login

② Dequeue operation:

If the queue is empty, return empty. If the queue is not empty, return the head node of the queue, and then re-use the next element of the head node as the head node

public Integer pop() {
if(this.isEmpty()) {
return null;
}
int data = head.data;
head = head.next;
return data;
}

Copy after login

③ It is very simple to judge the empty queue and the length of the queue, just paste the code directly, Say no more.

public int size() {
int count = 0;
Node tmp = head;
while(tmp != null) {
count++;
tmp = tmp.next;
}
return count;
}

Copy after login

④Detailed code implementation:

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

Copy after login

2. Use

linkedList

to implement the queue

This method is used in java Use the linkedList collection to implement a queue, and call the methods in the linkedList to implement queue entry and exit, empty judgment and other operations. First create a new class as our queue, which contains two attributes. , one is size: used to count the length of the queue, and the other is a LinkedList object,

represents our queue.

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

Copy after login

① Queue operation:

It should be that the add and delete operations have been implemented in the linkedList collection. Here we only need to simply call the method to implement the queue-related operations, which is very Simple and easy to understand.

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

Copy after login

② Dequeue operation:

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

Copy after login

③ Detailed code:

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

Copy after login

3. Use two stacks to implement a queue.

You can also use two implemented stacks to implement a queue (this question may be asked during the written interview). The implementation method is:

Create two stacks s1 and s2. When joining the queue, it is only pushed onto the stack into s1.

There are two cases of dequeuing: 1. When s2 is not empty, the top element of the stack is popped as the dequeuing element.

2. When S2 is equal to empty, first pop the elements in S1 into S2, and then pop up the top element from the S2 as the element of the team.

① Joining the team:

public synchronized void put(E data) {//使用同步处理，保证线程安全
s1.push(data);
}

Copy after login

② Leaving the team:

public synchronized E pop() {
if(!s2.isEmpty()) {
return s2.pop();
}else {
s2.push(s1.pop());
return s2.pop();
}
}

Copy after login

③. Detailed code implementation:

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

Copy after login