发布时间：2025-06-24 20:16:52 作者：北方职教升学中心 阅读量：284
Deque<Integer> stack = new ArrayDeque<>();//双端队列的线性实现Deque<Integer> queue = new LinkedList<>();//双端队列的链式实现
本篇文章到此结束，接下来会对二叉树相关知识进行讲解
2、 栈的使用
Stack是Java提供的类，其中包含了可以对栈进行一系列操作的常见方法
栈的方法：
| 方法 | 功能 |
| Stack （ ） | 构造一个空的栈 |
| E push ( E e） | 将e入栈,并返回e |
| E pop ( ) | 将栈顶元素出栈并返回 |
| E peek ( ) | 获取栈顶元素 |
| int size ( ) | 获取栈中有效元素个数 |
| boolean empty ( ) | 检测栈是否为空 |
代码示例：
public static void main(String[] args) { Stack<Integer> stack=new Stack<>(); stack.push(40); stack.push(30); stack.push(20); stack.push(10); System.out.println(stack);//[40, 30, 20, 10] System.out.println(stack.search(new Integer(40)));//返回40下标4 System.out.println(stack.pop());//删除栈顶元素10并返回 System.out.println(stack.peek());//获取栈顶元素 20 }public class MyQueue { // 双向链表节点 public static class ListNode{ ListNode next; ListNode prev; int value; ListNode(int value){ this.value = value; } } ListNode first; // 队头 ListNode last; // 队尾 int size = 0; // 入队列---向双向链表位置插入新节点 public void offer(int e){ ListNode newNode = new ListNode(e); if(first == null){ first = newNode;// last = newNode; }else{ last.next = newNode; newNode.prev = last;// last = newNode; } last = newNode; size++; } // 出队列---将双向链表第一个节点删除掉 public int poll(){// 1. 队列为空// 2. 队列中只有一个元素----链表中只有一个节点---直接删除// 3. 队列中有多个元素---链表中有多个节点----将第一个节点删除 int value = 0; if(first == null){ return -1; }else if(first == last){ last = null; first = null; }else{ value = first.value; first = first.next; first.prev.next = null; first.prev = null; } --size; return value; } // 获取队头元素---获取链表中第一个节点的值域 public int peek(){ if(first == null){ return -1; } return first.value; } public int size() { return size; } public boolean isEmpty(){ return first == null; }}目录
栈
1、队列模拟实现
3、概念
2、
代码实例：
public class Mystack { int []elem; int size; public Mystack(){ elem=new int[10]; } public int push(int e){ ensureCapacity(); elem[size++] = e; return e; } public int peek(){ if(empty()){ throw new RuntimeException("栈为空，无法获取栈顶元素"); } return elem[size-1]; } public boolean empty(){ return 0 == size; } public int pop(){ int e = peek(); size--; return e; }//扩容 private void ensureCapacity(){ if(size==elem.length) elem= Arrays.copyOf(elem,size*2); }}栈、函数栈帧；这里对这几个概念进行一个浅浅的区分
- 栈是一种数据结构
- 虚拟机栈是JVM的一块内存
- 函数栈帧是调用方法时为方法开辟的一块内存
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()); } }
Queue方法：
| 方法 | 功能 |
| boolean offer (E e ) | 入队列 |
| E poll ( ) | 出队列 |
| peek ( ) | 获取队头元素 |
| int size ( ) | 获取队列有效元素个数 |
| boolean isEmpty( ) | 检测队列是否为空 |
有三种办法：
- 计数器：通过添加 count 属性记录
- 使用标记，定义boolean 类型元素
- 保留一个位置不放元素（判断rear下一个是否为 front ）
小伙伴可以做道题练练手
设计循环队列
用数组实现队列时：
用循环队列可以解决空间浪费的问题
如何用代码将数组是变为循环队列
rear向后移动公式
rear =（ rear+1）% array.length
rear向前移动公式
rear =（ rear-1+ array.length）% array.length
在未放元素时，rear=front，随着元素放满，rear与front相遇时，代表队列已满。
队列的使用4、 循环队列
为什么要有循环列队
如何区分空与满
5、
来道例题：
1. 若进栈序列为 1,2,3,4 ，进栈过程中可以出栈，则下列不可能的一个出栈序列是（）A: 1,4,3,2 B: 2,3,4,1 C: 3,1,4,2 D: 3,4,2,1
注意： 进栈过程中可以出栈，答案选C
3、 环形队列通常使用数组实现。 栈的模拟实现
相关概念区分
队列
1、
概念