为使用节点的堆栈创建一个 int search(Object o) 方法 [英] Make an int search(Object o) method for a stack that uses nodes
问题描述
我正在尝试创建一个使用通用节点类的通用堆栈和队列类.它有 empty()、pop()、peek()、push() 和一个 search() 方法.我知道有一个内置的 Stack 类和 stack search 方法，但我们必须使用 Node 类来实现.
I'm trying to make a generic stack and queue class that uses the generic node class. It has empty(), pop(), peek(), push(), and a search() method. I know there is a built-in Stack class and stack search method but we have to make it by using the Node class.
我不确定如何制作 search 方法.search 方法应该返回离栈顶最近的事件的栈顶的距离.最上面的项目被认为在距离 1 处；下一个项目在距离 2 处；等
I am unsure of how to make the search method. The search method is supposed to return the distance from the top of the stack of the occurrence that is nearest the top of the stack. The topmost item is considered to be at distance 1; the next item is at distance 2; etc.
我的课程如下:
import java.io.*;
import java.util.*;
public class MyStack<E> implements StackInterface<E>
{
private Node<E> head;
private int nodeCount;
public static void main(String args[]) {
}
public E peek() {
return this.head.getData();
}
public E pop() {
E item;
item = head.getData();
head = head.getNext();
nodeCount--;
return item;
}
public boolean empty() {
if (head==null) {
return true;
} else {
return false;
}
}
public void push(E data) {
Node<E> head = new Node<E>(data);
nodeCount++;
}
public int search(Object o) {
// todo
}
}
public class Node<E>
{
E data;
Node<E> next;
// getters and setters
public Node(E data)
{
this.data = data;
this.next = null;
}
public E getData() {
return data;
}
public void setData(E data) {
this.data = data;
}
public Node<E> getNext() {
return next;
}
public void setNext(Node<E> next) {
this.next = next;
}
}
public class MyQueue<E> implements QueueInterface<E>
{
private Node<E> head;
private int nodeCount;
Node<E> rear;
public MyQueue()
{
this.head = this.rear = null;
}
public void add(E item){
Node<E> temp = new Node<E>(item);
if (this.rear == null) {
this.head = this.rear = temp;
return;
}
this.rear.next = temp;
this.rear = temp;
}
public E peek(){
return this.head.getData();
}
public E remove(){
E element = head.getData();
Node<E> temp = this.head;
this.head = this.head.getNext();
nodeCount--;
return element;
}
}
根据第一条评论进行处理后，我有这个:
After working on it based off of the first comment I have this:
public int search(Object o){
int count=0;
Node<E> current = new Node<E> (head.getData());
while(current.getData() != o){
current.getNext();
count++;
}
return count;
}
它没有任何错误，但我不知道它是否真的正常工作.这看起来正确吗?
It doesn't have any errors but I cannot tell if it is actually working correctly. Does this seem correct?
推荐答案
我认为您的 MyStack 类应该与您提到的 Java 提供的 Stack 类兼容在你的问题中.这意味着您的签名 public int search(Object o) 与 java.util.Stack#search(除了synchronised).
I assume your MyStack class should be compatible with the Stack class provided by Java as you mention it in your question. This means that your signature public int search(Object o) matches the signature of java.util.Stack#search (apart from synchronised).
要使用您的 Node 类实现 search 方法，我们需要遍历堆栈并返回第一个(最上面)匹配项的索引.首先，将head 赋值给一个局部变量(current).然后你可以创建一个循环，你在 current.getNext() 最后获得下一个元素.如果下一个元素是 null 则停止，因为我们已经到达堆栈的末尾.在循环中，您要么对 index 进行计数，要么在当前元素的数据与参数 o 匹配时返回此索引.
To implement the search method using your Node class, we need to traverse the stack and return the index of the first (uppermost) match. First, assign head to a local variable (current). Then you can create a loop where you current.getNext() at the end to get the next element. Stop if the next element is null as we have reached the end of the stack. In the loop, you either count up the index or return this index when the current element's data matches the argument o.
评估需要能够处理参数 o 的 null 值.因此，您需要先检查 null 并相应地调整您的逻辑.当 o 为 null 时，对 current.getData() 做一个 null 检查.如果 o 不是 null，检查 current.getData() 是否等于 o 且 equals().
The evaluation needs to be able to deal with null values for your argument o. Therefore, you need to check for null first and adjust your logic accordingly. When o is null, do a null-check against current.getData(). If o is not null, check if current.getData() is equal to o with equals().
这是一个工作示例: (与 java.util.Stack#search 兼容)
public int search(Object o) {
int index = 1;
Node<E> current = head;
while (current != null) {
if (o == null) {
if (current.getData() == null) {
return index;
}
} else {
if (o.equals(current.getData())) {
return index;
}
}
current = current.getNext();
index++;
}
return -1; // nothing found
}
要对此进行测试，您可以使用 JUnit 编写一个简单的单元测试，如下所示:
@Test
public void testMyStackSearch() {
// initialize
final MyStack<String> stack = new MyStack<>();
stack.push("e5");
stack.push("e4");
stack.push(null);
stack.push("e2");
stack.push("e1");
// test (explicitly creating a new String instance)
assertEquals(5, stack.search(new String("e5")));
assertEquals(3, stack.search(null));
assertEquals(2, stack.search(new String("e2")));
assertEquals(1, stack.search(new String("e1")));
assertEquals(-1, stack.search("X"));
}
由于您已经有了参考实现，您可以将 MyStack 替换为 Stack (java.util.Stack) 并查看您的断言是正确的.如果运行成功，请将其改回 MyStack 并查看您的实现是否正确.
Since you have already a reference implementation, you can replace MyStack with Stack (java.util.Stack) and see if your asserts are correct. If this runs successfully, change it back to MyStack and see if your implementation is correct.
注意:我不建议实际使用 Stack 在 Java 中的实现.在这里，它只是作为 java.util.Stack#search 方法的参考实现.Deque 接口及其实现提供了一组更完整和一致的 LIFO 堆栈操作，应该优先使用 Stack.
Note: I do not recommend to actually use the Stack implementation in Java. Here, it just serves as a reference implementation for the java.util.Stack#search method. The Deque interface and its implementations offer a more complete and consistent set of LIFO stack operations, which should be used in preference to Stack.
这篇关于为使用节点的堆栈创建一个 int search(Object o) 方法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
