{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Stacks and Queues" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Some sample code for binary trees:" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true }, "outputs": [], "source": [ "\n", "\n", "for (int i = 0; i < 1000000; i++) {\n", " while (! bt.add(getRandomNumber())) {\n", " }\n", "}\n", "\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Stacks" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true }, "outputs": [], "source": [ "%%file Stack.java\n", " \n", "public interface Stack {\n", " public void push(T value);\n", " public T pop();\n", "}" ] }, { "cell_type": "code", "execution_count": 7, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Created file '/home/dblank/public_html/CS206 Data Structures/2017-Spring/Notebooks/Stack.java'.\n" ] } ], "source": [ "%%file Stack.java\n", " \n", "public interface Stack {\n", " public void push(Number value);\n", " public Number pop();\n", "}" ] }, { "cell_type": "code", "execution_count": 8, "metadata": { "collapsed": true }, "outputs": [], "source": [ "! javac Stack.java" ] }, { "cell_type": "code", "execution_count": 15, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Created file '/home/dblank/public_html/CS206 Data Structures/2017-Spring/Notebooks/Node.java'.\n" ] } ], "source": [ "%%file Node.java\n", " \n", "public class Node {\n", " Node next;\n", " Number value;\n", " \n", " Node(Number value) {\n", " this.value = value;\n", " }\n", "}" ] }, { "cell_type": "code", "execution_count": 16, "metadata": { "collapsed": true }, "outputs": [], "source": [ "! javac Node.java" ] }, { "cell_type": "code", "execution_count": 23, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Created file '/home/dblank/public_html/CS206 Data Structures/2017-Spring/Notebooks/Calculator.java'.\n" ] } ], "source": [ "%%file Calculator.java\n", " \n", "public class Calculator implements Stack {\n", " Node stack;\n", " \n", " public void push(Number value) {\n", " Node tmp = new Node(value);\n", " tmp.next = stack;\n", " stack = tmp;\n", " }\n", " \n", " public Number pop() {\n", " Node tmp = stack;\n", " stack = tmp.next;\n", " return tmp.value;\n", " }\n", " \n", " public Number eval(String[] args) {\n", " for (int i = 0; i < args.length; i++) {\n", " if (args[i].equals(\"+\")) {\n", " // pop value off stack\n", " Number num = pop();\n", " // get the next number\n", " i++;\n", " Double d = new Double(args[i]);\n", " // push the sum onto stack\n", " push(d + num.doubleValue());\n", " } else { // assume it is an Integer\n", " push(new Integer(args[i]));\n", " }\n", " }\n", " return pop();\n", " }\n", " \n", " public static void main(String[] args) {\n", " Calculator calc = new Calculator();\n", " System.out.println(\"The answer is: \" + calc.eval(args));\n", " }\n", "}" ] }, { "cell_type": "code", "execution_count": 24, "metadata": { "collapsed": false }, "outputs": [], "source": [ "! javac Calculator.java" ] }, { "cell_type": "code", "execution_count": 27, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "The answer is: 6.0\r\n" ] } ], "source": [ "! java Calculator 1 + 2 + 3" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true }, "outputs": [], "source": [ "! java Calculator 34 + 21" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Our calculator has some serious limits.\n", "\n", "# Reverse Polish Notation\n", "\n", "The algorithm for evaluating any postfix expression is fairly straightforward:\n", "\n", "* While there are input tokens left\n", " * Read the next token from input.\n", " * If the token is a value\n", " * Push it onto the stack.\n", " * Otherwise, the token is an operator (operator here includes both operators and functions).\n", " * It is already known that the operator takes n arguments.\n", " * If there are fewer than n values on the stack\n", " * (Error) The user has not input sufficient values in the expression.\n", " * Else, Pop the top n values from the stack.\n", " * Evaluate the operator, with the values as arguments.\n", " * Push the returned results, if any, back onto the stack.\n", "* If there is only one value in the stack\n", " * That value is the result of the calculation.\n", "* Otherwise, there are more values in the stack\n", " * (Error) The user input has too many values.\n", "\n", "(After https://en.wikipedia.org/wiki/Reverse_Polish_notation)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "```\n", "5 1 2 + 4 * + 3 -\n", "```\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "
InputActionStack at endNotes
5Operand5Push onto stack.
1Operand1 5Push onto stack.
2Operand2 1 5Push onto stack.
+Operator3 5Pop the two operands (1, 2), calculate (1 + 2 = 3) and push onto stack.
4Operand4 3 5Push onto stack.
×Operator12 5Pop the two operands (3, 4), calculate (3 * 4 = 12) and push onto stack.
+Operator17Pop the two operands (5, 12), calculate (5 + 12 = 17) and push onto stack.
3Operand3 17Push onto stack.
−Operator14Pop the two operands (17, 3), calculate (17 - 3 = 14) and push onto stack.
Result14
" ] }, { "cell_type": "code", "execution_count": 47, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Created file '/home/dblank/public_html/CS206 Data Structures/2017-Spring/Notebooks/RPN.java'.\n" ] } ], "source": [ "%%file RPN.java\n", " \n", "public class RPN implements Stack {\n", " Node stack;\n", " \n", " public void push(Number value) {\n", " Node tmp = new Node(value);\n", " tmp.next = stack;\n", " stack = tmp;\n", " }\n", " \n", " public Number pop() {\n", " Node tmp = stack;\n", " stack = tmp.next;\n", " return tmp.value;\n", " }\n", " \n", " public Number eval(String[] args) {\n", " for (int i = 0; i < args.length; i++) {\n", " if (args[i].equals(\"+\")) {\n", " // pop value off stack\n", " Number num1 = pop();\n", " Number num2 = pop();\n", " // push the sum onto stack\n", " push(num1.intValue() + num2.intValue());\n", " } else if (args[i].equals(\"*\")) {\n", " // pop value off stack\n", " Number num1 = pop();\n", " Number num2 = pop();\n", " // push the sum onto stack\n", " push(num1.intValue() * num2.intValue());\n", " } else if (args[i].equals(\"-\")) {\n", " // pop value off stack\n", " Number num1 = pop();\n", " Number num2 = pop();\n", " // push the sum onto stack\n", " push(num2.intValue() - num1.intValue());\n", " } else { // assume it is an Integer\n", " push(new Integer(args[i]));\n", " }\n", " }\n", " return pop();\n", " }\n", " \n", " public static void main(String[] args) {\n", " RPN calc = new RPN();\n", " System.out.println(\"The answer is: \" + calc.eval(args));\n", " }\n", "}" ] }, { "cell_type": "code", "execution_count": 48, "metadata": { "collapsed": false }, "outputs": [], "source": [ "! javac RPN.java" ] }, { "cell_type": "code", "execution_count": 50, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "The answer is: 14\r\n" ] } ], "source": [ "! java RPN 5 1 2 + 4 \\* + 3 -" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Queue\n", "\n", "First-in First-Out" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true }, "outputs": [], "source": [ "%%file Queue.java\n", " \n", "public class Queue implements Stack {\n", "}\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Double Ended Queue" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "```java\n", "public class DoubleEndedQueue {\n", " \n", "}\n", "```\n", "\n", "or for short:\n", "\n", "```java\n", "public class Deque {\n", " \n", "}\n", "```\n", "\n", "Pronounced \"deck\"." ] }, { "cell_type": "markdown", "metadata": { "collapsed": true }, "source": [ "# Overload\n", "\n", "When a class has many methods with the same name, but different signatures.\n", "\n", "```java\n", "public class BinaryTree {\n", " void count() {\n", " }\n", " \n", " void count(Node node) {\n", " }\n", "}\n", "```\n", "\n", "not the same as:\n", "\n", "# Overridden \n", "\n", "When a extended class method has the same name as the parent. Recall [Inheritance.ipynb](Inheritance.ipynb)." ] }, { "cell_type": "code", "execution_count": 53, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Created file '/home/dblank/public_html/CS206 Data Structures/2017-Spring/Notebooks/TestMe.java'.\n" ] } ], "source": [ "%%file TestMe.java\n", "\n", "public class TestMe {\n", " void count(Node node, boolean other) {\n", " }\n", "\n", " void count(Node node) {\n", " }\n", "}" ] }, { "cell_type": "code", "execution_count": 54, "metadata": { "collapsed": false }, "outputs": [], "source": [ "! javac TestMe.java" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true }, "outputs": [], "source": [] } ], "metadata": { "kernelspec": { "display_name": "Calysto Processing", "language": "java", "name": "calysto_processing" }, "language_info": { "codemirror_mode": { "name": "text/x-java", "version": 2 }, "file_extension": ".java", "mimetype": "text/x-java", "name": "java" } }, "nbformat": 4, "nbformat_minor": 1 }