作者主页：paper jie 的博客
本文作者：大家好，我是paper jie，感谢你阅读本文，欢迎一建三连哦。
本文录入于《JAVA数据结构》专栏，本专栏是针对于大学生，编程小白精心打造的。笔者用重金(时间和精力)打造，将javaSE基础知识一网打尽，希望可以帮到读者们哦。
其他专栏：《算法详解》《C语言》《javaSE》等
内容分享：本期将会分享数据结构中的栈与队列
目录
栈
栈的概念
栈它是一种特殊的线性表，只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守着先进后出的规则。
压栈：栈的插入操作叫做进栈，压栈，入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据在栈顶。
栈的使用
代码示范：
public class Test { public static void main(String[] args) { Stack stack = new Stack<>(); stack.push(1); stack.push(2); stack.push(3); stack.push(4); stack.push(5); System.out.println(stack.peek()); System.out.println(stack.pop()); System.out.println(stack.empty()); System.out.println(stack.size()); }} 栈的模拟实现
Stack继承了Vector，Vector和ArrayList类似，都是动态的顺序表，但不同的是Vector是线性安全的。
代码模拟实现：
public class MyStack implements Istack{ private int[] elem; private int usedsize; private static final int DEFAULT_CAPACITY = 10; public MyStack() { this.elem = new int[DEFAULT_CAPACITY]; } @Override public void push(int x) { if(full()) { elem = Arrays.copyOf(elem, 2*elem.length); } elem[usedsize] = x; usedsize++; } @Override public boolean full() { if(usedsize == elem.length) { return true; } return false; } @Override public int pop() { if(Empty()) { throw new Emptyexception("数组为空"); } int ret = elem[usedsize-1]; usedsize--; return ret; } @Override public int peek() { if(Empty()) { throw new Emptyexception("数组为空"); } return elem[usedsize - 1]; } @Override public int size() { return usedsize; } @Override public boolean Empty() { if(usedsize == 0) { return true; } return false; }}栈的应用
将递归转化为循环
// 递归方式 void printList(Node head){ if(null != head){ printList(head.next); System.out.print(head.val + " "); } } // 循环方式 void printList(Node head){ if(null == head){ return; } Stack s = new Stack<>();// 将链表中的结点保存在栈中 Node cur = head; while(null != cur){ s.push(cur); cur = cur.next; } // 将栈中的元素出栈 while(!s.empty()){ System.out.print(s.pop().val + " "); } } 栈，虚拟机栈，栈帧的区分
栈：是一种数据结构
虚拟机栈：是java虚拟机JVM中分配的一块内存
栈帧：是在调用方法的时候，会在虚拟机中为这个方法分配一块内存
队列（Queue）
队列的概念
队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(FirstIn First Out)
入队列：进行插入操作的一端称为队尾（Tail/Rear）
出队列：进行删除操作的一端称为队头
队列的使用
在java中，Queue是一个接口，底层是通过链表来实现的
这里要注意一个点：Queue是一个接口，在实例化时必须实例化LinkedList的对象，因为LinkedList实现了Queue接口
public static void main(String[] args) {Queue 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());}} 队列模拟实现
链式结构对列：
public class MyLinkqueue { static class ListNode { int val; ListNode prev; ListNode next; public ListNode(int val) { this.val = val; } } ListNode head; ListNode last; int usedsize; public void offer(int val) { ListNode node = new ListNode(val); if(head == null) { head = node; last = node; usedsize++; return; } last.next = node; node.prev = last; last = node; usedsize++; } public int poll() { if(head == null) { return -1; } int ret = head.val; if(head.next == null) { head = null; last = null; } else { head.next.prev = null; head = head.next; } usedsize--; return ret; } public int peek() { if(head == null) { return -1; } return head.val; } public boolean Empty(){ return head == null; } public int size() { return usedsize; }}循环队列
实际中我们有时还会使用一种队列叫循环队列，操作系统课程讲解生产者消费者模型时可以就会使用循环队列，环形队列通常使用数组实现
代码：
class MyCircularQueue { int[] elem; int front; int rear; public MyCircularQueue(int k) { elem = new int[k+1]; } public boolean enQueue(int value) { if(isFull()) { return false; } elem[rear] = value; rear = (rear+1) % elem.length; return true; } public boolean deQueue() { if(isEmpty()) { return false; } front = (front+1)% elem.length; return true; } public int Front() { if(isEmpty()) { return -1; } return elem[front]; } public int Rear() { if(isEmpty()) { return -1; } int ret = (rear == 0) ? elem.length-1 : rear-1; return elem[ret]; } public boolean isEmpty() { return front == rear; } public boolean isFull() { return (rear+1) % elem.length == front; }}双端队列
双端队列是指允许两端都可以进行入队和出队操作的队列，deque 是 “double ended queue” 的简称，那就说明元素可以从队头出队和入队，也可以从队尾出队和入队，Deque是一个接口，使用时必须创建LinkedList的对象
来源地址：https://blog.csdn.net/paperjie/article/details/133561168
