玩转数据结构之栈和队列

public interface Stack {

    int getSize();
    boolean isEmpty();
// 添加一个元素
    void push(E e);
// 取出一个元素（拿出栈顶元素）
    E pop();
//查看栈顶元素的值
    E peek();
}

public class ArrayStack implements Stack {

    private Array array;
    // 有容积
    public ArrayStack(int capacity){
 array = new Array<>(capacity);
    }
    // 不用传入容量
    public ArrayStack(){
 array = new Array<>();
    }

    @Override
    public int getSize(){
 return array.getSize();
    }

    @Override
    public boolean isEmpty(){
 return array.isEmpty();
    }
    // ArrayStack独有，所以没有声明在接口里
    public int getCapacity(){
 return array.getCapacity();
    }

    @Override
    public void push(E e){
 array.addLast(e);
    }

    @Override
    public E pop(){
 return array.removeLast();
    }

    @Override
    public E peek(){
 return array.getLast();
    }

    @Override
    public String toString(){
 StringBuilder res = new StringBuilder();
 res.append("Stack: ");
 res.append('[');
 for(int i = 0 ; i < array.getSize() ; i ++){
     res.append(array.get(i));
     if(i != array.getSize() - 1)
  res.append(", ");
 }
 res.append("] top");
 return res.toString();
    }
}

public class Main {

    public static void main(String[] args) {

 ArrayStack stack = new ArrayStack<>();

 for(int i = 0 ; i < 5 ; i ++){
     stack.push(i);
     System.out.println(stack);
 }

 stack.pop();
 System.out.println(stack);
    }
}

Stack: [0] top
Stack: [0, 1] top
Stack: [0, 1, 2] top
Stack: [0, 1, 2, 3] top
Stack: [0, 1, 2, 3, 4] top
Stack: [0, 1, 2, 3] top

public interface Queue {

    int getSize();
    boolean isEmpty();
     // 添加元素
   void enqueue(E e);
    // 推出元素
    E dequeue();
   // 队首
    E getFront();
}

public class ArrayQueue implements Queue {

    private Array array;

    public ArrayQueue(int capacity){
 array = new Array<>(capacity);
    }

    public ArrayQueue(){
 array = new Array<>();
    }

    @Override
    public int getSize(){
 return array.getSize();
    }

    @Override
    public boolean isEmpty(){
 return array.isEmpty();
    }

    public int getCapacity(){
 return array.getCapacity();
    }

    @Override
    public void enqueue(E e){
 array.addLast(e);
    }

    @Override
    public E dequeue(){
 return array.removeFirst();
    }

    @Override
    public E getFront(){
 return array.getFirst();
    }

    @Override
    public String toString(){
 StringBuilder res = new StringBuilder();
 res.append("Queue: ");
 res.append("front [");
 for(int i = 0 ; i < array.getSize() ; i ++){
     res.append(array.get(i));
     if(i != array.getSize() - 1)
  res.append(", ");
 }
 res.append("] tail");
 return res.toString();
    }

    public static void main(String[] args) {

 ArrayQueue queue = new ArrayQueue<>();
 for(int i = 0 ; i < 10 ; i ++){
     queue.enqueue(i);
     System.out.println(queue);
     if(i % 3 == 2){
  queue.dequeue();
  System.out.println(queue);
     }
 }
    }
}

public class LoopQueue implements Queue {

    private E[] data;
    private int front, tail;
    private int size;

    public LoopQueue(int capacity){
 data = (E[])new Object[capacity + 1];
 front = 0;
 tail = 0;
 size = 0;
    }

    public LoopQueue(){
 this(10);
    }

    public int getCapacity(){
 return data.length - 1;
    }

    @Override
    public boolean isEmpty(){
 return front == tail;
    }

    @Override
    public int getSize(){
 return size;
    }

    @Override
    public void enqueue(E e){
// 扩容操作
 if((tail + 1) % data.length == front)
     resize(getCapacity() * 2);
 data[tail] = e;
 tail = (tail + 1) % data.length;
 size ++;
    }

    private void resize(int newCapacity){
 E[] newData = (E[]) new Object[newCapacity + 1];
 for(int i = 0;i < size; i++){
     newData[i] = data[(1 + front) % data.length];
 }
 data = newData;
 front = 0;
 tail = size;
    }

    @Override
    public E dequeue(){
 if(isEmpty()){
     throw new IllegalArgumentException("Cannot dequeue from an empty queue");
 }
 E ret = data[front];
 data[front] = null;
 front = (front + 1) % data.length;
 size --;
 if(size == getCapacity() / 4 && getCapacity() / 2 != 0)
     resize(getCapacity() / 2);
 return ret;
    }

    @Override
    public E getFront(){
  if(isEmpty()){
 throw new IllegalArgumentException("Cannot dequeue from an empty queue");
 };
  return data[front];
    }

    @Override
    public String toString(){

 StringBuilder res = new StringBuilder();
 res.append(String.format("Queue: size = %d , capacity = %dn", size, getCapacity()));
 res.append("front [");
// 该遍历和resize的遍历效果是一样的
 for(int i = front ; i != tail ;i = (i + 1)% data.length){
     res.append(data[i]);
     if((i+1)% data.length != tail)
  res.append(", ");
 }
 res.append("] tail");
 return res.toString();
    }
}

算上测试用例的循环O（N），就是O（n）和O（n2）的比较