标签：sar reads his alt most 复杂 object htm base
前言
栈（Stack）是一种后进先出的数据结构，仅允许在栈顶插入、删除、读取。队列（Queue）是一种先进先出的数据结构，队头读取、删除，队尾插入。
使用数组实现栈
使用到的MyArrayList和MyLinkedList详情请查看 java实现一个自己的ArrayList和LinkedList
public interface Stack {
/**
* 栈是否为空
*/
boolean isEmpty();
/**
* 栈顶添加元素
*/
void push(E e);
/**
* 栈顶删除元素
*/
E pop();
/**
* 查询栈顶元素
*/
E peek();
}
定义栈的接口
/**
* 使用数组实现栈
*/
public class ArrayStack implements Stack {
/**
* 代理对象
*/
private List delegate;
public ArrayStack(int capacity) {
delegate = new MyArrayList(capacity);
}
public ArrayStack() {
delegate = new MyArrayList();
}
@Override
public boolean isEmpty() {
return delegate.isEmpty();
}
@Override
public void push(E e) {
delegate.add(e);
}
@Override
public E pop() {
return delegate.remove(delegate.size() - 1);
}
@Override
public E peek() {
return delegate.get(delegate.size() - 1);
}
@Override
public String toString() {
return delegate.toString();
}
}
使用链表实现栈
/**
* 使用链表实现栈
*/
public class LinkedStack implements Stack {
private List delegate;
public LinkedStack() {
delegate = new MyLinkedList();
}
@Override
public boolean isEmpty() {
return delegate.isEmpty();
}
@Override
public void push(E e) {
delegate.add(e);
}
@Override
public E pop() {
return delegate.remove(delegate.size() - 1);
}
@Override
public E peek() {
return delegate.get(delegate.size() - 1);
}
@Override
public String toString() {
return delegate.toString();
}
}
使用数组实现队列
public interface Queue {
/**
* 队列是否为空
*/
boolean isEmpty();
/**
* 入队
*/
void enqueue(E e);
/**
* 出队
*/
E dequeue();
/**
* 查询队头元素
*/
E peek();
}
定义接口
/**
* 使用数组实现队列
*/
public class ArrayQueue implements Queue {
/**
* 代理对象
*/
private List delegate;
public ArrayQueue(int capacity) {
delegate = new MyArrayList(capacity);
}
public ArrayQueue() {
delegate = new MyArrayList();
}
@Override
public boolean isEmpty() {
return delegate.isEmpty();
}
@Override
public void enqueue(E e) {
delegate.add(e);
}
@Override
public E dequeue() {
return delegate.remove(0);
}
@Override
public E peek() {
return delegate.get(0);
}
@Override
public String toString() {
return delegate.toString();
}
}
使用链表实现队列
/**
* 使用链表实现队列
*/
public class LinkedQueue implements Queue {
/**
* 代理对象
*/
private List delegate;
public LinkedQueue() {
delegate = new MyLinkedList();
}
@Override
public boolean isEmpty() {
return delegate.isEmpty();
}
@Override
public void enqueue(E e) {
delegate.add(e);
}
@Override
public E dequeue() {
return delegate.remove(0);
}
@Override
public E peek() {
return delegate.get(0);
}
@Override
public String toString() {
return delegate.toString();
}
}
使用数组实现循环队列
对于使用数组实现的队列来说，每次出队都需要将所有队头之后的元素往前移动一位，时间复杂度为O(n)，这种情况我们可以使用循环队列来优化，
使用两个指针表示队头(front)和队尾(rear)，每次出队不移动元素，只移动队头指针。
为了区分队空和队满的情况，有两种处理方式，
size == 0 表示队空
size == capacity 表示队满
front == tail 表示队空
(tail + 1) % capacity == front 表示队满
(tail - front + capacity) % capacity 为实际容量
第一种方式
/**
* 使用数组实现循环队列
*/
public class LoopQueue implements Queue {
/**
* 数组容器
*/
private Object[] data;
/**
* 队头和队尾指针
*/
private int front, tail;
/**
* 队列实际容量
*/
private int size;
public LoopQueue(int capacity) {
data = new Object[capacity];
front = 0;
tail = 0;
size = 0;
}
public LoopQueue() {
this(10);
}
private int capacity() {
return data.length;
}
@Override
public boolean isEmpty() {
return size == 0;
}
@Override
public void enqueue(E e) {
int oldCapacity = capacity();
if (size == oldCapacity) {
//扩容1.5倍
resize(oldCapacity + (oldCapacity >> 1));
}
data[tail] = e;
tail = inc(tail + 1);
size++;
}
@Override
public E dequeue() {
rangeCheck();
E ret = front();
data[front] = null;
front = inc(front + 1);
size--;
int capacity = capacity();
//在实际容量为总容量的4分之一时缩容
if (size == (capacity >> 2) && (capacity >> 1) != 0) {
//缩容2分之1
resize(capacity >> 1);
}
return ret;
}
private E front() {
return (E) data[front];
}
@Override
public E peek() {
rangeCheck();
return front();
}
private void resize(int newCapacity) {
Object[] newData = new Object[newCapacity];
for (int i = 0; i
第二种方式
/**
* 使用数组实现循环队列
*/
public class LoopQueueWithoutSize implements Queue {
/**
* 数组容器
*/
private Object[] data;
/**
* 队头和队尾指针
*/
private int front, tail;
public LoopQueueWithoutSize(int capacity) {
/**
* 在需要的容量上增加一个容量
*/
data = new Object[capacity + 1];
front = 0;
tail = 0;
}
public LoopQueueWithoutSize() {
this(10);
}
private int capacity() {
return data.length - 1;
}
@Override
public boolean isEmpty() {
return size() == 0;
}
private int size() {
return inc(tail + data.length - front);
}
@Override
public void enqueue(E e) {
int oldCapacity = capacity();
if (size() == oldCapacity) {
//扩容1.5倍
resize(oldCapacity + (oldCapacity >> 1));
}
data[tail] = e;
tail = inc(tail + 1);
}
@Override
public E dequeue() {
rangeCheck();
E ret = front();
data[front] = null;
front = inc(front + 1);
//在实际容量为总容量的4分之一时缩容
int capacity = capacity();
if (size() == (capacity >> 2) && (capacity >> 1) != 0) {
//缩容2分之1
resize(capacity >> 1);
}
return ret;
}
private E front() {
return (E) data[front];
}
@Override
public E peek() {
rangeCheck();
return front();
}
private void resize(int newCapacity) {
Object[] newData = new Object[newCapacity + 1];
int size = size();
for (int i = 0; i
jdk也提供了一个数组实现的循环队列ArrayDeque，就是使用第二种方式实现的
/**
* Resizable-array implementation of the {@link Deque} interface. Array
* deques have no capacity restrictions; they grow as necessary to support
* usage. They are not thread-safe; in the absence of external
* synchronization, they do not support concurrent access by multiple threads.
* Null elements are prohibited. This class is likely to be faster than
* {@link Stack} when used as a stack, and faster than {@link LinkedList}
* when used as a queue.
*
* Most {@code ArrayDeque} operations run in amortized constant time.
* Exceptions include
* {@link #remove(Object) remove},
* {@link #removeFirstOccurrence removeFirstOccurrence},
* {@link #removeLastOccurrence removeLastOccurrence},
* {@link #contains contains},
* {@link #iterator iterator.remove()},
* and the bulk operations, all of which run in linear time.
*
*
The iterators returned by this class‘s {@link #iterator() iterator}
* method are fail-fast: If the deque is modified at any time after
* the iterator is created, in any way except through the iterator‘s own
* {@code remove} method, the iterator will generally throw a {@link
* ConcurrentModificationException}. Thus, in the face of concurrent
* modification, the iterator fails quickly and cleanly, rather than risking
* arbitrary, non-deterministic behavior at an undetermined time in the
* future.
*
*
Note that the fail-fast behavior of an iterator cannot be guaranteed
* as it is, generally speaking, impossible to make any hard guarantees in the
* presence of unsynchronized concurrent modification. Fail-fast iterators
* throw {@code ConcurrentModificationException} on a best-effort basis.
* Therefore, it would be wrong to write a program that depended on this
* exception for its correctness: the fail-fast behavior of iterators
* should be used only to detect bugs.
*
*
This class and its iterator implement all of the
* optional methods of the {@link Collection} and {@link
* Iterator} interfaces.
*
*
This class is a member of the
*
* Java Collections Framework.
*
* @author Josh Bloch and Doug Lea
* @param the type of elements held in this deque
* @since 1.6
*/
public class ArrayDeque extends AbstractCollection
implements Deque, Cloneable, Serializable {
/**
* 数组容器
*/
transient Object[] elements;
/**
* 队头指针
*/
transient int head;
/**
* 队尾指针
*/
transient int tail;
/**
* 队列实际容量
*/
public int size() {
return sub(tail, head, elements.length);
}
/**
* 计算实际容量
*/
static final int sub(int i, int j, int modulus) {
if ((i -= j)
两种队列性能对比
我们简单对比一下我们自己实现的ArrayQueue和LoopQueue
import java.util.Random;
public class Main {
// 测试使用运行opCount个enqueue和dequeue操作所需要的时间，单位：秒
private static double testQueue(Queue q, int opCount) {
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");
Queue loopQueue = new LoopQueue();
double time2 = testQueue(loopQueue, opCount);
System.out.println("LoopQueue, time: " + time2 + " s");
}
}
运行结果为
ArrayQueue, time: 0.520611 s
LoopQueue, time: 0.0196162 s
可以看到循环队列的优势还是很明显的。
java使用数组和链表实现栈和队列
标签：sar reads his alt most 复杂 object htm base
原文地址：https://www.cnblogs.com/strongmore/p/14203303.html