在JDK中,Java Stack类是vector的一个子类,继承vector,在util包下。并且只定义了默认构造方法,大部分方法的实现也来源于vector。
public class Stack<E> extends Vector<E> {}
public class ArrayStack{
private static final int DEFAULT_CAPACITY = 100; //栈的默认容量
private Object[] arrStack; //实现栈的数组
private int topOfStack; //栈顶
//栈的初始化
public ArrayStack(){
arrStack = new Object[DEFAULT_CAPACITY];
topOfStack = -1;
}
//栈空判断
public boolean isEmpty(){
return topOfStack == -1;
}
//栈满判断
public boolean isFull(){
return topOfStack == DEFULT_CAPACITY - 1;
}
//入栈
public void push(Object o){
if(isFull()){
throw new RuntimeException("栈满");
}
arrStack[topOfStack++] = o;
}
//出栈
public Object pop(){
if(isEmpty()){
throw new RuntimeException("栈空");
}
return arrStack[topOfStack--];
}
}
在JDK中,队列是collection的一个子类
设front指向队头元素,rear指向队尾元素,那么
队空条件:front = rear = -1;
入队操作:队不满时,队尾rear指针向后移一位,再将值放入队尾,即++rear;
出队操作:队非空时,队头指针向后移动一位,再从队头取值,即++front;
class ArrayQueue{
private Object[] arrQueue;
private int front;
private int rear;
private int maxSize;
//构造函数初始化
public ArrayQueue(){
arrQueue = new Object[maxSize];
front = -1;
rear = -1;
}
//判断队列是否已满
public boolean isFull(){
return rear == this.maxSize - 1;
}
//判断队列是否为空
public boolean isEmpty(){
return rear == front;
}
//入队
public void EnQueue(Object o){
if(isFull()){
throw new RuntimeException("队列已满");
}
arrQueue[++rear] = o;
}
//出队
public Object DeQueue(){
if(isEmpty()){
throw new RuntimeException("队列为空");
}
return arrQueue[++front];
}
}
在上面的顺序队列中,能否通过rear == maxSize - 1 来判断数组中元素是否已满?答案是不能,如图,此时已经不能再插入新的元素,然而在数组左侧仍然有空位,这就是顺序队列中的假溢出
因此,就引出了循环队列,将存储队列元素的数组表从逻辑上看成一个环,当队头front = maxSize -1后,再前进一格位置就到达数组的0位,节约了内存空间。
队空条件:front = rear;
队满条件:(rear + 1) % maxSize == front;
入队操作:rear = (rear + 1) % maxSize;
出队操作:front = (front + 1) % maxSize;
队列长度:(rear + maxsize - front) % maxSize;
class CircleQueue{
private Object[] arrQueue;
private int front;
private int rear;
private int maxSize;
//构造函数初始化
public CircleQueue(){
arrQueue = new Object[maxSize];
front = 0;
rear = 0;
}
//判断队列是否已满
public boolean isFull(){
return (rear + 1) % maxSize == front;
}
//判断队列是否为空
public boolean isEmpty(){
return rear == front;
}
//入队
public void EnQueue(Object o){
if(isFull()){
throw new RuntimeException("队列已满");
}
arrQueue[rear] = o;
rear = (rear + 1) % maxSize;
}
//出队
public Object DeQueue(){
if(isEmpty()){
throw new RuntimeException("队列为空");
}
Object value = arrQueue[front];
front = (front + 1) % maxSize;
return value;
}
//队列长度
public int len(){
if(isEmpty()){
return 0;
}
return (rear + maxSize - front ) % maxSize;
}
}