1. 栈 Stack
1.1 栈的特点
- 栈是一种线性结构
- 只能从一端添加元素,也只能从同一端(栈顶)取出元素
- 后进先出(Last In First Out,LIFO)
1.2 栈的应用
1.3 栈的实现
栈应该具有的功能: 1)入栈,void push(E,e) 2)出栈,E pop() 3)返回栈顶元素,E peek() 4)判断栈是否为空,boolean isEmpty() 5)返回栈中元素个数,int getSize()
-
定义支持泛型的栈接口 public interface Stack<E> {
int getSize();
boolean isEmpty();
E peek();
E pop();
void push(E e);
-
定义动态数组以存储栈内元素: public class DynamicArray<E> {
private E[] data;
private int size;
// 构造函数,传入数组的容量
public DynamicArray(int capacity) {
data = (E[])new Object[capacity];
size = 0;
}
// 空构造,默认数组容量capacity=10
public DynamicArray() {
this(10);
}
// 获取数组的容量
public int getCapacity(){
return data.length;
}
// 获取数组中元素个数
public int getSize(){
return size;
}
// 返回数组是否为空
public boolean isEmpty() {
return size == 0;
}
// 向所有元素后添加一个新元素
public void addLast(E e) {
// if(size == data.length) {
// throw new IllegalArgumentException("AddLast failed. Array is full.");
// }
//
// data[size] = e;
// size++;
add(size,e);
}
// 向所有元素前添加一个新元素
public void addFirst(E e) {
add(0,e);
}
// 向指定位置插入一个新元素e
public void add(int index,E e) {
if(index<0 || index > size) {
throw new IllegalArgumentException("Add failed. Require index >= 0 and index <= size.");
}
// 如果存储数据长度已超过数组容量,则扩容
if(size == data.length)
resize(2*data.length);
for(int i = size - 1;i>=index;i--) {
data[i+1] = data[i];
}
data[index] = e;
size ++;
}
private void resize(int newCapacity) {
E newData[] = (E[])new Object[newCapacity];
for(int i = 0;i<size;i++) {
newData[i] = data[i];
}
data = newData;
}
// 获取index索引位置的元素
public E get(int index) {
if(index <0 || index >=size) {
throw new IllegalArgumentException("Get failed. Index is illegal.");
}
return data[index];
}
// 修改index索引位置的元素为e
public void set(int index,E e) {
if(index <0 || index >=size) {
throw new IllegalArgumentException("Set failed. Index is illegal.");
}
data[index] = e;
}
// 查找数组中是否包含元素e
public boolean contains(E e) {
for(int i = 0;i<size;i++) {
if (data[i].equals(e))
return true;
}
return false;
}
// 查找数组中元素e所在的索引,如果不存在元素e,则返回-1
public int find(E e) {
for(int i = 0;i<size;i++) {
if (data[i].equals(e))
return i;
}
return -1;
}
// 从数组中删除index索引位置的元素,返回删除的元素
public E remove(int index) {
if(index<0 || index > size) {
throw new IllegalArgumentException("Remove failed. Index is illegal.");
}
E ret = data[index];
for(int i = index + 1;i<size;i++) {
data [i - 1] = data[i];
}
size--;
data[size] = null;
// 如果存储数据的个数已小于容量的一半,则缩减容量
// 惰性,如果存储数据的个数已小于容量的1/4,则缩减一半容量
if(size==data.length/4) {
resize(data.length/2);
}
return ret;
}
// 从数组中删除第一个元素,返回删除的元素
public E removeFirst() {
return remove(0);
}
// 从数组中删除最后元素,返回删除的元素
public E removeLast() {
return remove(size-1);
}
// 从数组删除元素e
public void removeElement(E e) {
int index = find(e);
if(index != -1)
remove(index);
}
@Override
public String toString() {
StringBuilder res = new StringBuilder();
res.append(String.format("Array: size = %d,capacity = %d n",size,data.length));
res.append('[');
for(int i = 0;i<size;i++) {
res.append(data[i]);
if(i!=size -1)
res.append(",");
}
res.append(']');
return res.toString();
}
public E getLast() {
return get(size-1);
}
public E getFirst() {
return get(0);
}
}
-
基于动态数组,实现数组栈 public class ArrayStack<E> implements Stack<E> {
DynamicArray<E> Array;
public ArrayStack(int capacity) {
Array = new DynamicArray<>(capacity);
}
public ArrayStack() {
Array = new DynamicArray<>();
}
@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 peek() {
return Array.getLast();
}
@Override
public E pop() {
return Array.removeLast();
}
@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<Integer> stack = new ArrayStack<>();
for(int i = 0;i<5;i++) {
stack.push(i);
System.out.println(stack);
// Stack: [0] top
// Stack: [0,1] top
// Stack: [0,1,2] top
// Stack: [0,2,3] top
// Stack: [0,3,4] top
}
stack.pop();
System.out.println(stack);
// Stack: [0,3] top
}
}
1.4 栈的复杂度分析
- void push(E) // O(1),均摊复杂度(可能触发resize操作)
- E pop() // O(1),均摊复杂度(可能触发resize操作)
- E peek() // O(1),返回栈顶元素即可
- int getSize() // O(1)
- boolean isEmpty() // O(1)
2. 队列 Queue
2.1 队列特点
- 一种先进先出的数据结构
- 只能从一端(队尾)添加元素,从另一端(队首)取出元素
- First In First Out (FIFO)
- 在实际生活中应用广泛(排队)
2.2 数组队列的实现
-
基本功能 1) 入队,void enqueue(E e) 2) 出队,E dequeue() 3) 取出队首元素,E getFront() 4) 返回队列大小,int getSize() 5) 判断队列是否为空,boolean isEmpty()
-
定义支持泛型的队列接口 public interface Queue<E> {
int getSize();
boolean isEmpty();
void enqueue(E e);
E getFront();
E dequeue();
}
-
利用定义的动态数组实现数组队列 public class ArrayQueue<E> implements Queue<E> {
private DynamicArray<E> array;
public ArrayQueue(int capacity) {
array = new DynamicArray<>(capacity);
}
public ArrayQueue() {
array = new DynamicArray<>();
}
@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.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<Integer> 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);
}
}
}
}
2.3 数组队列复杂度分析
- void enqueue(E) // O(1),均摊复杂度(可能触发resize操作)
- E dequeue() // O(n)
- E getFront() // O(1),返回队首元素即可
- int getSize() // O(1)
- boolean isEmpty() // O(1)
2.4 循环队列
数组队列在出队时,总是需要遍历队列,将队列所有元素向前移一位,复杂度比较高,因此一个解决办法就是循环队列:
- 关键点1: 定义front,tail记录队首及队尾所在位置,入队时 tail = (tail+1)%length,出队时front = (front+1) % length
- 关键点2: 当front == tail时表示队列为空
- 关键点3: 当front == (tail+1) % length时表示队列已满,需要扩容
实现过程:
-
泛型接口 public interface Queue<E> {
int getSize();
boolean isEmpty();
void enqueue(E e);
E getFront();
E dequeue();
}
-
定义包含静态数组成员变量、实现泛型接口的动态循环队列 public class LoopQueue<E> implements Queue<E> {
private E[] data;
private int size;
private int front,tail;
public LoopQueue(int capacity) {
data = (E[])new Object[capacity + 1];//循环队列要预留一个空间
front = 0;
tail = 0;
size = 0;
}
// 缺省构造
public LoopQueue() {
this(10);
}
@Override
public boolean isEmpty() {
return front == tail;
}
@Override
public int getSize() {
return size;
}
public int getCapacity() {
return data.length - 1;
}
@Override
public void enqueue(E e) {
// 如果队列已满,扩容
if(front == (tail + 1)%data.length) {
resize(getCapacity()*2);
}
// 将元素添加到队尾
data[tail] = e;
// tail 向后移一位,循环移位
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++) {
// 新队列的首位存储旧队列的front
newData[i] = data[(i+front)%data.length];
}
data = newData;
front = 0;
tail = size;
}
@Override
public E dequeue() {
if(isEmpty()) {
throw new IllegalArgumentException("Dequeue failed. Queue is empty.");
}
// 取出队首元素,并将队首置空
E res = data[front];
data[front] = null;
// front 向后移一位,循环
front = (front + 1)%data.length;
size--;
// 当队列元素等于容量的1/4时,缩小一半队列容量
if(size == getCapacity() / 4 && getCapacity() / 2 != 0){
resize(getCapacity() / 2);
}
return res;
}
@Override
public E getFront() {
if(isEmpty()) {
throw new IllegalArgumentException("Queue is empty.");
}
return data[front];
}
@Override
public String toString() {
StringBuilder res = new StringBuilder();
res.append(String.format("LoopQueue: size = %d,capacity = %dn",getCapacity()));
res.append("front "+"[");
// 从队首开始循环,直到队尾结束
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();
}
}
-
测试 public static void main(String[] args) {
LoopQueue<Integer> 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);
}
}
/*
LoopQueue: size = 1,capacity = 10
front [0] tail
LoopQueue: size = 2,capacity = 10
front [0,1] tail
LoopQueue: size = 3,2] tail
LoopQueue: size = 2,capacity = 5
front [1,2] tail
LoopQueue: size = 3,3] tail
LoopQueue: size = 4,4] tail
LoopQueue: size = 5,4,5] tail
LoopQueue: size = 4,capacity = 5
front [2,5] tail
*/
}
2.5 循环队列时间复杂度分析
- void enqueue(E) // O(1),均摊复杂度(可能触发resize操作)
- E dequeue() // O(1),均摊复杂度(可能触发resize操作)
- E getFront() // O(1),返回队首元素即可
- int getSize() // O(1)
- boolean isEmpty() // O(1)
3. 数组队列与循环队列对比
import java.util.Random;
public class Main {
public static double costTime(Queue<Integer> queue,int nCount) {
Random random = new Random();
long startTime = System.nanoTime();
for(int i = 0;i<nCount;i++) {
queue.enqueue(random.nextInt(Integer.MAX_VALUE));
}
for(int i = 0;i<nCount;i++) {
queue.dequeue();
}
long endTime = System.nanoTime();
return (endTime-startTime) / 1000000000.0 ;
}
public static void main(String[] args) {
int nCount = 100000;
ArrayQueue<Integer> arrayQueue = new ArrayQueue<>();
LoopQueue<Integer> loopQueue = new LoopQueue<>();
System.out.println("ArrayQueue:"+costTime(arrayQueue,nCount)); //ArrayQueue:5.000418012
System.out.println("LoopQueue:"+costTime(loopQueue,nCount)); // LoopQueue:0.022053394
}
}
4. 总结
这节课主要学习了最常见的两种数据结构,栈和队列。栈是后进先出的一种线性结构,实际应用包括:撤销操作、函数调用、括号匹配等,借助动态数组很容易实现栈的相关功能;队列是先进先出的一种线性结构,基于动态数组可以实现队列的相关功能,但数组队列的出队复杂度比较高,为此,借助循环的概念,可以实现一种更加高效的循环队列结构,最后的测试也证实了循环队列的高效性。
(编辑:李大同)
【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容!
|