✅栈和队列的区别
典型回答
栈和队列从定义上来讲，只有一个不同，就是**栈是先进后出的，而队列是先进先出的。**网上有一个形象的例子，说栈是吃了吐，队列则是吃了拉，哈哈哈。两者不的不同如下所图所示：
栈：
队列：
栈和队列的实现
从实现上来说，栈和队列都可以用数组或者链表实现，不过从实现难度和时空复杂度的角度考虑，一般来说，栈会用数组实现，队列会用链表实现。如下所示：
class StackByArray {
private int top = -1;
private int maxSize;
private int[] stack;
public ArrayStack(int maxSize){
this.maxSize = maxSize;
stack = new int[maxSize];
}
public boolean isFull(){
return top == maxSize - 1;
}
public boolean isEmpty(){
return top == -1;
}
public void push(int data){
if (isFull()){
return;
}
stack[++top] = data;
}
public int pop () {
if (isEmpty()){
throw new RuntimeException("this stack is empty");
}
int data = stack[top--];
return data;
}
}
class StackByLink {
private Node head;
public void push(int data) {
Node temp = new Node(data);
if(head != null) {
temp.next = head;
}
head = temp;
}
public int pop() {
if(head == null) {
return 0;
}
int ans = head.data;
head = head.next;
return ans;
}
private static class Node {
public int data;
public Node next;
public Node(int data) {
this.data = data;
}
}
}class QueueByLink {
Node front;
Node tail;
int size;
public void offer(int data){
Node temp = new Node(data);
if(isEmpty()){
front = temp;
tail = front;
} else {
tail.next = temp;
tail = temp;
}
size++;
}
public int poll(){
if(isEmpty()){
return 0;
}
int data = front.data;
front = front.next;
size --;
return data;
}
public boolean isEmpty(){
return size == 0;
}
private static class Node {
public int data;
public Node next;
public Node(int data) {
this.data = data;
}
}
}在Java中，常见的栈有Stack，Deque(implemented by LinkedList�)，常见的队列有Queue和Queue（implemented by LinkedList）所以我们一般刷题的时候，常常会用下面的写法：
Stack<Integer> stack = new Stack<>();
stack.push(1);
stack.pop();
Queue<Integer> queue = new LinkedList<>();
queue.offer(1);
queue.poll();应用
栈和队列在日常开发过程中无处不在。
我们平常所使用的递归，就是通过栈来实现的。同时还有JVM中的方法在执行的时候，也会放到栈上，因为他们的执行顺序都是遵循先进后出的
队列常常作为缓冲区来使用，像我们熟知的生产者和消费者模型，生产者完成任务后，会把数据存放到队列中，等待消费者来读取。
知识扩展
什么是双端队列和循环队列
双端队列
队列还有一种变形的结构叫双端队列，所谓的双端，就是说该队列不仅遵循FIFO原则，通常也可以按照使用者的想法从队首或者队尾进行插入和删除
Deque<Integer> deque = new LinkedList<>();
deque.offerFirst(1);
deque.offerLast(1);
deque.pollFirst();
deque.pollLast();循环队列
一般情况下，数组是不能实现队列的，因为先进先出，可能会存在假溢出的情况，所以数组的空间一定会被浪费。所以，我们会通过循环的方式，当最尾部的索引到达length之后，我们会将该索引重新置为0，以此来重复利用数组的空间。而这样一种形式，就会造成一种逻辑循环，也就是我们说的循环队，假溢出如下所示：
代码如下：
class QueueByArray {
private final int[] items;
private int head=0;
private int tail=0;
public boolean push(int data) {
if(((tail + 1) % items.length) == head) {
// 此时说明队列的空间已经满了，只能扩容
return false;
}
else {
items[tail] = data;
tail = (tail+1) % items.length;
return true;
}
}
public int pop() {
int data = items[head];
head = (head+1) % items.length;
return data;
}
public QueueByArray(int length) {
this.items = new int[length];
}
}一般来说，循环队列可以作为缓冲区使用，如果index超出，直接覆盖就可以了。