阅读量:1
栈与队列本质上都是一种线性表，他们存放与读取数据方式的不同，利用好他们各自的特点，就能够解决许多棘手的问题，他们会是之后我们编程中存放数据的两种重要数据结构。接下来就由我来带大家梳理一下他们各自的特点吧。
一、栈
1、概念
栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出的原则。简单来说就像存放羽毛球的羽毛球桶，后放入桶中的羽毛球会压住先放入桶中的羽毛球，在取羽毛球时，必须先取出后放入的羽毛球，才能取出下面先放入的羽毛球，也就是所谓的先进后出的原则
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。 出栈：栈的删除操作叫做出栈。出数据在栈顶。所谓压栈就相当于是放羽毛球，出栈就是取羽毛球。在数据结构中就对应了存放数据和读取数据。
2、栈的模拟实现
栈可以用数组或链表实现，一般会采用数组来进行实现，因为相比于链表，数组在进行尾插的效率更高一些
这里我们就主要来介绍一下栈的数组实现吧：
和顺序表一样：一个存储数据的数组，一个变量记录个数，一个变量记录容量
public class MyStack { public int[] elem; public int usedSize; }功能实现：
（1）栈的初始化
public MyStack() { this.elem = new int[10]; }（2）压栈
在压栈时一定要注意数组是否已经满了，如果满了就需要先进行扩容再完成插入操作，不然是会发生空指针异常的。
public void push(int val) { if(isFull()) { //扩容 elem = Arrays.copyOf(elem,2*elem.length); } elem[usedSize] = val; usedSize++; } public boolean isFull() { return usedSize == elem.length; }小tips：我们在学习数据结构时一定要注意好这些小细节，提高代码的严谨性和适用性。培养好这种思想对我们后续编程学习非常重要
（3）出栈
在出栈时我们也不能单单只想着实现出栈删除尾部元素就完了，要注意还要考虑空栈的情况，如果空栈的话就没有元素可以取出，直接返回即可
public boolean empty() { return usedSize == 0; } public int pop() { if(empty()) { return -1; } int oldVal = elem[usedSize-1]; usedSize--; return oldVal; }同时在实际应用中，我们可能只需要知道栈顶元素的值就可以了，不需要删除元素，这时我们就可以“小瞄一下”，只读取栈顶元素值而不删除了。
public int peek() { if(empty()) { return -1; } return elem[usedSize-1]; }3、Stack
在java中内置了栈的实现类Stack类，我们只需要会调用即可。自己实现一编栈的功能也是为了加深我们对栈的深层理解。
常见方法
使用示例：
public static void main(String[] args) { Stack<Integer> s = new Stack(); s.push(1); s.push(2); s.push(3); s.push(4); System.out.println(s.size()); // 获取栈中有效元素个数---> 4 System.out.println(s.peek()); // 获取栈顶元素---> 4 s.pop(); // 4出栈，栈中剩余1 2 3，栈顶元素为3 System.out.println(s.pop()); // 3出栈，栈中剩余1 2 栈顶元素为3 if(s.empty()){ System.out.println("栈空"); }else{ System.out.println(s.size()); } }二、队列
1、概念
队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾（Tail/Rear） 出队列：进行删除操作的一端称为队头 （Head/Front）
相信我们在生活中应该多少都有经历过排队，与栈不同，排队讲究的就是一个先来后到，先来的可以进行操作，后来的就得排在之后了。
数据结构中的队列与现实中的排队是非常类似的，将插入的数据按先后顺序排列起来，在取用时则先取用“先来的”，再取用“后来的”
2、队列的模拟实现
队列可以用数组或链表实现，一般采用链表实现，因为在实现出队操作时相当于进行头删，链表进行头删的操作效率更高一些
这里我们就主要来介绍一下队列的链表实现吧。
public class MyQueue { static class ListNode { public int val; public ListNode prev ; public ListNode next; public ListNode(int val) { this.val = val; } } public ListNode head; public ListNode last; }（1）入队
public void offer(int val) { ListNode node = new ListNode(val); if(head == null) { head = last = node; }else { last.next = node; node.prev = last; last = last.next; } }（2）出队
public int poll() { if(head == null) { return -1; } int ret = head.val; if(head.next == null) { head = null; last = null; }else { head = head.next; head.prev = null; } return ret; } public int peek() { if(head == null) { return -1; } return head.val; } public boolean isEmpty() { return head == null; }3、Queue
在Java中，Queue是个接口，底层是通过链表实现的
常见方法：
使用示例：
public static void main(String[] args) { Queue<Integer> q = new LinkedList<>(); q.offer(1); q.offer(2); q.offer(3); q.offer(4); q.offer(5); // 从队尾入队列 System.out.println(q.size()); System.out.println(q.peek()); // 获取队头元素 q.poll(); System.out.println(q.poll()); // 从队头出队列，并将删除的元素返回 if(q.isEmpty()){ System.out.println("队列空"); }else{ System.out.println(q.size()); } }三、总结
栈和队列本质上就是两种存放与读取方式不同的线性表，栈的主要特点是先进后出，队列则是先进先出，我们可以根据实际应用场景来选择适合的结构。还是那句话，没有最好的数据结构，只有最适合的数据结构。
那么本篇文章就到此为止了，如果觉得这篇文章对你有帮助的话，可以点一下关注和点赞来支持作者哦。作者还是一个萌新，如果有什么讲的不对的地方欢迎在评论区指出，希望能够和你们一起进步✊
