Skip to content

Instantly share code, notes, and snippets.

@benknoble
Created March 7, 2017 17:20
Show Gist options
  • Save benknoble/e1b1e3073e5ae0ac037f7cf7777a7993 to your computer and use it in GitHub Desktop.
Save benknoble/e1b1e3073e5ae0ac037f7cf7777a7993 to your computer and use it in GitHub Desktop.
Array-based Stack in java demonstrating $O(1)$ time per operation
public class ArrayStack<T> {
private T[] array;
private int top = -1;
private static final int MAX_SIZE = 1000000;
public ArrayStack() {
array = (T[])(new Object[MAX_SIZE]);//'cause generics
}
public void push(T t) {
array[++top] = t;
}
public void pop() {
if (!isEmpty())
--top;
}
public T top() {
if (!isEmpty())
return array[top];
return null;//or throw exception
}
public int size() {
return top + 1;//because the 0th element means size is 1, -1 means size is 0
}
public boolean isEmpty() {
return size() == 0;
}
public void clear() {
top = -1;
}
public static void main(String[] args) {
int[] sizes = new int[] { 1,2,4,8,16,32,64,128,256,1024,2048 };
ArrayStack<Integer> intStack = new ArrayStack<>();
for (int size : sizes) {
for (int i = size; i>=1; i--) {
intStack.push(i);
}
System.out.println("Size expected: " + size + " Size actual: " + intStack.size());
for (int i = 1; i <= size; i++) {
System.out.println("Element " + i + ": " + intStack.top());
intStack.pop();
}
System.out.println("Empty? " + intStack.isEmpty());
intStack.clear();
}
}
}
@heyCarlH
Copy link

heyCarlH commented Mar 8, 2017

Thanks! But for a queue's clear method, is it right that linked cell can still have O(1) while array implementation cannot?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment