Java 中的泛型(队列)
Generics in Java (Queue)
我实现了一个 Stack Class。
现在,我想基于该堆栈创建一个队列。像这样:
public class Queue<E> {
private Stack<E> next;
private Stack<E> next2;
public E first() {
}
public Queue<E> enqueue(E e) {
}
public Queue<E> dequeue() {
}
public boolean isEmpty() {
if (this.next == null) {
return true;
}
if (Stack.isEmpty(next)) {
return true;
}
return false;
}
}
我不知道从哪里开始。我怎么解决这个问题?我的第一个想法是使用 Stack 中的“反向”方法。但我不确定。
有两种方法可以做到这一点。第一个是使用你的函数 reverse 推到堆栈的末尾。像这样
public class Queue<E> {
private Stack<E> next;
public E front() {
return (E) Stack.<E>top(next);
}
public Queue<E> enqueue(E e) {
Stack<E> nextNew = Stack.reverse(next);
nextNew = Stack.push(nextNew, e);
nextNew = Stack.reverse(nextNew);
Queue<E> q = new Queue<E>();
q.next = nextNew;
return q;
}
public Queue<E> dequeue() {
Stack<E> nextNew = Stack.pop(next);
Queue<E> q = new Queue<E>();
q.next = nextNew;
return q;
}
public boolean isEmpty() {
if (this.next == null) {
return true;
}
if (Stack.isEmpty(next)) {
return true;
}
return false;
}
}
我认为递归最流畅:
public class Queue<E> {
private Stack<E> stack;
public Queue(Stack stack) {
this.stack = stack;
}
public E front() {
return Stack.top(stack);
}
public Queue<E> enqueue(E newValue) {
if (Stack.top(stack) == null) {
return new Queue(Stack.push(Stack.create(), newValue));
}
return new Queue<>(Stack.push(new Queue(Stack.pop(stack)).enqueue(newValue).stack, Stack.top(stack)));
}
public Queue<E> dequeue() {
return new Queue<>(Stack.pop(stack));
}
public String toString() {
return "Q: " + stack.toString();
}
}
请注意,不需要反转。
我认为 Stack class 中的一些代码对于“a”参数和额外变量有点不清楚,所以我对其进行了一些重构并删除了所有未使用的内容。我还添加了一个递归遍历堆栈的toString()
:
public class Stack<E> {
private final E value;
private final Stack<E> next;
private Stack(E value, Stack<E> next) {
this.value = value;
this.next = next;
}
public static <E> Stack<E> create() {
return new Stack<>(null, null);
}
public static <E> Stack<E> push(Stack<E> stack, E newValue) {
return new Stack<E>(newValue, stack);
}
public static <E> Stack<E> pop(Stack<E> stack) {
if (stack == null) {
return new Stack<E>(null, null);
} else if (stack.value == null) {
return new Stack<>(null, null);
} else if (stack.next == null) {
return new Stack<E>(null, null);
} else {
return stack.next;
}
}
public static <E> E top(Stack<E> stack) {
if (stack == null) {
return null;
} else if (stack.value == null) {
return null;
} else {
return stack.value;
}
}
public String toString() {
if (Stack.top(next) == null) {
return (value != null ? value.toString() : "Null");
}
return (value != null ? value.toString() : "Null") + " " + next.toString();
}
}
还有一点测试class。为了显示堆栈和队列之间的区别,它首先加载一个堆栈,然后将其传递给一个队列并添加更多元素,然后从前面拉出一些元素:
public class QueueWithStackMain {
public static void main(String[] args) {
Stack<String> stack = Stack.create();
stack = Stack.push(stack, "1");
System.out.println(stack.toString());
stack = Stack.push(stack, "2");
System.out.println(stack.toString());
stack = Stack.push(stack, "3");
System.out.println(stack.toString());
Queue<String> queue = new Queue<>(stack);
System.out.println(queue.toString());
queue = queue.enqueue("4");
System.out.println(queue.toString());
queue = queue.enqueue("5");
System.out.println(queue.toString() + " -> " + queue.front());
queue = queue.dequeue();
System.out.println(queue.toString() + " -> " + queue.front());
}
}
我实现了一个 Stack Class。
现在,我想基于该堆栈创建一个队列。像这样:
public class Queue<E> {
private Stack<E> next;
private Stack<E> next2;
public E first() {
}
public Queue<E> enqueue(E e) {
}
public Queue<E> dequeue() {
}
public boolean isEmpty() {
if (this.next == null) {
return true;
}
if (Stack.isEmpty(next)) {
return true;
}
return false;
}
}
我不知道从哪里开始。我怎么解决这个问题?我的第一个想法是使用 Stack 中的“反向”方法。但我不确定。
有两种方法可以做到这一点。第一个是使用你的函数 reverse 推到堆栈的末尾。像这样
public class Queue<E> {
private Stack<E> next;
public E front() {
return (E) Stack.<E>top(next);
}
public Queue<E> enqueue(E e) {
Stack<E> nextNew = Stack.reverse(next);
nextNew = Stack.push(nextNew, e);
nextNew = Stack.reverse(nextNew);
Queue<E> q = new Queue<E>();
q.next = nextNew;
return q;
}
public Queue<E> dequeue() {
Stack<E> nextNew = Stack.pop(next);
Queue<E> q = new Queue<E>();
q.next = nextNew;
return q;
}
public boolean isEmpty() {
if (this.next == null) {
return true;
}
if (Stack.isEmpty(next)) {
return true;
}
return false;
}
}
我认为递归最流畅:
public class Queue<E> {
private Stack<E> stack;
public Queue(Stack stack) {
this.stack = stack;
}
public E front() {
return Stack.top(stack);
}
public Queue<E> enqueue(E newValue) {
if (Stack.top(stack) == null) {
return new Queue(Stack.push(Stack.create(), newValue));
}
return new Queue<>(Stack.push(new Queue(Stack.pop(stack)).enqueue(newValue).stack, Stack.top(stack)));
}
public Queue<E> dequeue() {
return new Queue<>(Stack.pop(stack));
}
public String toString() {
return "Q: " + stack.toString();
}
}
请注意,不需要反转。
我认为 Stack class 中的一些代码对于“a”参数和额外变量有点不清楚,所以我对其进行了一些重构并删除了所有未使用的内容。我还添加了一个递归遍历堆栈的toString()
:
public class Stack<E> {
private final E value;
private final Stack<E> next;
private Stack(E value, Stack<E> next) {
this.value = value;
this.next = next;
}
public static <E> Stack<E> create() {
return new Stack<>(null, null);
}
public static <E> Stack<E> push(Stack<E> stack, E newValue) {
return new Stack<E>(newValue, stack);
}
public static <E> Stack<E> pop(Stack<E> stack) {
if (stack == null) {
return new Stack<E>(null, null);
} else if (stack.value == null) {
return new Stack<>(null, null);
} else if (stack.next == null) {
return new Stack<E>(null, null);
} else {
return stack.next;
}
}
public static <E> E top(Stack<E> stack) {
if (stack == null) {
return null;
} else if (stack.value == null) {
return null;
} else {
return stack.value;
}
}
public String toString() {
if (Stack.top(next) == null) {
return (value != null ? value.toString() : "Null");
}
return (value != null ? value.toString() : "Null") + " " + next.toString();
}
}
还有一点测试class。为了显示堆栈和队列之间的区别,它首先加载一个堆栈,然后将其传递给一个队列并添加更多元素,然后从前面拉出一些元素:
public class QueueWithStackMain {
public static void main(String[] args) {
Stack<String> stack = Stack.create();
stack = Stack.push(stack, "1");
System.out.println(stack.toString());
stack = Stack.push(stack, "2");
System.out.println(stack.toString());
stack = Stack.push(stack, "3");
System.out.println(stack.toString());
Queue<String> queue = new Queue<>(stack);
System.out.println(queue.toString());
queue = queue.enqueue("4");
System.out.println(queue.toString());
queue = queue.enqueue("5");
System.out.println(queue.toString() + " -> " + queue.front());
queue = queue.dequeue();
System.out.println(queue.toString() + " -> " + queue.front());
}
}