算法基础概念 (四) --- 栈和队列

本节实现队列代码 https://github.com/down-to-earth1994/Java_Arithmetic.git
com.hyf.java_arithmetic.link.queue 包下的 QueueTest.class 文件
数据结构分为逻辑结构和物理结构；

• 物理结构是：
  a. 包含顺序存储结构 eg： 数组；
  b. 链式存储结构 eg：链表

• 逻辑结构是：
  a. 包含线性结构 eg: 顺序表，栈，队列；
  b. 非线性结构 eg： 树，图

一：栈

• 栈是一种线性结构 栈中的元素只能先入后出(FILO).最早进入的元素存放的位置叫栈底(bottom)，最后进入元素存放的位置叫做栈顶(top)

• 栈的实现既可以拿数组实现也可以拿链表实现

• 入栈(push）和出栈(pop)都 只影响一个元素，所以时间复杂度都是 O(1)

二：队列

• 队列是一种线性结构，队列中的元素只能先入先出（FIFO)队列的端口叫做队头(front),队列的入口端叫作 队尾（rear）
• 队列的实现既可以拿数组实现也可以拿链表实现
• 入队(enqueue) 和出队（dequeue） 只影响一个元素，所以时间复杂度都是 O(1)
  *队列左边不断的出队，队头左边的空间失去作用，则采用循环队列的方式保持队列容量的恒定

说明： 实现循环队列的小技巧，使用 （下标 + 1） 取模 数组的长度 ；控制头指针和尾指针的移动；来保证队列容量不变；具体实现请参考代码实现

栈和队列的应用：

• 栈的应用：

• 栈的输出和输入顺序是相反的 栈通常做对 “历史”的回朔 也就是逆流而上追溯 “历史” eg:1: 实现递归的逻辑；就可以用栈来实现； 2: 因为栈可以回溯 方法的调用链；3: 实现面包屑导航；

• 队列的应用

• 队列的输入和输出顺序是一样的，所以队列通常用于对 "历史"的回放，也就是按照历史的顺序，把 “历史” 重演一遍。
  eg:1:网站爬虫，将爬取的 url 存放在队列中；2:多线程中，争夺公平锁的等待队列，就是按照顺序来决定线程在队列中的次序；