栈
栈是一种特殊的线性表, 只能在一端进行操作
- 添加元素, push, 入栈
- 移除元素, pop, 出栈, 移除栈顶
- 后进先出LIFO 原则
栈
入栈操作
入栈
出栈
public class Stack<E> {
private List<E> list = new LinkedList<>();
public void clear() {
list.clear();
}
public int size() {
return list.size();
}
public boolean isEmpty() {
return list.isEmpty();
}
public void push(E element) {
list.add(element);
}
public E pop() {
return list.remove(list.size() - 1);
}
public E top() {
return list.get(list.size() - 1);
}
}
软件的撤销和恢复功能, 也会用到栈的操作
队列(queue)
队列是一种特殊的线性表, 只能在头尾两端进行操作
队尾: 只能在队尾添加元素, enQueue, 入队
队头: 只能在队头移除元素, deQueue, 出队
先进先出原则, FIFO
队列
接口设计
public class Queue<E> {
LinkedList<E> list = new LinkedList<>();
public int size() {
return list.size();
}
public boolean isEmpty() {
return list.isEmpty();
}
public void enQueue(E element) {
list.add(element);
}
public E deQueue() {
return list.remove(0);
}
public E front() {
return list.get(0);
}
public void clear() {
}
}
双端队列
能在头尾两端添加删除的队列
public class Deque<E> {
LinkedList<E> list = new LinkedList<>();
public int size() {
return list.size();
}
public boolean isEmpty() {
return list.isEmpty();
}
public void enQueueRear(E element) {
list.add(element);
}
public E deQueueRear() {
return list.remove(list.size() - 1);
}
public void enQueueFront(E element) {
list.add(0, element);
}
public E deQueueFront() {
return list.remove(0);
}
public E front() {
return list.get(0);
}
public E rear() {
return list.get(list.size() - 1);
}
public void clear() {
}
}
循环队列
使用数组实现循环队列以及扩容的实现
@SuppressWarnings("unchecked")
public class CircleQueue<E> {
private int front;
private int size;
private E[] elements;
private static final int DEFAULT_CAPACITY = 10;
public CircleQueue() {
elements = (E[]) new Object[DEFAULT_CAPACITY];
}
public int size() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
public void enQueue(E element) {
ensureCapacity(size + 1);
elements[(front + size) % elements.length] = element;
size++;
}
public E deQueue() {
E frontElement = elements[front];
elements[front] = null;
front = (front + 1) % elements.length;
size --;
return frontElement;
}
public E front() {
return elements[front];
}
public void clear() {
}
private void ensureCapacity(int capacity) {
int oldCapacity = elements.length;
if (oldCapacity >= capacity) return;
int newCapacity = oldCapacity + (oldCapacity >> 1);
E[] newElements = (E[]) new Object[newCapacity];
for (int i = 0; i < size; i++) {
newElements[i] = elements[(i + front) % elements.length];
}
elements = newElements;
front = 0;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append("capacity=").append(elements.length).append(" size=").append(size).append(" front=").append(front).append(", [");
for (int i = 0; i < elements.length; i++) {
if (i != 0) {
sb.append(", ");
}
sb.append(elements[i]);
}
sb.append("]");
return sb.toString();
}
}
建议: 尽量避免使用乘*, 除/, 模%, 浮点数运算, 效率比较低
已知n>=0, m>0
n%m, 等价 n - (m > n ? 0 : m), n < 2m
循环双端队列
@SuppressWarnings("unchecked")
public class CircleDeque<E> {
private int front;
private int size;
private E[] elements;
private static final int DEFAULT_CAPACITY = 10;
public CircleDeque() {
elements = (E[]) new Object[DEFAULT_CAPACITY];
}
public int size() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
/**
* 尾部入队
* @param element
*/
public void enQueueRear(E element) {
ensureCapacity(size + 1);
elements[index(size)] = element;
size++;
}
/**
* 尾部出队
* @return
*/
public E deQueueRear() {
int rearIndex = index(size - 1);
E rear = elements[rearIndex];
elements[rearIndex] = null;
size--;
return rear;
}
/**
* 头部入队
* @param element
*/
public void enQueueFront(E element) {
ensureCapacity(size + 1);
front = index(-1);
elements[front] = element;
size++;
}
/**
* 头部出队
* @return
*/
public E deQueueFront() {
E frontElement = elements[front];
elements[front] = null;
front = index(1);
size--;
return frontElement;
}
public E front() {
return elements[front];
}
public E rear() {
return elements[index(size - 1)];
}
public void clear() {
for (int i = 0; i < size; i++) {
elements[index(i)] = null;
}
size = 0;
front = 0;
}
private void ensureCapacity(int capacity) {
int oldCapacity = elements.length;
if (oldCapacity >= capacity) return;
int newCapacity = oldCapacity + (oldCapacity >> 1);
E[] newElements = (E[]) new Object[newCapacity];
for (int i = 0; i < size; i++) {
newElements[i] = elements[index(i)];
}
elements = newElements;
front = 0;
}
private int index(int index) {
index += front;
if (index < 0) {
return index + elements.length;
}
return index - (index >= elements.length ? elements.length : 0);
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append("capacity=").append(elements.length).append(" size=").append(size).append(" front=").append(front).append(", [");
for (int i = 0; i < elements.length; i++) {
if (i != 0) {
sb.append(", ");
}
sb.append(elements[i]);
}
sb.append("]");
return sb.toString();
}
}
网友评论