- 栈的基本功能：
public interface Stack<E> {
int getSize();
boolean isEmpty();
void push(E e);
E pop();
E peek();
}- 基于动态数组的栈的实现
public class ArrayStack<E> implements Stack<E>{
Array<E> 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();
}
@Override
public void push(E e) {
array.addLast(e);
}
@Override
public E pop() {
return array.removeLast();
}
@Override
public E peek() {
E ele=array.get(array.getSize()-1);
return ele;
}
public int getCapacity(){
return array.getCapacity();
}
@Override
public String toString() {
StringBuilder ret=new StringBuilder();
ret.append("Stack: ");
ret.append("[");
for(int i=0;i<array.getSize();i++){
ret.append(array.get(i));
if(i!=array.getSize()-1){
ret.append(", ");
}
}
ret.append("] top");
return ret.toString();
}
}| 操作 | 时间复杂度 |
|---|---|
| push(E) | 均摊时间复杂度：O(1) |
| pop() | 均摊时间复杂度：O(1) |
| peek() | O(1) |
| getSize() | O(1) |
| isEmpty() | O(1) |
-
队列是一种线性结构
-
相比数组，队列对应的操作是数组的子集
-
只能从一端(队尾)添加元素，只能从另一端(队首)取出元素
public interface Queue<E> {
void enqueue(E e);
E dequeue();
E getFront();
int getSize();
boolean isEmpty();
}/**
* 基于动态数组的队列的实现
*/
public class ArrayQueue<E> implements Queue<E>{
Array<E> 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();
}
@Override
public void enqueue(E e) {
array.addLast(e);
}
@Override
public E dequeue() {
return array.removeFirst();
}
@Override
public E getFront() {
return array.get(0);
}
@Override
public String toString() {
StringBuilder ret=new StringBuilder();
ret.append("Queue: ");
ret.append("front [");
for(int i=0;i<array.getSize();i++){
ret.append(array.get(i));
if(i!=array.getSize()-1){
ret.append(", ");
}
}
ret.append("] tail");
return ret.toString();
}
}| 操作 | 时间复杂度 |
|---|---|
| enqueue(e) | 均摊时间复杂度：O(1) |
| dequeue() | O(n) |
| front() | O(1) |
| getSize() | O(1) |
| isEmpty() | O(1) |
-
数组队列的问题
出队操作，要移动数据，时间复杂度是O(n)
- 循环队列
队列为空判断条件：
front == tail队列为满判断条件：
(tail + 1) % data.length == front 动态调整数组大小的resize函数：
private void resize(int newCapacity) {
//预留一个位置，用来判断队列是否已满
E[] newData=(E[])new Object[newCapacity+1];
for(int i=0;i<size;i++){
//将原来循环队列中数据复制到新数组，原来的data数据是从 font开始的
//复制到数组，新数组是从0小标开始的
newData[i]=data[(i+front)%data.length];
}
data=newData;
front=0;
tail=size;
}public class LoopQueue<E> implements Queue<E>{
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 int getSize() {
return size;
}
@Override
public boolean isEmpty() {
return front==tail;
}
@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("con not dequeue from 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("con not dequeue from empty queue");
}
return data[front];
}
private void resize(int newCapacity) {
E[] newData=(E[])new Object[newCapacity+1];
for(int i=0;i<size;i++){
newData[i]=data[(i+front)%data.length];
}
data=newData;
front=0;
tail=size;
}
@Override
public String toString() {
StringBuilder ret=new StringBuilder();
ret.append(String.format("LooPQueue: size=%d,capacity=%d\n",size,getCapacity()));
ret.append("font [");
for(int i=front;i!=tail;i=(i+1)%data.length){
ret.append(data[i]);
if((i+1)%data.length!=tail){
ret.append(", ");
}
}
ret.append("] tail");
return ret.toString();
}
}| 操作 | 时间复杂度 |
|---|---|
| enqueue(e) | 均摊时间复杂度：O(1) |
| dequeue() | 均摊时间复杂度：O(1) |
| front() | O(1) |
| getSize() | O(1) |
| isEmpty() | O(1) |
public class Main {
public static void main(String[] args) {
int opCount=100000;
ArrayQueue<Integer> arrayQueue=new ArrayQueue<>();
double t1=testQueue(arrayQueue,opCount);
System.out.println("Array Queue time:"+t1+"s");
LoopQueue<Integer> loopQueue=new LoopQueue<>();
double t2=testQueue(loopQueue,opCount);
System.out.println("Loop Queue time:"+t2+"s");
}
//测试使用q运行opCount个enqueue和dequeue操作所需要的时间，单位：秒
private static double testQueue(Queue<Integer> q,int opCount){
long startTime=System.nanoTime();
Random random=new Random();
for(int i=0;i<opCount;i++){
q.enqueue(random.nextInt(Integer.MAX_VALUE));
}
for(int i=0;i<opCount;i++){
q.dequeue();
}
long endTime=System.nanoTime();
return (endTime-startTime)/1000000000.0;
}
}