写在前面
栈和队列，也属于线性表，因为它们也都用于存储逻辑关系为 "一对一" 的数据。使用栈结构存储数据，讲究先进后出，即最先进栈的数据，最后出栈；使用队列存储数据，讲究先进先出，即最先进队列的数据，也最先出队列。
什么是栈
栈是一种只能从表的一端存取数据且遵循 "先进后出" 原则的线性存储结构，同顺序表和链表一样，也是用来存储逻辑关系为 "一对一" 数据。栈的应用有很多，比如浏览器的跳转和回退机制等。
从上图可以看出：
栈只能从一端存取数据，而另外一端是封闭的
无论是存还是取，都需要遵循先进后出的原则。如需要取元素 1，需要提前将元素 4,3,2 取出。
通常，栈的开口端被称为栈顶；封口端被称为栈底。
进栈和出栈
对于栈的操作一般是如下两种：
进栈：将新元素放到栈顶元素的上面，成为新的栈顶元素（入栈或压栈）；
出栈：将栈顶元素删除掉，使得与其相邻的元素成为新的栈顶元素（退栈或弹栈）；
栈的存储结构
顺序栈
一个简单的队列，包含以下方法：
代码测试
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()); }}
复制代码
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 的设计理念相冲突（栈只能在栈顶添加或删除元素），我估计当时的开发者肯定是偷懒了。
什么是队列
队列是一种要求数据只能从一端进，从另一端出且遵循 "先进先出" 原则的线性存储结构。
通常，称进数据的一端为 "队尾"，出数据的一端为 "队头"，数据元素进队列的过程称为 "入队"，出队列的过程称为 "出队"。生活中常见的排队买票和医院挂号都是队列。
队列的存储结构
一个简单的队列，包含以下方法：
顺序队列
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 是一个接口，他的实现类主要包括以下几种：
可参考：BlockingQueue（阻塞队列）详解
优先级队列
优先级队列和通常的栈和队列一样，只不过里面的每一个元素都有一个优先级，在处理的时候，首先处理优先级最高的。如果两个元素具有相同的优先级，则按照他们插入到队列中的先后顺序处理。
可参考：Java Queue系列之PriorityQueue
总结
栈和队列涉及的方面很广，比如 JVM 的虚拟机栈，消息中间件 MQ 和队列的关系，本文主要强调对栈和队列概念的理解，后续会逐步分享。
参考
拓展延伸
都是自己人，点赞关注我就收下了🤞（白 piao 无罪🥺）
评论 (1 条评论)