写在前面
栈和队列，也属于线性表，因为它们也都用于存储逻辑关系为 “一对一” 的数据。使用栈结构存储数据，讲究 先进后出，即最先进栈的数据，最后出栈；使用队列存储数据，讲究 先进先出，即最先进队列的数据，也最先出队列。
什么是栈
栈是一种只能从表的一端存取数据且遵循 “先进后出” 原则的线性存储结构，同顺序表和链表一样，也是用来存储逻辑关系为 “一对一” 数据。栈的应用有很多，比如浏览器的跳转和回退机制等。
从上图可以看出：
- 栈只能从一端存取数据，而另外一端是封闭的
- 无论是存还是取，都需要遵循 先进后出的原则。如需要取元素1，需要提前将元素4,3,2取出。
通常，栈的开口端被称为栈顶；封口端被称为栈底。
进栈和出栈
对于栈的操作一般是如下两种：
- 进栈：将新元素放到 栈顶元素的上面，成为新的栈顶元素（入栈或压栈）；
- 出栈：将 栈顶元素删除掉，使得与其相邻的元素成为新的栈顶元素（退栈或弹栈）；
栈的存储结构
- 顺序结构：使用数组实现
- 链式结构：使用链表实现
顺序栈
一个简单的队列，包含以下方法：
方法 说明 push(E e) 入栈 pop() 出栈 peek() 获取栈头部元素 isEmpty() 判断栈是否为空
代码测试
public class Stack {
/**
* 栈的大小
*/
private int maxSize;
/**
* 数组
*/
private int[] stackArray;
/**
* 栈的top
*/
private int top;
/**
* 初始化栈
*
* @param size
*/
public Stack(int size) {
this.maxSize = size;
stackArray = new int[maxSize];
top = -1;
}
/**
* 入栈
*
* @param i
*/
public void push(int i) {
stackArray[++top] = i;
}
/**
* 常量出栈
*
* @return
*/
public int pop() {
return stackArray[top--];
}
/**
* 判空
*
* @return
*/
public boolean isEmpty() {
return (top == -1);
}
/**
* 是否已满
*
* @return
*/
public boolean isFull() {
return (top == maxSize);
}
@Override
public String toString() {
for (int i : stackArray) {
System.out.println("top:"+i);
}
return super.toString();
}
//测试
public static void main(String[] args) {
Stack stack = new Stack(5);
//入栈
stack.push(1);
stack.push(2);
stack.push(3);
stack.push(4);
stack.push(5);
while (!stack.isEmpty()){
//出栈
int pop = stack.pop();
System.out.println("出栈元素："+pop);
}
}
}
测试结果可以发现显示的数据和输入的数据恰好相反。这也就符合 “先进后出”的原则。
实际运用：字符反转
public class StackReverse {
/**
* 栈的大小
*/
private int maxSize;
/**
* 数组
*/
private char[] stackArray;
/**
* 栈的top
*/
private int top;
public StackReverse() {
}
/**
* 初始化栈
*
* @param size
*/
public StackReverse(int size) {
this.maxSize = size;
stackArray = new char[maxSize];
top = -1;
}
/**
* 入栈
*
* @param c
*/
public void push(char c) {
stackArray[++top] = c;
}
/**
* 常量出栈
*
* @return
*/
public char pop() {
return stackArray[top--];
}
/**
* 判空
*
* @return
*/
public boolean isEmpty() {
return (top == -1);
}
/**
* 是否已满
*
* @return
*/
public boolean isFull() {
return (top == maxSize);
}
public String doReverse(String str) {
System.out.println("输入字符为：" + str);
String rev = "";
int stackSize = str.length();
StackReverse stack = new StackReverse(stackSize);
for (int i = 0; i < stackSize; i++) {
//获取字符
char c = str.charAt(i);
//入栈
stack.push(c);
}
while (!stack.isEmpty()) {
char pop = stack.pop();
rev = rev + pop;
}
return rev;
}
public static void main(String[] args) {
String rev = new StackReverse().doReverse("reverse");
System.out.println("字符反转后：" + rev);
}
}
测试结果：
之前我面试碰到过，我当时是这样回答的：直接调用reverse方法就行了啊。现在想想无地自容啊，因为面试官问的是实现方式，当然还有很多方法去实现，比如递归等等，这里只是举个例子。
链栈
public class StackByLink<e> {
private Node<e> top;
/**
* 返回栈顶元素
*
* @return
*/
public E peek() {
return top.getData();
}
/**
* 出栈
*
* @return
*/
public E pop() {
E data = null;
if (top != null) {
data = top.getData();
//把栈顶元素弹出，并把原栈顶的下一个元素设为栈顶元素
top = top.getNext();
}
return data;
}
/**
* 入栈
* 不太清楚的可以看上面的图
* 把an设为新栈顶元素node an-1为原来的栈顶元素 an-1的前一个元素就是an即node
*
* @param data
*/
public void push(E data) {
Node<e> node = new Node<e>();
node.setData(data);
if (top == null) {
top = node;
} else {
//原来的元素设为新栈顶的下一个元素
node.setNext(top);
//
top.setPre(node);
top = node;
}
}
/**
* 判空
*
* @return
*/
public boolean isEmpty() {
return (top == null);
}
class Node<e> {
E data;
//前驱节点
Node pre;
//后继节点
Node next;
...省略get set
}
//测试
public static void main(String[] args) {
StackByLink<string> stack = new StackByLink<>();
stack.push("我");
stack.push("是");
stack.push("链");
stack.push("表");
System.out.println("peek:" + stack.peek());
stack.push("实");
stack.push("现");
stack.push("的");
stack.push("栈");
System.out.println("pop:" + stack.pop());
System.out.println("peek:" + stack.peek());
}
}
</string></e></e></e></e></e>
Java中的栈
java中的栈是通过继承Vector来实现的，如下：
Vector作为List的另外一个典型实现类，支持List的全部功能，Vector类也封装了一个动态的，允许在分配的Object[]数组，Vector是一个比较古老的集合，JDK1.0就已经存在，建议尽量不要使用这个集合，Vector与ArrayList的主要是区别是，Vector是线程安全的，但是性能比ArrayList要低，主要原因是每个方法都是通过synchronized来保证线程同步的。
所以问题就来了，既然只是为了实现栈，为什么不用链表来单独实现，只是为了复用简单的方法而迫使它继承Vector（Stack和Vector本来是毫无关系的）。这使得Stack在基于数组实现上效率受影响，另外因为继承Vector类，Stack可以复用Vector大量方法，这使得Stack在设计上不严谨，当我们看到Vector中：
public void add(int index, E element) {
insertElementAt(element, index);
}
该方法可以在指定位置添加元素，这与Stack的设计理念相冲突（栈只能在栈顶添加或删除元素），我估计当时的开发者肯定是偷懒了。
什么是队列
队列是一种要求数据只能从一端进，从另一端出且遵循 “先进先出” 原则的线性存储结构。
通常，称进数据的一端为 “队尾”，出数据的一端为 “队头”，数据元素进队列的过程称为 “入队”，出队列的过程称为 “出队”。生活中常见的排队买票和医院挂号都是队列。
队列的存储结构
- 顺序结构：使用数组实现
- 链式结构：使用链表实现
一个简单的队列，包含以下方法：
方法 说明 add(E e) 入队 remove() 删除此队列的头部 peek() 获取队列头部元素 isEmpty() 判断队列是否为空
顺序队列
public class Queue {
private int maxSize;
private int[] queueArray;
private int front;
private int rear;
private int count;
/**
* 初始化
* @param s
*/
public Queue(int s) {
this.maxSize = s;
queueArray = new int[s];
front = 0;
rear = -1;
count = 0;
}
/**
* 入队
* @param i
*/
public void add(int i) {
if (rear == maxSize - 1) {
rear = -1;
}
queueArray[++rear] = i;
count++;
}
/**
* 出队
* @return
*/
public int remove() {
int temp = queueArray[front++];
if (front == maxSize) {
front = 0;
}
count--;
return temp;
}
/**
* 获取队列头部元素
* @return
*/
public int peek() {
return queueArray[front];
}
public boolean isEmpty() {
return (count == 0);
}
@Override
public String toString() {
return "入队元素：" + Arrays.toString(queueArray);
}
public static void main(String[] args) {
Queue queue = new Queue(5);
queue.add(1);
queue.add(2);
queue.add(3);
queue.add(4);
queue.add(5);
System.out.println(queue);
while (!queue.isEmpty()){
int remove = queue.remove();
System.out.println("出队元素："+remove);
}
}
}
测试结果
链式队列
队列的链式存储结构，本质就是线性表的单链表，但它只能 尾进头出，可参考前面的单链表，这里不再复述。
注：以下队列只做介绍，并附上详细讲解连接，感兴趣的可以自行查看
双端队列
双端队列Deque是一种具有 队列和栈的性质的数据结构。双端队列中的元素可以从两端弹出，其限定插入和删除操作在表的两端进行。
ArrayDeque是 Deque接口的一个实现，使用了可变数组，所以没有容量上的限制。 同时， ArrayDeque是线程不安全的，在没有外部同步的情况下，不能再多线程环境下使用。
ArrayDeque是 Deque的实现类，可以作为栈来使用，效率高于 Stack；
也可以作为队列来使用，效率高于 LinkedList。
需要注意的是， ArrayDeque不支持 null值。
可参考：ArrayDeque类的使用详解
阻塞队列
当队列是空的时候，从队列 获取元素的操作将会被阻塞，当队列是满的时候，从队列 插入元素的操作将会被阻塞。后面会在并发编程的JUC中讲到。
Java中阻塞队列BlockingQueue是一个接口，他的实现类主要包括以下几种：
类名 说明 ArrayBlockingQueue 基于数组的阻塞队列实现，在ArrayBlockingQueue内部，维护了一个定长数组，以便缓存队列中的数据对象，这是一个常用的阻塞队列，除了一个定长数组外，ArrayBlockingQueue内部还保存着两个整形变量，分别标识着队列的头部和尾部在数组中的位置。 LinkedBlockingQueue 基于链表的阻塞队列，同ArrayListBlockingQueue类似，其内部也维持着一个数据缓冲队列（该队列由一个链表构成），当生产者往队列中放入一个数据时，队列会从生产者手中获取数据，并缓存在队列内部，而生产者立即返回；只有当队列缓冲区达到最大值缓存容量时（LinkedBlockingQueue可以通过构造函数指定该值），才会阻塞生产者队列，直到消费者从队列中消费掉一份数据，生产者线程会被唤醒，反之对于消费者这端的处理也基于同样的原理。而LinkedBlockingQueue之所以能够高效的处理并发数据，还因为其对于生产者端和消费者端分别采用了独立的锁来控制数据同步，这也意味着在高并发的情况下生产者和消费者可以并行地操作队列中的数据，以此来提高整个队列的并发性能。 DelayQueue DelayQueue中的元素只有当其指定的延迟时间到了，才能够从队列中获取到该元素。DelayQueue是一个没有大小限制的队列，因此往队列中插入数据的操作（生产者）永远不会被阻塞，而只有获取数据的操作（消费者）才会被阻塞。 PriorityBlockingQueue 基于优先级的阻塞队列（优先级的判断通过构造函数传入的Compator对象来决定），但需要注意的是PriorityBlockingQueue并不会阻塞数据生产者，而只会在没有可消费的数据时，阻塞数据的消费者。因此使用的时候要特别注意，生产者生产数据的速度绝对不能快于消费者消费数据的速度，否则时间一长，会最终耗尽所有的可用堆内存空间。在实现PriorityBlockingQueue时，内部控制线程同步的锁采用的是公平锁。 SynchronousQueue 一种无缓冲的等待队列，类似于无中介的直接交易，有点像原始社会中的生产者和消费者，生产者拿着产品去集市销售给产品的最终消费者，而消费者必须亲自去集市找到所要商品的直接生产者，如果一方没有找到合适的目标，那么对不起，大家都在集市等待。和其他队列不同的还有，SynchronousQueue直接使用CAS实现线程的安全访问。主要使用场景是在线程池中，后续会讲到。
优先级队列
优先级队列和通常的栈和队列一样，只不过里面的每一个元素都有一个 优先级，在处理的时候，首先处理优先级最高的。如果两个元素具有相同的优先级，则按照他们插入到队列中的先后顺序处理。
可参考：Java Queue系列之PriorityQueue
总结
栈和队列涉及的方面很广，比如JVM的虚拟机栈，消息中间件MQ和队列的关系，本文主要强调对 栈和队列概念的理解，后续会逐步分享。
参考
拓展延伸
- Java中的Stack是通过Vector来实现的，这种设计被认为是不良的设计，说说你的看法？
- LIFO和FIFO各代表什么含义？
- 栈的入栈和出栈操作与队列的插入和移除的时间复杂度是否相同？
Original: https://www.cnblogs.com/javatv/p/15614694.html
Author: Ayue、
Title: 栈和队列
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/572686/
转载文章受原作者版权保护。转载请注明原作者出处！