From 4631f2cec9d94a0b4869fe1fc5c3c036f42a8db0 Mon Sep 17 00:00:00 2001 From: bculkin2442 Date: Sat, 11 Mar 2017 05:22:08 -0500 Subject: Stack work There are now multiple kinds of stacks, with Stack being abstract and SimpleStack being the basic implementation. QueueStack is a stack that's actually a queue. SpaghettiStack is a stack that has a parent it can access. --- .../main/java/bjc/utils/esodata/QueueStack.java | 50 +++++++ .../main/java/bjc/utils/esodata/SimpleStack.java | 50 +++++++ .../java/bjc/utils/esodata/SpaghettiStack.java | 62 +++++++++ .../src/main/java/bjc/utils/esodata/Stack.java | 148 +++++++++------------ 4 files changed, 228 insertions(+), 82 deletions(-) create mode 100644 BJC-Utils2/src/main/java/bjc/utils/esodata/QueueStack.java create mode 100644 BJC-Utils2/src/main/java/bjc/utils/esodata/SimpleStack.java create mode 100644 BJC-Utils2/src/main/java/bjc/utils/esodata/SpaghettiStack.java (limited to 'BJC-Utils2/src/main/java/bjc') diff --git a/BJC-Utils2/src/main/java/bjc/utils/esodata/QueueStack.java b/BJC-Utils2/src/main/java/bjc/utils/esodata/QueueStack.java new file mode 100644 index 0000000..472e161 --- /dev/null +++ b/BJC-Utils2/src/main/java/bjc/utils/esodata/QueueStack.java @@ -0,0 +1,50 @@ +package bjc.utils.esodata; + +import java.util.ArrayList; +import java.util.Deque; +import java.util.List; +import java.util.LinkedList; +import java.util.function.Consumer; + +/** + * A FIFO implementation of a stack. + * + * @param T The datatype stored in the stack. + * @author Ben Culkin + */ +public class QueueStack extends Stack { + private Deque backing; + + /** + * Create a new empty stack queue. + * + */ + public SimpleStack() { + backing = new LinkedList(); + } + + @Override + public void push(T elm) { + backing.add(elm); + } + + @Override + public T pop() { + return backing.remove(); + } + + @Override + public T top() { + return backing.peek(); + } + + @Override + public int size() { + return backing.size(); + } + + @Override + public boolean empty() { + return backing.size() == 0; + } +} diff --git a/BJC-Utils2/src/main/java/bjc/utils/esodata/SimpleStack.java b/BJC-Utils2/src/main/java/bjc/utils/esodata/SimpleStack.java new file mode 100644 index 0000000..67f228f --- /dev/null +++ b/BJC-Utils2/src/main/java/bjc/utils/esodata/SimpleStack.java @@ -0,0 +1,50 @@ +package bjc.utils.esodata; + +import java.util.ArrayList; +import java.util.Deque; +import java.util.List; +import java.util.LinkedList; +import java.util.function.Consumer; + +/** + * Simple implementation of a stack. + * + * @param T The datatype stored in the stack. + * @author Ben Culkin + */ +public class SimpleStack extends Stack { + private Deque backing; + + /** + * Create a new empty stack. + * + */ + public SimpleStack() { + backing = new LinkedList(); + } + + @Override + public void push(T elm) { + backing.push(elm); + } + + @Override + public T pop() { + return backing.pop(); + } + + @Override + public T top() { + return backing.peek(); + } + + @Override + public int size() { + return backing.size(); + } + + @Override + public boolean empty() { + return backing.size() == 0; + } +} diff --git a/BJC-Utils2/src/main/java/bjc/utils/esodata/SpaghettiStack.java b/BJC-Utils2/src/main/java/bjc/utils/esodata/SpaghettiStack.java new file mode 100644 index 0000000..75e6331 --- /dev/null +++ b/BJC-Utils2/src/main/java/bjc/utils/esodata/SpaghettiStack.java @@ -0,0 +1,62 @@ +package bjc.utils.esodata; + +import java.util.ArrayList; +import java.util.Deque; +import java.util.List; +import java.util.LinkedList; +import java.util.function.Consumer; + +/* + * Implements a spaghetti stack, which is a stack that is branched off of a + * parent stack. + * + * @param T The datatype stored in the stack. + * @author Ben Culkin + */ +class SpaghettiStack extends Stack { + private Stack backing; + + private Stack parent; + + /** + * Create a new empty spaghetti stack, off of the specified parent. + * + * @param par The parent stack + */ + public SimpleStack() { + backing = new SimpleStack(); + } + + @Override + public void push(T elm) { + backing.push(elm); + } + + @Override + public T pop() { + if(backing.empty()) { + return parent.pop(); + } + + return backing.pop(); + } + + @Override + public T top() { + if(backing.empty()) { + return parent.top(); + } + + return backing.peek(); + } + + @Override + public int size() { + return parent.size() + backing.size(); + } + + @Override + public boolean empty() { + return backing.empty() && parent.empty(); + } +} diff --git a/BJC-Utils2/src/main/java/bjc/utils/esodata/Stack.java b/BJC-Utils2/src/main/java/bjc/utils/esodata/Stack.java index 71db3d6..43e10ab 100644 --- a/BJC-Utils2/src/main/java/bjc/utils/esodata/Stack.java +++ b/BJC-Utils2/src/main/java/bjc/utils/esodata/Stack.java @@ -14,59 +14,43 @@ import java.util.function.Consumer; * @param T The datatype stored in the stack. * @author Ben Culkin */ -public class Stack { - private Deque backing; - - /** - * Create a new empty stack. - * - */ - public Stack() { - backing = new LinkedList(); - } - +public abstract class Stack { /** * Push an element onto the stack. * * @param elm The element to insert. */ - public void push(T elm) { - backing.push(elm); - } + public abstract void push(T elm); /** * Pop an element off of the stack. * * @return The element on top of the stack. */ - public T pop() { - return backing.pop(); - } + public abstract T pop(); - /** - * Get the top item of the stack without removing it. - * - * @return The element on top of the stack. - */ - public T top() { - return backing.peek(); - } + public abstract T top(); /** * Get the number of elements in the stack. * * @return the number of elements in the stack. */ - public int size() { - return backing.size(); - } + public abstract int size(); /** Check if the stack is empty. * - * @return Whether or not the stack is empty + * @return Whether or not the stack is empty. + */ + public abstract boolean empty(); + + /** + * Create a spaghetti stack branching off of this one. + * + * @return A spaghetti stack with this stack as a parent. */ - public boolean empty() { - return backing.size() == 0; + public Stack spaghettify() { + return new SpaghettiStack<>(this); } /* @@ -80,7 +64,7 @@ public class Stack { */ public void drop(int n) { for(int i = 0; i < n; i++) { - backing.pop(); + pop(); } } @@ -97,11 +81,11 @@ public class Stack { * @param n The number of items below the top to delete. */ public void nip(int n) { - T elm = backing.pop(); + T elm = pop(); drop(n); - backing.push(elm); + push(elm); } /** @@ -121,12 +105,12 @@ public class Stack { List lst = new ArrayList<>(n); for(int i = n; i > 0; i--) { - lst.set(i - 1, backing.pop()); + lst.set(i - 1, pop()); } for(int i = 0; i < m; i++) { for(T elm : lst) { - backing.push(elm); + push(elm); } } } @@ -156,20 +140,20 @@ public class Stack { public void multiover(int n, int m) { List lst = new ArrayList<>(n); - T elm = backing.pop(); + T elm = pop(); for(int i = n; i > 0; i--) { - lst.set(i - 1, backing.pop()); + lst.set(i - 1, pop()); } for(T nelm : lst) { - backing.push(nelm); + push(nelm); } - backing.push(elm); + push(elm); for(int i = 1; i < m; i++) { for(T nelm : lst) { - backing.push(nelm); + push(nelm); } } } @@ -194,76 +178,76 @@ public class Stack { * Duplicate the third item in the stack. */ public void pick() { - T z = backing.pop(); - T y = backing.pop(); - T x = backing.pop(); - - backing.push(x); - backing.push(y); - backing.push(z); - backing.push(x); + T z = pop(); + T y = pop(); + T x = pop(); + + push(x); + push(y); + push(z); + push(x); } /** * Swap the top two items on the stack. */ public void swap() { - T y = backing.pop(); - T x = backing.pop(); + T y = pop(); + T x = pop(); - backing.push(y); - backing.push(x); + push(y); + push(x); } /** * Duplicate the second item below the first item. */ public void deepdup() { - T y = backing.pop(); - T x = backing.pop(); + T y = pop(); + T x = pop(); - backing.push(x); - backing.push(x); - backing.push(y); + push(x); + push(x); + push(y); } /** * Swap the second and third items in the stack. */ public void deepswap() { - T z = backing.pop(); - T y = backing.pop(); - T x = backing.pop(); + T z = pop(); + T y = pop(); + T x = pop(); - backing.push(y); - backing.push(x); - backing.push(z); + push(y); + push(x); + push(z); } /** * Rotate the top three items on the stack */ public void rot() { - T z = backing.pop(); - T y = backing.pop(); - T x = backing.pop(); + T z = pop(); + T y = pop(); + T x = pop(); - backing.push(y); - backing.push(z); - backing.push(x); + push(y); + push(z); + push(x); } /** * Inversely rotate the top three items on the stack */ public void invrot() { - T z = backing.pop(); - T y = backing.pop(); - T x = backing.pop(); + T z = pop(); + T y = pop(); + T x = pop(); - backing.push(z); - backing.push(x); - backing.push(y); + push(z); + push(x); + push(y); } /* @@ -279,13 +263,13 @@ public class Stack { List elms = new ArrayList<>(n); for(int i = n; i > 0; i--) { - elms.set(i - 1, backing.pop()); + elms.set(i - 1, pop()); } cons.accept(this); for(T elm : elms) { - backing.push(elm); + push(elm); } } @@ -320,12 +304,12 @@ public class Stack { List elms = new ArrayList<>(n); for(int i = n; i > 0; i--) { - elms.set(i - 1, backing.pop()); + elms.set(i - 1, pop()); } for(Consumer> cons : conses) { for(T elm : elms) { - backing.push(elm); + push(elm); } cons.accept(this); @@ -354,7 +338,7 @@ public class Stack { List elms = new ArrayList<>(n); for(int j = n; j > 0; j--) { - elms.set(j, backing.pop()); + elms.set(j, pop()); } nelms.set(i, elms); @@ -363,7 +347,7 @@ public class Stack { int i = 0; for(List elms : nelms) { for(T elm : elms) { - backing.push(elm); + push(elm); } conses.get(i).accept(this); -- cgit v1.2.3