Skip to content

Instantly share code, notes, and snippets.

@AlexFrazer
Created October 10, 2012 23:39
Show Gist options
  • Save AlexFrazer/3869239 to your computer and use it in GitHub Desktop.
Save AlexFrazer/3869239 to your computer and use it in GitHub Desktop.
Stacks and Queues
/**
* Array Queue class
* Takes data into an array. The first item to enter is the first to
* be returned. This is the opposite of a Queue.
*
* @Alex Frazer
*/
import java.util.Random;
public class ArrayQueue<T>
{
/**My initial array, and my implicit pointer to the last thing I referenced in the array*/
Object[] DataArray = new Object[10];
int FrontIndex=-1;
int BackIndex=0;
public void enqueue(T data) {
/**check if the array is big enough. If not, create a new array of twice the size and move the variables in there*/
if(FrontIndex >= (BackIndex + DataArray.length - FrontIndex + 1) % DataArray.length) {
Object[] newArray = new Object[DataArray.length*2];
for(int i=0; i<DataArray.length; i++) {
newArray[i] = DataArray[i];
}
DataArray = newArray;
}
/**after that, add the data to the array in it's correct spot*/
DataArray[++FrontIndex] = data;
}
public Object dequeue() {
/**saves the Object which I am trying to return as a variable*/
Object tmp = DataArray[0];
/** this loop shifts everything one index over */
for(int i=0; i<DataArray.length-1; i++) {
DataArray[i] = DataArray[i+1];
}
/**the end needs to be set in value*/
DataArray[DataArray.length-1] = null;
/**Decreases the size of the array, given it's twice as big as it needs to be*/
if(DataArray.length/2 < (BackIndex + DataArray.length - FrontIndex + 1) % DataArray.length) {
Object[] newArray2 = new Object[DataArray.length/2];
for(int i=0; i<newArray2.length; i++) {
newArray2[i] = DataArray[i];
}
DataArray = newArray2;
}
/**returns the tmp variable, which was the object to be removed from the queue*/
return tmp;
}
public static void main(String[] args) {
ArrayQueue Queue = new ArrayQueue();
}
}
import java.util.Random;
public class ArrayStack<T>
{
Object[] DataArray = new Object[10];
int FrontIndex=-1;
int BackIndex=0;
public void push(T data) {
if(FrontIndex >= (BackIndex + DataArray.length - FrontIndex + 1) % DataArray.length) {
Object[] newArray = new Object[DataArray.length*2];
for(int i=0; i<DataArray.length; i++) {
newArray[i] = DataArray[i];
}
DataArray = newArray;
}
DataArray[++FrontIndex] = data;
}
public Object pop() {
Object tmp = DataArray[FrontIndex];
DataArray[FrontIndex]=null;
if(DataArray.length/2 < (BackIndex + DataArray.length - FrontIndex + 1) % DataArray.length) {
Object[] newArray2 = new Object[DataArray.length/2];
for(int i=0; i<newArray2.length; i++) {
newArray2[i] = DataArray[i];
}
DataArray = newArray2;
}
if(FrontIndex>=0) {
FrontIndex--;
} else {
System.out.println("Your stack is empty");
System.exit(0);
}
return tmp;
}
public void print() {
for(int i=0; i<DataArray.length; i++) {
System.out.print(DataArray[i] + " ");
}
}
public static void main(String[] args) {
ArrayStack stack = new ArrayStack();
}
}
import java.util.Random;
public class ListQueue<AnyType>
{
public class ListNode
{
AnyType data;
ListNode next;
public ListNode(AnyType data, ListNode next)
{
this.data = data;
this.next = next;
}
}
ListNode back;
ListNode front;
public ListQueue()
{
front = new ListNode(null, null);
back = new ListNode(null, null);
}
public void enqueue(AnyType data)
{
if(back.data == null)
{
back = (new ListNode(data, back.next));
front = back;
}
else
{
back.next = (new ListNode(data, back.next));
back = back.next;
}
//back = (new ListNode(data, back.next));
//top = top.next;
//top.next = data;
}
public AnyType dequeue()
{
if(front == null)
{
System.out.println("queue is empty");
return null; //THIS MIGHT CAUSE NULL POINTER EXCEPTION
}
AnyType tmp = front.data;
front = front.next;
return tmp;
}
public void print()
{
ListNode current = front;
//ListNode current = back;
while(current != null)
{
System.out.println(current.data);
current = current.next;
}
}
public static void main(String args[])
{
}
}
/**
* A LinkedList implementation of a stack.
*/
import java.util.Random;
public class ListStack<AnyType>
{
public class ListNode
{
AnyType data;
ListNode next;
public ListNode(AnyType data, ListNode next)
{
this.data = data;
this.next = next;
}
}
ListNode top;
public ListStack()
{
top = new ListNode(null, null);
}
public void push(AnyType data)
{
top = (new ListNode(data, top));
}
public AnyType pop()
{
if(top == null)
{
System.out.println("Stack is empty");
return null; //THIS MIGHT CAUSE NULL POINTER EXCEPTION
}
AnyType tmp = top.data;
top = top.next;
return tmp;
}
public void print()
{
ListNode current = top;
while(current != null)
{
System.out.println(current.data);
current = current.next;
}
}
public static void main(String args[])
{
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment