У меня два LinkedStack (ов). LinkedStack stackOne со вставленными в него [9,7,5,3,1] узлами. LinkedStack stackTwo со вставленными в него [10,8,6,4,2] узлов.
Мне нужно добавить первый узел из stackTwo в stackOne и использовать указатель, чтобы отслеживать, где я нахожусь в StackOne. Второй узел от stackTwo до stackOne нужно добавить, начиная с указателя, который удерживает позицию предыдущей вставки.
Мне нужно предположить, что stackOne и stackTwo являются ссылочными переменными LinearNode. Я мог бы реализовать эти
Ниже я придумал. Я использую метод stackOne.pu sh () для первого случая, поскольку 10> 9. Я не могу обернуть голову вокруг случая сохранения 9 в качестве позиции указателя, а при вставке второго di git (8) это вставлен в стек без дальнейшего поиска нужного места.
Спасибо за ваше время!
LinearNode. java
public class LinearNode<T> {
// Linear Node variables are initialized below
LinearNode<T> next;
private T element;
// Constructor of an empty object
public LinearNode() {
next = null;
element = null;
} // End of LinearNode
// Constructor of a filled object
public LinearNode(T elementP) {
next = null;
element = elementP;
} // End of LinearNode(Integer elementP)
// Returning following node of current target
public LinearNode<T> getNext() {
return next;
} // End of getNext()
// Setting the following node of current target
public void setNext(LinearNode<T> nodeP) {
next = nodeP;
} // End of setNext(LinearNode<Integer> nodeP)
// Returns the element of a current node
public T getElement() {
return element;
} // End of getElement()
// Sets the element for a current node
public void setElement(T interValue) {
element = interValue;
} // End of setElement(Integer elementP)
// toString method
public String toString() {
return "" + element;
} // End of toString()
} // End of LinearNode
LinkedStack. java
import java.util.EmptyStackException;
public class LinkedStack<T> implements StackADT<T> {
// Variable initialization
private int count;
private LinearNode top;
// Creating an empty LinkedStack
public LinkedStack() {
count = 0;
top = null;
} // End of LinkedStack()
// Adding a node to a stack
public void push(T elementP) {
LinearNode temp = new LinearNode<T>(elementP);
temp.setNext(top);
top = temp;
count++;
} // End of push(T elementP)
// Removing the top of the stack,
// and returning a reference to it.
public T pop() throws EmptyStackException {
if (isEmpty())
throw new EmptyStackException();
@SuppressWarnings("unchecked")
T result = (T) ((LinearNode) top).getElement();
top = top.getNext();
//top = (LinearNode) ((LinearNode) top).getNext().getElement();
//top.setNext(this.top.getNext());
count--;
return result;
} // End of pop()
// returns a reference to the top element
// of a stack
@SuppressWarnings("unchecked")
public T peek() throws EmptyStackException {
if (isEmpty())
throw new EmptyStackException();
T result = (T) top.getElement();
return result;
} // End of peek
// Checking a stack for any elements present
public boolean isEmpty() {
if (this.count == 0) // if elements not present
{
return true; // return empty
}
return false; // return not empty
} // End of isEmpty()
// Returning the size of a given stack
public int Size() {
return this.count;
} // End of size()
// custom toString() operation
public String toString() {
String stackPrint = "";
LinearNode temp = new LinearNode();
temp = top;
while (temp != null){
stackPrint += " " + temp.toString();
temp = temp.getNext();}
return stackPrint;
} // End of toString
// method inserting an element in the reverse positioning
public LinkedStack<LinearNode> reverseStack(LinkedStack stackP)
{
// linerStack helps with the facilitation
LinkedStack<LinearNode> stackTest = new LinkedStack();
// a LinearNode facilitating the calculation
LinearNode<LinearNode> nodeTest = stackP.top;
// stripping a stack
while (nodeTest.getNext() != null)
{
stackTest.push(nodeTest);
nodeTest = nodeTest.getNext();
} // End of While
stackP.push(nodeTest);
while (!stackTest.isEmpty())
{
nodeTest.setNext((LinearNode) stackTest.peek());
nodeTest = nodeTest.getNext();
stackTest.pop();
} // End of While
nodeTest.setNext(null);
return stackP;
} // End of reverseStack
// Insertion with the ability of tracking
// the last place a value was inserted.
public void insertListOne(T nodeP)
{
// LinearNode temp = new LinearNode<T>(elementP);
// temp.setNext(top);
// top = temp;
// count++;
LinearNode insertionNode = new LinearNode<T>(nodeP);
LinearNode pointer = this.top;
System.out.println("Pointer: " + pointer.toString() + "Inserting: " + insertionNode);
int interNodeInt = 0;
int insertionNodeInt = 0;
int relation = 0;
try
{
System.out.println("Top Node from List One: " + pointer + " ");
interNodeInt = Integer.parseInt(pointer.toString());
System.out.println("Insertion Node from List Two: " + insertionNode + " ");
insertionNodeInt = Integer.parseInt(insertionNode.toString());
}
catch (NumberFormatException e)
{
System.out.println("Oopsie at the integer parser.");
}
relation = interNodeInt < insertionNodeInt ? 1 : 2;
switch(relation)
{
case 1:
System.out.println("Insert at the top.");
pointer = this.top;
System.out.println("Pointer :" + pointer);
this.push((T) insertionNode);
System.out.println("List One: " + this.toString());
System.out.print("\n");
break;
case 2:
System.out.println("Move a layer down.");
*********************************************************************
с использованием указателя для вставки di git
System.out.println("Pointer :" + pointer);
while (this.peek() != pointer)
{
LinkedStack interStack = this;
interStack.pop();
// how to select a second item in a linked stack
}
System.out.println("List One: " + this.toString());
System.out.print("\n");
break;
}
} // End of LinkedStack
} // End of LinkedStack
StackADT. java
// Interface for the Stack
public interface StackADT<T> {
// pushes an element onto a stack
public void push(T element);
// removes an element from a stack
public T pop();
// Show's the top element of a stack
public T peek();
// Checks if stack has any elements
public boolean isEmpty();
// Checks the amount of nodes in a given stack
public int Size();
// Outputs a given stack
public String toString();
} // End of StackATD<T>
digitArrayTester. java
public class digitArrayTester {
static LinearNode nodeA = new LinearNode();
static LinearNode nodeB = new LinearNode();
static LinkedStack listOne = new LinkedStack();
static LinkedStack listTwo = new LinkedStack();
static LinearNode []nodeHelper = new LinearNode [10];
public static void main(String[] args) {
for (int count = 0; count < 10; count++)
{
if (count == 0)
{
nodeHelper[count] = new LinearNode();
nodeHelper[count].setElement(++count);
nodeA.setElement(nodeHelper[--count]);
listOne.push(nodeHelper[count]);
nodeHelper[++count] = new LinearNode();
nodeHelper[count].setElement(++count);
nodeB.setElement(nodeHelper[--count]);
System.out.println("Inserting Values into List One and List Two");
System.out.print("\n");
listTwo.push(nodeHelper[count]);
System.out.println("Adding to List One : " + nodeA.toString() + "\t " + "Adding to List Two : " + nodeB.toString());
System.out.println("List One: " + listOne.toString() + "\t" + "List Two: " + listTwo.toString());
}
else
{
nodeHelper[count] = new LinearNode();
nodeHelper[count].setElement(++count);
nodeA.setNext(nodeHelper[--count]);
listOne.push(nodeHelper[count]);
nodeHelper[++count] = new LinearNode();
nodeHelper[count].setElement(++count);
nodeB.setNext(nodeHelper[--count]);
listTwo.push(nodeHelper[count]);
System.out.println("Adding to List One : " + nodeA.getNext().toString() + "\t " + "Adding to List Two : " + nodeB.getNext().toString());
System.out.println("List One: " +listOne.toString() + "\t" + "List Two: " + listTwo.toString());
}
} // End of LinkedStack population
while (!listTwo.isEmpty())
{
LinearNode interNode = new LinearNode();
interNode = (LinearNode) listTwo.pop();
//listOne.push(inter); not using push since the new value needs to be placed
// on a specific spot based on the relationship to other values.
listOne.insertListOne(interNode);
System.out.print("\n");
System.out.println("List One: " +listOne.toString() + "\t" + "List Two: " + listTwo.toString());
}
} // End of main()
} // End of digitArrayTester