## Jupyter at Bryn Mawr College

Public notebooks: /services/public/dblank / CS206 Data Structures / 2017-Spring / Notebooks

# Stacks and Queues¶

Some sample code for binary trees:

In [ ]:
for (int i = 0; i < 1000000; i++) {
}
}


## Stacks¶

In [ ]:
%%file Stack.java

public interface Stack<T> {
public void push(T value);
public T pop();
}

In [7]:
%%file Stack.java

public interface Stack {
public void push(Number value);
public Number pop();
}

Created file '/home/dblank/public_html/CS206 Data Structures/2017-Spring/Notebooks/Stack.java'.

In [8]:
! javac Stack.java

In [15]:
%%file Node.java

public class Node {
Node next;
Number value;

Node(Number value) {
this.value = value;
}
}

Created file '/home/dblank/public_html/CS206 Data Structures/2017-Spring/Notebooks/Node.java'.

In [16]:
! javac Node.java

In [23]:
%%file Calculator.java

public class Calculator implements Stack {
Node stack;

public void push(Number value) {
Node tmp = new Node(value);
tmp.next = stack;
stack = tmp;
}

public Number pop() {
Node tmp = stack;
stack = tmp.next;
return tmp.value;
}

public Number eval(String[] args) {
for (int i = 0; i < args.length; i++) {
if (args[i].equals("+")) {
// pop value off stack
Number num = pop();
// get the next number
i++;
Double d = new Double(args[i]);
// push the sum onto stack
push(d + num.doubleValue());
} else { // assume it is an Integer
push(new Integer(args[i]));
}
}
return pop();
}

public static void main(String[] args) {
Calculator calc = new Calculator();
System.out.println("The answer is: " + calc.eval(args));
}
}

Created file '/home/dblank/public_html/CS206 Data Structures/2017-Spring/Notebooks/Calculator.java'.

In [24]:
! javac Calculator.java

In [27]:
! java Calculator 1 + 2 + 3

The answer is: 6.0

In [ ]:
! java Calculator 34 + 21


Our calculator has some serious limits.

# Reverse Polish Notation¶

The algorithm for evaluating any postfix expression is fairly straightforward:

• While there are input tokens left
• Read the next token from input.
• If the token is a value
• Push it onto the stack.
• Otherwise, the token is an operator (operator here includes both operators and functions).
• It is already known that the operator takes n arguments.
• If there are fewer than n values on the stack
• (Error) The user has not input sufficient values in the expression.
• Else, Pop the top n values from the stack.
• Evaluate the operator, with the values as arguments.
• Push the returned results, if any, back onto the stack.
• If there is only one value in the stack
• That value is the result of the calculation.
• Otherwise, there are more values in the stack
• (Error) The user input has too many values.
5 1 2 + 4 * + 3 -
Input Action Stack at end Notes
5 Operand 5 Push onto stack.
1 Operand 1 5 Push onto stack.
2 Operand 2 1 5 Push onto stack.
+ Operator 3 5 Pop the two operands (1, 2), calculate (1 + 2 = 3) and push onto stack.
4 Operand 4 3 5 Push onto stack.
× Operator 12 5 Pop the two operands (3, 4), calculate (3 * 4 = 12) and push onto stack.
+ Operator 17 Pop the two operands (5, 12), calculate (5 + 12 = 17) and push onto stack.
3 Operand 3 17 Push onto stack.
Operator 14 Pop the two operands (17, 3), calculate (17 - 3 = 14) and push onto stack.
Result 14
In [47]:
%%file RPN.java

public class RPN implements Stack {
Node stack;

public void push(Number value) {
Node tmp = new Node(value);
tmp.next = stack;
stack = tmp;
}

public Number pop() {
Node tmp = stack;
stack = tmp.next;
return tmp.value;
}

public Number eval(String[] args) {
for (int i = 0; i < args.length; i++) {
if (args[i].equals("+")) {
// pop value off stack
Number num1 = pop();
Number num2 = pop();
// push the sum onto stack
push(num1.intValue() + num2.intValue());
} else if (args[i].equals("*")) {
// pop value off stack
Number num1 = pop();
Number num2 = pop();
// push the sum onto stack
push(num1.intValue() * num2.intValue());
} else if (args[i].equals("-")) {
// pop value off stack
Number num1 = pop();
Number num2 = pop();
// push the sum onto stack
push(num2.intValue() - num1.intValue());
} else { // assume it is an Integer
push(new Integer(args[i]));
}
}
return pop();
}

public static void main(String[] args) {
RPN calc = new RPN();
System.out.println("The answer is: " + calc.eval(args));
}
}

Created file '/home/dblank/public_html/CS206 Data Structures/2017-Spring/Notebooks/RPN.java'.

In [48]:
! javac RPN.java

In [50]:
! java RPN 5 1 2 + 4 \* + 3 -

The answer is: 14


# Queue¶

First-in First-Out

In [ ]:
%%file Queue.java

public class Queue implements Stack {
}


# Double Ended Queue¶

public class DoubleEndedQueue {

}


or for short:

public class Deque {

}


Pronounced "deck".

When a class has many methods with the same name, but different signatures.

public class BinaryTree {
void count() {
}

void count(Node node) {
}
}


not the same as:

# Overridden¶

When a extended class method has the same name as the parent. Recall Inheritance.ipynb.

In [53]:
%%file TestMe.java

public class TestMe {
void count(Node node, boolean other) {
}

void count(Node node) {
}
}

Created file '/home/dblank/public_html/CS206 Data Structures/2017-Spring/Notebooks/TestMe.java'.

In [54]:
! javac TestMe.java