Using Array or List to implement Queue & Stack
Stack
interface StackAPI<T> {
void push(T element);
T pop();
}
List Implementation
class MyListStack implements StackAPI<T> {
int size;
Node head;
Node tail;
public MyListStack() {
size = 0;
head = null;
tail = null;
}
@Override
public void push(int element) {
// add the element to the tail of list
if (head == null) { // initial status, no element in stack
head = new Node(element);
tail = head;
} else {
tail.next = new Node(element);
tail.next.prev = tail;
tail = tail.next;
}
size++;
}
@Override T pop() {
if (size == 0) {
return null;
}
Node res = null;
// pop the element from the head of list
if (head == tail) { // if there is only one element in list
res = head;
head = null;
tail = null;
} else {
res = tail;
tail = res.prev;
tail.next = null;
res.prev = null;
}
size--;
return res;
}
}
class Node {
int val;
Node prev;
Node next;
public Node(int i) {
this.val = i;
this.prev = null;
this.next = null;
}
}
Array Implementation
class MyArrayStack implements StackAPI {
int[] arr;
int size;
public MyArrayStack(int capacity) {
arr = new int[capacity];
size = 0;
}
@Override
public void push(int element) {
if (size == capacity) {
return;
}
arr[size++] = element;
}
@Override
public Integer pop() {
if(size == 0) {
return null;
}
return arr[--size];
}
}
Queue
interface QueueAPI<T> {
void push(T element);
T pop();
}
List Implementation
public class MyListQueue implements QueueAPI<Integer>{
@Override
public void push(int element) {
// add the element to the tail of list
if (head == null) { // initial status, no element in stack
head = new Node(element);
tail = head;
} else {
tail.next = new Node(element);
tail.next.prev = tail;
tail = tail.next;
}
size++;
}
@Override T pop() {
if (size == 0) {
return null;
}
Node res = null;
// pop the element from the head of list
if (head == tail) { // if there is only one element in list
res = head;
head = null;
tail = null;
} else {
res = head;
head = head.next;
res.next = null;
head.prev = null;
}
size--;
return res;
}
}
Array Implementation
public class MyArrayQueue implements QueueAPI<Integer> {
int[] arr;
int size;
int head;
int tail;
public MyArrayQueue(int capacity) {
arr = new int[capacity];
size = 0;
head = 0;
tail = 0;
}
@Override
public void push(Integer element) {
if(size == capacity) {
return;
}
if (tail == arr.length) {
tail = 0;
}
arr[tail++] = element;
size++;
}
@Override
public Integer pop() {
if(size == 0) {
return null;
}
if (head == arr.length) {
head = 0;
}
return arr[head++];
}
}