Stack using double-linked list
Hey. I am assigned to do Stack using double-linked list and I faced a problem. I can't link to previous element (while I had no problems using one link).
class Node
{
Data data;
Node previous;
Node next;
}
class Data
{
int size;
double price;
boolean isOnOffer;
char sex;
String brand;
Data(int size, double price, boolean isOnOffer, char sex, String brand){
this.size = size;
this.price = price;
this.isOnOffer = isOnOffer;
this.sex = sex;
this.brand = brand;
}
}
class Stack
{
private static int sizeOfS开发者_运维百科tack;
private static Node topElement;
public static boolean isEmpty() { return topElement == null; }
public static void Initialize() {
sizeOfStack = 0;
topElement = null;
}
public static void Push(Data x) {
Node oldElement = topElement;
topElement = new Node();
topElement.data = x;
topElement.next = oldElement;
topElement.previous = null;
//oldElement.previous = topElement; // <----- problem here
sizeOfStack++;
}
public static void Pop() {
if (!isEmpty()){
topElement = topElement.next; // delete first node
sizeOfStack--;
}
}
public static void Top() {
int size = topElement.data.size;
double price = topElement.data.price;
boolean isOnOffer = topElement.data.isOnOffer;
char sex = topElement.data.sex;
String brand = topElement.data.brand;
System.out.println(size + " " + price + " " + isOnOffer + " " + sex + " " + brand);
}
public static void Kill() { }
public static void Print() { }
public static void main(String[] args){
Push(new Data(37, 155, false, 'F', "Nike"));
Push(new Data(38, 140, true, 'F', "Reebok"));
Push(new Data(35, 160.99, false, 'F', "Converse"));
Push(new Data(35, 20.99, true, 'F', "Inkaras"));
Pop();
Pop();
Top();
}
}
//oldElement.previous = topElement; // <----- problem here
As already pointed out: if oldElement
is null, you'd get a NullPointerException. Check for null before, like if(oldElement != null) { oldElement.previous = topElement; }
.
Also note that the Top()
method won't work for an empty stack, it would throw an NPE in the first line topElement.data...
.
Look at the different cases:
{Stack} //Top of stack is the leftmost node
[Node(Next|Prev)]
Case: #1 "empty stack case"
{null}
Push:
[Node1(null|null)]
Case: #2 "normal case"
{[Node1(null|null)]}
Push:
[Node2(Node1|null)]
Change:
[Node1(null|null)] -> [Node1(null|Node2)]
Looking at Case: #3 we see that it is similar to case #2, no need to implement
{[Node2(Node1|null)],[Node1(null|Node2)]}
Push:
[Node3(Node2|null)]
Change:
[Node2(Node1|null)] -> [Node2(Node1|Node3)]
精彩评论