队列的定义以及实现
队列是一种先进先出的数据结构，新加入的元素放到队尾，从队头进行出队
队列
链表实现队列
public static class Queue1 {
// java中的双向链表LinkedList
// 单向链表就足够了
public Queue<Integer> queue = new LinkedList<>();
// 调用任何方法之前，先调用这个方法来判断队列内是否有东西
public boolean isEmpty() {
return queue.isEmpty();
}
// 向队列中加入num，加到尾巴
public void offer(int num) {
queue.offer(num);
}
// 从队列拿，从头拿
public int poll() {
return queue.poll();
}
// 返回队列头的元素但是不弹出
public int peek() {
return queue.peek();
}
// 返回目前队列里有几个数
public int size() {
return queue.size();
}
}
数组实现队列
public static class Queue2 {
public int[] queue;
public int l;
public int r;
// 加入操作的总次数上限是多少，一定要明确
public Queue2(int n) {
queue = new int[n];
l = 0;
r = 0;
}
// 调用任何方法之前，先调用这个方法来判断队列内是否有东西
public boolean isEmpty() {
return l == r;
}
//入队操作
public void offer(int num) {
queue[r++] = num;
}
//出队操作
public int poll() {
return queue[l++];
}
// 返回队头元素
public int head() {
return queue[l];
}
// 返回队尾元素
public int tail() {
return queue[r - 1];
}
// 获取队列大小
public int size() {
return r - l;
}
}
为了实现空间的循环利用，我们也可以基于数组实现一个循环队列。对于队列的判空和判满，我们使用一个size变量进行控制，当size=0，表示队列为空，size=limit（即队列最大长度），表示队列满
数组实现循环队列
class MyCircularQueue {
public int[] queue;
public int l, r, size, limit;
// 同时在队列里的数字个数，不要超过k
public MyCircularQueue(int k) {
queue = new int[k];
l = r = size = 0;
limit = k;
}
// 如果队列满了，什么也不做，返回false
// 如果队列没满，加入value，返回true
public boolean enQueue(int value) {
if (isFull()) {
return false;
} else {
queue[r] = value;
// r++, 结束了，跳回0
r = r == limit - 1 ? 0 : (r + 1);
size++;
return true;
}
}
// 如果队列空了，什么也不做，返回false
// 如果队列没空，弹出头部的数字，返回true
public boolean deQueue() {
if (isEmpty()) {
return false;
} else {
// l++, 结束了，跳回0
l = l == limit - 1 ? 0 : (l + 1);
size--;
return true;
}
}
// 返回队列头部的数字（不弹出），如果没有数返回-1
public int Front() {
if (isEmpty()) {
return -1;
} else {
return queue[l];
}
}
// 返回队列尾部的数字（不弹出），如果没有数返回-1
public int Rear() {
if (isEmpty()) {
return -1;
} else {
int last = r == 0 ? (limit - 1) : (r - 1);
return queue[last];
}
}
public boolean isEmpty() {
return size == 0;
}
public boolean isFull() {
return size == limit;
}
}
栈的定义以及实现
栈是一种后进先出的数据结构，新加入的元素放到栈顶，出栈是也是先弹出栈顶元素，可直接使用数组实现。
栈的定义及实现
// 实际刷题时更常见的写法，常数时间好
// 如果可以保证同时在栈里的元素个数不会超过n，那么可以用
// 也就是发生弹出操作之后，空间可以复用
// 一般笔试、面试都会有一个明确数据量，所以这是最常用的方式
public static class Stack2 {
public int[] stack;
public int size;
// 同时在栈里的元素个数不会超过n
public Stack2(int n) {
stack = new int[n];
size = 0;
}
// 调用任何方法之前，先调用这个方法来判断栈内是否有东西
public boolean isEmpty() {
return size == 0;
}
// 入栈
public void push(int num) {
stack[size++] = num;
}
// 出栈
public int pop() {
return stack[--size];
}
// 返回栈顶元素，不出栈
public int peek() {
return stack[size - 1];
}
// 返回栈的大小
public int size() {
return size;
}
}
