Stack Implementation
Stack Implementation from Linked list
/* This is wrapper class...
Objective would be to push more functionality into this Class to enforce consistent definition
*/
public abstract class Generics {
public final String masterType = "Generic";
private String type; // extender should define their data type
// generic enumerated interface
public interface KeyTypes {
String name();
}
protected abstract KeyTypes getKey(); // this method helps force usage of KeyTypes
// getter
public String getMasterType() {
return masterType;
}
// getter
public String getType() {
return type;
}
// setter
public void setType(String type) {
this.type = type;
}
// this method is used to establish key order
public abstract String toString();
// static print method used by extended classes
public static void print(Generics[] objs) {
// print 'Object' properties
System.out.println(objs.getClass() + " " + objs.length);
// print 'Generics' properties
if (objs.length > 0) {
Generics obj = objs[0]; // Look at properties of 1st element
System.out.println(
obj.getMasterType() + ": " +
obj.getType() +
" listed by " +
obj.getKey());
}
// print "Generics: Objects'
for(Object o : objs) // observe that type is Opaque
System.out.println(o);
System.out.println();
}
}
public class ConsoleMethods {
//Method to make sure no database is available in the
//input stream
private static void inputFlush() {
try {
while (System.in.available() != 0) {
}
} catch (java.io.IOException e) {
System.out.println("Input error");
}
}
public static void printChar(char txt)
{
System.out.print(txt);
}
public static void clearScreen()
{
printChar('\u000C');
}
public static void print(String txt)
{
System.out.print(txt);
}
public static void println()
{
System.out.println("\n");
}
public static void println(String txt)
{
System.out.println(txt);
}
public static void println(Object obj)
{
System.out.println(obj);
}
public static void printPrompt(String prompt) {
print(prompt + " ");
System.out.flush();
}
public static String inputString(String prompt) {
//inputFlush();
printPrompt(prompt);
return inString();
}
private static String inString() {
int aChar;
StringBuilder s = new StringBuilder();
boolean finished = false;
while (!finished) {
try {
aChar = System.in.read();
if (aChar < 0 || (char) aChar == '\n')
finished = true;
else if ((char) aChar != '\r')
s.append((char) aChar); // Enter into string
}
catch (java.io.IOException e) {
System.out.println("Input error");
finished = true;
}
}
return s.toString();
}
public static int inputInt(String prompt) {
while (true) {
inputFlush();
printPrompt(prompt);
try {
return Integer.parseInt(inString().trim());
}
catch (NumberFormatException e) {
System.out.println("Invalid input. Not an integer");
}
}
}
public static char inputChar(String prompt) {
int aChar = 0;
inputFlush();
printPrompt(prompt);
try {
aChar = System.in.read();
}
catch (java.io.IOException e) {
println("Input error");
}
inputFlush();
return (char) aChar;
}
}
/**
* Implementation of a Double Linked List; forward and backward links point to adjacent Nodes.
*
*/
public class LinkedList<T>
{
private T data;
private LinkedList<T> prevNode, nextNode;
/**
* Constructs a new element
*
* @param data, data of object
* @param node, previous node
*/
public LinkedList(T data, LinkedList<T> node)
{
this.setData(data);
this.setPrevNode(node);
this.setNextNode(null);
}
/**
* Clone an object,
*
* @param node object to clone
*/
public LinkedList(LinkedList<T> node)
{
this.setData(node.data);
this.setPrevNode(node.prevNode);
this.setNextNode(node.nextNode);
}
/**
* Setter for T data in DoubleLinkedNode object
*
* @param data, update data of object
*/
public void setData(T data)
{
this.data = data;
}
/**
* Returns T data for this element
*
* @return data associated with object
*/
public T getData()
{
return this.data;
}
/**
* Setter for prevNode in DoubleLinkedNode object
*
* @param node, prevNode to current Object
*/
public void setPrevNode(LinkedList<T> node)
{
this.prevNode = node;
}
/**
* Setter for nextNode in DoubleLinkedNode object
*
* @param node, nextNode to current Object
*/
public void setNextNode(LinkedList<T> node)
{
this.nextNode = node;
}
/**
* Returns reference to previous object in list
*
* @return the previous object in the list
*/
public LinkedList<T> getPrevious()
{
return this.prevNode;
}
/**
* Returns reference to next object in list
*
* @return the next object in the list
*/
public LinkedList<T> getNext()
{
return this.nextNode;
}
}
import java.util.Iterator;
/**
* Queue Iterator
*
* 1. "has a" current reference in Queue
* 2. supports iterable required methods for next that returns a generic T Object
*/
class QueueIterator<T> implements Iterator<T> {
LinkedList<T> current; // current element in iteration
// QueueIterator is pointed to the head of the list for iteration
public QueueIterator(LinkedList<T> head) {
current = head;
}
// hasNext informs if next element exists
public boolean hasNext() {
return current != null;
}
// next returns data object and advances to next position in queue
public T next() {
T data = current.getData();
current = current.getNext();
return data;
}
}
/**
* Queue: custom implementation
* @author John Mortensen
*
* 1. Uses custom LinkedList of Generic type T
* 2. Implements Iterable
* 3. "has a" LinkedList for head and tail
*/
public class Stack<T> {
LinkedList<T> head = null;
public T peek() {
if (head == null)
return null;
else
return head.getData();
}
public void push(T data)
{
head = new LinkedList<>(data, head);
}
public T pop()
{
T data = null; // empty condition
if (head != null) {
data = head.getData();
head = head.getPrevious(); // stack is overwritten with next item
}
return data; // pop always returns data of element popped
}
public String toString()
{
StringBuilder stackToString = new StringBuilder("[");
LinkedList<T> node = head; // start from the back
while (node != null)
{
stackToString.append(node.getData()); // append the database to output string
node = node.getPrevious(); // go to previous node
if (node != null)
stackToString.append(", ");
} // loop 'till you reach the beginning
stackToString.append("]");
return stackToString.toString();
}
}
class StackDriver<T> {
static public boolean DEBUG = false;
private String title;
public final Stack<T> stack = new Stack<>(); // stack object
public int count;
/**
* Stack constructor
*
* @param title name associated with stack
* @param seriesOfObjects data to be inserted into stack
*/
@SafeVarargs
public StackDriver(String title, T[]... seriesOfObjects) {
this.title = title;
this.addList(seriesOfObjects);
}
/**
* Add a series of data object to the Stack
*
* @param seriesOfObjects data to be inserted into stack
*/
@SafeVarargs
public final void addList(T[]... seriesOfObjects)
{
if (DEBUG) ConsoleMethods.println("Add " + title);
for (T[] objects: seriesOfObjects)
for (T data : objects) {
this.stack.push(data);
this.count++;
if (DEBUG) ConsoleMethods.println("Push: " + this.stack.peek() + " " + this.stack);
}
if (DEBUG) ConsoleMethods.println();
}
/**
* Empty or remove all data objects from the Stack
*
*/
public void emptyStack()
{
if (DEBUG) ConsoleMethods.println("Delete " + title);
while (this.stack.peek() != null) {
T data = this.stack.pop();
if (DEBUG) ConsoleMethods.println("Pop: " + data + " " + stack);
}
if (DEBUG) ConsoleMethods.println();
}
/**
* Print analytics from the Stack
*
*/
public void printStack()
{
ConsoleMethods.println("Size: " + count);
ConsoleMethods.println("Top Element: " + stack.peek());
ConsoleMethods.println("Full Stack: " + stack);
ConsoleMethods.println();
}
}
class Main {
/**
* Test Stack functionality using different types of Objects
*
*/
public static void main(String[] args) {
// Create Stack of Integers
StackDriver.DEBUG = false;
Object[] numbers = new Integer[] { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
StackDriver<Object> sNums = new StackDriver<>("Integers", numbers );
sNums.printStack();
sNums.stack.push(11);
sNums.printStack();
sNums.stack.pop();
sNums.printStack();
}
}
Main.main(null);
import java.util.Iterator;
/**
* Queue Iterator
*
* 1. "has a" current reference in Queue
* 2. supports iterable required methods for next that returns a generic T Object
*/
class QueueIterator<T> implements Iterator<T> {
LinkedList<T> current; // current element in iteration
// QueueIterator is pointed to the head of the list for iteration
public QueueIterator(LinkedList<T> head) {
current = head;
}
// hasNext informs if next element exists
public boolean hasNext() {
return current != null;
}
// next returns data object and advances to next position in queue
public T next() {
T data = current.getData();
current = current.getNext();
return data;
}
}
/**
* Queue: custom implementation
* @author John Mortensen
*
* 1. Uses custom LinkedList of Generic type T
* 2. Implements Iterable
* 3. "has a" LinkedList for head and tail
*/
public class Queue<T> implements Iterable<T> {
LinkedList<T> head = null, tail = null;
/**
* Add a new object at the end of the Queue,
*
* @param data, is the data to be inserted in the Queue.
*/
public void add(T data) {
// add new object to end of Queue
LinkedList<T> tail = new LinkedList<>(data, null);
if (this.head == null) // initial condition
this.head = this.tail = tail;
else { // nodes in queue
this.tail.setNextNode(tail); // current tail points to new tail
this.tail = tail; // update tail
}
}
/**
* Returns the data of head.
*
* @return data, the dequeued data
*/
public T delete() {
T data = this.peek();
if (this.tail != null) { // initial condition
this.head = this.head.getNext(); // current tail points to new tail
if (this.head != null) {
this.head.setPrevNode(tail);
}
}
return data;
}
/**
* Returns the data of head.
*
* @return this.head.getData(), the head data in Queue.
*/
public T peek() {
return this.head.getData();
}
/**
* Returns the head object.
*
* @return this.head, the head object in Queue.
*/
public LinkedList<T> getHead() {
return this.head;
}
/**
* Returns the tail object.
*
* @return this.tail, the last object in Queue
*/
public LinkedList<T> getTail() {
return this.tail;
}
public boolean isEmpty() {
if ((this.getHead() == null) && (this.getTail() == null)) {
return true;
}
else {
return false;
}
}
public int getSize() {
int size = 0;
for (T data : this)
size += 1;
return size;
}
/**
* Returns the iterator object.
*
* @return this, instance of object
*/
public LinkedList<T> next() {
LinkedList<T> next = this.head.getNext();
this.head = next;
return next;
}
public static <T extends Comparable<T>> int compare(T x, T y) {
return x.compareTo(y);
}
public Iterator<T> iterator() {
return new QueueIterator<>(this.head);
}
}
/**
* Queue Manager
* 1. "has a" Queue
* 2. support management of Queue tasks (aka: titling, adding a list, printing)
*/
class QueueManager<T> {
// queue data
private final String name; // name of queue
private int count = 0; // number of objects in queue
public final Queue<T> queue = new Queue<>(); // queue object
/**
* Queue constructor
* Title with empty queue
*/
public QueueManager(String name) {
this.name = name;
}
/**
* Queue constructor
* Title with series of Arrays of Objects
*/
public QueueManager(String name, T[]... seriesOfObjects) {
this.name = name;
this.addList(seriesOfObjects);
}
/**
* Add a list of objects to queue
*/
public void addList(T[]... seriesOfObjects) { //accepts multiple generic T lists
for (T[] objects: seriesOfObjects)
for (T data : objects) {
this.queue.add(data);
this.count++;
}
}
/**
* Print any array objects from queue
*/
public void printQueue() {
System.out.println(this.name + " count: " + count);
System.out.print(this.name + " data: ");
for (T data : queue)
System.out.print(data + " ");
System.out.println();
}
}
class StackReverse {
public static void main(String[] args) {
// Initializing the queue
int[] primitiveArr = new int[] {5, 1, 4, 3, 7, 2};
int len = primitiveArr.length;
Integer[] objectArr = new Integer[len];
for(int i = 0; i < len; i++) {
objectArr[i] = Integer.valueOf(primitiveArr[i]);
}
StackDriver<Object> sNums = new StackDriver<>("Integers", objectArr);
Integer[] numbers = new Integer[] {};
QueueManager sorted = new QueueManager("Sorted", numbers);
for (int i = 0; i < len; i++) {
sorted.queue.add((Integer) sNums.stack.pop());
}
sorted.printQueue();
}
}
StackReverse.main(null);