Doubly Linked List Infix to PostFix

Question

For class, we are tasked with the assignment of converting an infix expression to postfix using a "doubly linked list stack implementation in abstraction". I was able to write a program that uses the Stack in order to make the conversion, but what is the purpose of the doubly linked list? What node of information are we adding to the list?

This is the stack class that was provided to us as an example. Why is the variable next type Stack? Shouldn't it be Node?

public class Stack {
  private int data;
  private Stack next;
  private static Stack top;

  //Initialize Stack
  public Stack () {
      top = null;
      next = null;
  }

  public Stack (int d, Stack node) {
      data = d;
      next = node;
  }

  public void push(int item) {
      top = new Stack(item, top);
  }

  public int peek () {
     if(top == null) {
         throw new EmptyStackException();
     } 
     return (top.data);          
  }

  public int pop () {
      int item;

      if(top == null) {
          throw new EmptyStackException();
      } else
          item = top.data;
      top = top.next;
      return (item);
  }

  public boolean empty () {
      return top == null;
  }
}

If I create a doubly linked list and node class, what data is in the node object?

x Nuclear 213 x Nuclear 213 · Accepted Answer · 2015-05-06T23:10:37

0

votes

Data member of Node class would be: pointers to previous and next, along with the data.

Doubly Linked List Infix to PostFix

2 Answers