Java数据类型Stack栈、Queue队列、数组队列和循环队列的比较

Java数据类型Stack栈、Queue队列、数组队列和循环队列的比较

判断括号是否匹配：调用java本身

import java.util.Stack;public class Solution { public boolean isValid(String s){ Stack stack=new Stack<>(); for(int i=0;i

调用自己写的：

接口：

public interface Stack { int getSize(); boolean isEmpty(); void push(E e); E pop(); E peek();}

实现方法：

public class ArrayStack implements Stack { 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(); } 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

队列也是一种线性结构

相比数组，队列对应的操作是数组的子集

只能从一端（队尾）添加元素，只能从另一端（队首）取出元素

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 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++; } @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]; } private void resize(int newCapacity){ E[] newData=(E[])new Object[newCapacity+1]; for(int i=0;i queue=new LoopQueue<>(); 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 Main { //测试使用q运行opCount个enqueueu和dequeue操作所需要的时间，单位 秒 private static double testQueue(Queue q,int opCout){ long startTime=System.nanoTime(); Random random=new Random(); for( int i=0;i arrayQueue=new ArrayQueue<>(); double time1=testQueue(arrayQueue, opCount); System.out.println("ArrayQueue,time: "+time1+" s"); LoopQueue loopQueue=new LoopQueue<>(); double time2=testQueue(loopQueue, opCount); System.out.println("ArrayQueue,time: "+time2+" s"); } }

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。