数据结构与算法 --- 组数、链表、栈和队列（二）
💡
原文中文，约2800字，阅读约需7分钟。
📝
内容提要
本文介绍了数组、链表、栈和队列的数据结构和算法优化策略。栈是一种后进先出的线性表，可以用数组或链表实现。队列是一种先进先出的线性表，也可以用数组或链表实现。阻塞队列和并发队列是特殊的队列实现，分别实现了生产者-消费者模型和无锁并发操作。
🎯
关键要点
-
栈是一种后进先出的线性表，称为LIFO或FILO，只允许在一端进行插入和删除操作。
-
栈可以用数组实现（顺序栈）或用链表实现（链式栈）。
-
栈的入栈和出栈操作的时间复杂度均为O(1)，空间复杂度也为O(1)。
-
顺序栈需要动态扩容，当栈满时需要重新申请更大的内存空间。
-
入栈操作的时间复杂度在栈有空闲空间时为O(1)，在没有空闲空间时为O(n)。
-
队列是一种先进先出的线性表，称为FIFO，入队操作在队尾，出队操作在队首。
-
队列可以用数组实现（顺序队列）或用链表实现（链式队列）。
-
顺序队列需要两个指针：head指向队首，tail指向队尾，可能会遇到边界问题。
-
循环队列通过将首尾相连避免了数据搬移的问题，提升了性能。
-
阻塞队列在队列为空时会阻塞出队操作，队列满时会阻塞入队操作，常用于生产者-消费者模型。
-
并发队列通过加锁实现线程安全，或利用CAS原子操作实现无锁并发。
➡️
