英文:
How to add to the beginning of a queue in java
问题
我正在制作一个带有实例方法setNext、getNext的节点的简单队列实现。我编写的类具有字段Node First和Node Last。我的enqueue方法必须有3种情况
(1) 添加到列表末尾（正常队列实现）
this.back.setNext(要添加的节点);
this.back = 要添加的节点;
(2) 添加到空列表
this.front = this.back = 要添加的节点;
(3) 添加到列表前面（从而将所有其他元素都向后移动）
对我来说，这似乎非常简单，但是我在弄清楚如何使所有的下一个值匹配并且不覆盖任何节点方面遇到了很大困难。请告诉我一个能够做到这一点的算法。谢谢！
更新：我尝试过的一种实现方法是使用一个数组：
Node[] x = new Node[this.totalNodes+1];
Node current = this.front;
int i = 0;
while(current != null) {
x[i] = current;
current = current.getNext();
i++;
}
int j = 0;
Node current2 = this.front;
this.front = 要添加的节点
while(j < x.length-1) {
current2.setNext(x[j+1]);
current2 = current2.getNext();
j++;
}
英文:
I am making a simple queue implementation with nodes that have instance methods setNext, getNext. The class I am writing them has fields Node First, and Node Last. My enqueue method must have 3 cases
(1) Add to end of list (normal queue implementation)
this.back.setNext(node to add);
this.back = (node to add);
(2) Add to empty list
this.front = this.back = (node to add);
(3) Add to front of list (and thus move all other elements back)
It seems really simple to me but I am having a tough time sorting out how to get all of the next values to match and not overwrite any nodes. Please let me know of an algorithm that could do this. Thanks!
Update: one implementation I have tried is using an array:
Node[] x = new Node[this.totalNodes+1];
Node current = this.front;
int i = 0;
while(current != null) {
x[i] = current;
current = current.getNext();
i++;
}
int j = 0;
Node current2 = this.front;
this.front = (node to add)
while(j < x.length-1) {
current2.setNext(x[j+1]);
current2 = current2.getNext();
j++;
}
答案1
得分: 0
以下是您要求的代码的翻译部分：
也许这就是你想要的
public class MyDS {
Node head = null;
Node next = null;
class Node {
String data;
Node link = null;
Node(String s) {
data = s;
}
}
public void add(Node n) {
if (head == null) {
head = n;
n.link = null;
} else {
if (next == null) {
next = n;
head.link = next;
} else {
next.link = n;
next = n;
}
}
}
public void addTop(Node n) {
if (head == null) {
head = n;
n.link = null;
} else {
Node oldHead = head;
head = n;
n.link = oldHead;
}
}
public String print() {
String str = "";
Node startN = head;
while (startN.link != null) {
str += startN.data + "_";
startN = startN.link;
}
if (startN.data != null) str += startN.data + "_End!";
return str;
}
public static void main(String args[]) {
MyDS myDS = new MyDS();
myDS.add(myDS.new Node("a"));
myDS.add(myDS.new Node("b"));
myDS.add(myDS.new Node("c"));
myDS.addTop(myDS.new Node("d"));
myDS.add(myDS.new Node("e"));
myDS.addTop(myDS.new Node("f"));
System.out.println(myDS.print());
}
}
输出：
f_d_a_b_c_e_End!
英文:
Maybe this is what you wanted
public class MyDS {
Node head=null;
Node next=null;
class Node
{
String data;
Node link=null;
Node(String s)
{
data=s;
}
}
public void add(Node n)
{
if(head == null)
{
head = n;
n.link = null;
}
else
{
if(next == null)
{
next = n;
head.link = next;
}
else
{
next.link = n;
next = n;
}
}
}
public void addTop(Node n)
{
if(head == null)
{
head = n;
n.link = null;
}
else
{
Node oldHead = head;
head = n;
n.link = oldHead;
}
}
public String print()
{
String str="";
Node startN=head;
while(startN.link != null)
{
str+=startN.data+"_";
startN = startN.link;
}
if(startN.data !=null) str+=startN.data+"_End!";
return str;
}
public static void main(String args[])
{
MyDS myDS = new MyDS();
myDS.add(myDS.new Node("a"));
myDS.add(myDS.new Node("b"));
myDS.add(myDS.new Node("c"));
myDS.addTop(myDS.new Node("d"));
myDS.add(myDS.new Node("e"));
myDS.addTop(myDS.new Node("f"));
System.out.println(myDS.print());
}
}
<br>Output
<br><br>f_d_a_b_c_e_End!
专注分享java语言的经验与见解，让所有开发者获益！
评论