队列和栈的实现和应用

一、概述

队列：先进先出
栈：先进后出

二、栈的实现

• 顺序栈：使用数组实现，标记数组中元素数量，数组存储满了，需要重新开辟内存（这时时间复杂度O(n)，但平均时间复杂度还是O(1)，）
• 链式栈：链表实现

三、栈的应用

• 函数调用
• 计算器实现：双栈，一个存数，一个存运算符
• 检查括号是否匹配
• 浏览器的前进和后退

四、队列的实现

• 顺序队列：数组实现（变量标记队头和队尾的下标）
• 链式队列：链表实现（head和tail指针）

循环队列：
对于使用数组（长度为n）实现的循环队列，判断是否为空队列的条件是head == tail，判断队列是否为满队列条件是（tail+1)%n = head。当队列满了会浪费一个节点来代表tail。

队列入队：

bool push(item)
if(tail + 1) % n = head;
{
	return false;
}
items[tail] = item;
tail = (tail + 1) % n ;

return true;
1
2
3
4
5
6
7
8
9

队列出队

if(head == tail)
{
	return null;
}

item = items[head];
head = (head + 1) % n;

return item;

1
2
3
4
5
6
7
8
9
10

五、队列的应用

1. 阻塞队列：生产者、消费者模型
2. 并发队列：基于数组的循环队列，使用CAS原子操作实现高效的并发队列
3. 线程池请求队列
   对于大部分资源有限的场景，当没有空闲资源时，基本上都可以通过“队列”这种数据结构来实现请求排队。

六、栈和队列常见问题

1. 最小栈：
使用双栈，一个存放原始数据，一个辅助栈存放没入栈的时候对比下是不是最小值（大于等于当前最小值），如果是存入辅助栈。
入栈节点为pair，或者自定义结构体，入栈时节点分辨存储入栈数据和入栈后栈中的最小值。
2. 使用栈实现队列：
使用双栈，一个主栈push入栈数据，另一个辅助栈用于取数据，辅助栈空了将主栈的数据全部取出存入，这时先入主栈的数据就在最上面，从而实现了先进先出。
3. 使用队列实现栈：
使用双队列，主队列存储最终的位置，辅助队列用于先将入栈的数据数据存入队列头部，再将主队列数据依次存储辅助队列，这样保证的新入的数据都在队列头部，最后将，主队列和辅助队列属性交换。
使用单个队列，入栈数据直接入队列，然后将之前的数据全部依次出队列再入队列，这样保证了新进数据永远再队列头部。
https://leetcode.cn/problems/implement-stack-using-queues/solution/yong-dui-lie-shi-xian-zhan-by-leetcode-solution/

七、其他相关知识点

1. 无锁并发队列：使用CAS+数组方式实现
2. 消息队列：