I am working on a project using Stacks in Linked Lists. I have to "Implement a stack including a tester. Methods include push, pop, isEmpty, and reverse." I'm working on my reverse method that is meant to reverse a stack. However, for this method, I'm only allowed to "use the following data type as a new variable: int, stack." In this method, I used my LinkedList project for the reverse method but in this case, I'm not allowed to. Does someone know how I would reverse a stack? My code is down below. The first code segment is for my LinkedList and the second code segment is for my Stack project.
import java.util.Random;
public class LinkedListOfInts {
Node head;
Node tail;
private class Node {
int value;
Node nextNode;
public Node(int value, Node nextNode) {
this.value = value;
this.nextNode = nextNode;
}
}
public LinkedListOfInts(int N, int low, int high) {
Random random = new Random();
for (int i = 0; i < N; i )
this.addToFront(random.nextInt(high - low) low);
}
public void addToFront(int x) {
head = new Node(x, head);
if (tail == null)
tail = head;
}
public int deleteFromFront() {
int headValue = -1;
if (head == null)
return headValue;
else {
if (head == tail) {
head = null;
tail = null;
} else {
headValue = head.value;
head = head.nextNode;
}
}
return headValue;
}
public LinkedListOfInts reverse() {
Node previous = null;
Node current = head;
Node next;
while (current != null) {
next = current.nextNode;
current.nextNode = previous;
previous = current;
current = next;
}
head = previous;
return this;
}
public String toString() {
String result = "";
for (Node ptr = head; ptr != null; ptr = ptr.nextNode) {
if (!result.isEmpty()) {
result = ", ";
}
result = ptr.value;
}
return "[" result "]";
}
public static void main(String[] args) {
LinkedListOfInts list = new LinkedListOfInts(5, 1, 10);
System.out.println("Original List" list.toString());
list.addToFront(1);
System.out.println("List After Adding One: " list.toString());
list.addToFront(2);
System.out.println("List After Adding Two: " list.toString());
list.addToFront(3);
System.out.println("List After Adding Three: " list.toString());
list.deleteFromFront();
System.out.println("List After Deleting Item from the Front: " list.toString());
list.reverse();
System.out.println("Reversed List: " list.toString());
}
}
import java.util.Scanner;
public class Stack {
LinkedListOfInts list = new LinkedListOfInts(5, 1, 10);
public void push(int item) {
list.addToFront(item);
}
public int pop() {
return list.deleteFromFront();
}
public boolean isEmpty() {
while (list.head != null) {
list.head = null;
return true;
}
return false;
}
public void reverse() {
Stack tmpB = new Stack();
while (!this.isEmpty()) {
tmpB.push(this.pop());
}
Stack tmpC = new Stack();
while (!tmpB.isEmpty()) {
tmpC.push(tmpB.pop());
}
while (!tmpC.isEmpty()) {
this.push(tmpC.pop());
}
}
@Override
public String toString() {
return "Stack: " list "";
}
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
Stack stack = new Stack();
boolean done = false;
while (!done) {
System.out.println("1. Push");
System.out.println("2. Pop");
System.out.println("3. Empty");
System.out.println("4. Reverse");
System.out.println("5. toString");
switch (input.nextInt()) {
case 1:
System.out.println("Add an Item to the Front of the Stack");
stack.push(input.nextInt());
break;
case 2:
System.out.println("Delete an Item at the Front of the Stack");
System.out.println(stack.pop());
break;
case 3:
System.out.println("Empty a Stack");
System.out.println(stack.isEmpty());
break;
case 4:
System.out.println("Reverse the List");
stack.reverse();
break;
case 5:
System.out.println("toString");
System.out.println(stack.toString());
break;
}
}
}
}
CodePudding user response：
Solution description using only Stack operations (without code - that’s for you to write, which is the point of the exercise):
To create a new stack in reverse order, pop-push every element from old to new.
To reverse a stack, you need to empty it, then pop-push from a stack in same order.
So, if you want to reverse stack A, create 2 new stacks B and C. Pop-push from A->B, then B->C, then C->A.
CodePudding user response：
Ok, after clarifying& fixing methods:
// easiest method to "empty the stack":
public void clear() {
this.list = new LinkedListOfInts();
}
//method identifies, whether there are elements in the stack:
public boolean isEmpty() {
return list.head == null;
}
..and after fixing:
public int deleteFromFront() {
int headValue = -1;
if (head == null)
return headValue;
else { //! move headValue(return value) assignment here, otherwise it returns -1 on 1-element lists.
headValue = head.value;
if (head == tail) {
head = null;
tail = null;
} else {
head = head.nextNode;
}
}
return headValue;
}
we can finally trick like:
public void reverse() {
Stack tmp = new Stack();
while (!this.isEmpty()) {
tmp.push(this.pop());
}
this.list = tmp.list; // ;(;(
}
deliver/enjoy, after:
...
case 3:
System.out.println("Empty a Stack");
stack.clear();
System.out.println("Stack cleared!");
break;
...
case 6:
System.out.println("bye!");
done = true;
break;
And as proposed by Bohemian the "pure stack" solution:
public void reverseStackOnly() { //works! 1^^
Stack tmpB = new Stack();
while (!this.isEmpty()) {
tmpB.push(this.pop());
}
Stack tmpC = new Stack();
while (!tmpB.isEmpty()) {
tmpC.push(tmpB.pop());
}
while (!tmpC.isEmpty()) {
this.push(tmpC.pop());
}
}