目录
- 1.栈(Stack)
- 1.1 介绍
- 1.2 栈的实现
- 1.2.1 模拟实现栈
- 1.2.2 Stack类实现
- 1.3 栈的常用方法
- 1.4 栈,虚拟机栈和栈帧的区别
- 2.队列(Queue)
- 2.1 介绍
- 2.2 队列的实现
- 2.2.1 模拟实现队列
- 2.2.2 Queue接口实现
- 2.3 队列的常用方法
1.栈(Stack)
1.1 介绍
栈是一种特殊的线性表,只允许在固定的一端
进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶
,另一端称为栈底
。栈中的数据元素遵守后进先出
的原则
1.2 栈的实现
栈可以通过自己写代码来模拟实现,或直接使用java.util包
中的Stack类
实现
1.2.1 模拟实现栈
压栈(入栈)
:栈的插入操作,插入的数据在栈顶
出栈
:栈的删除操作,出数据在栈顶
java">import java.util.Arrays;public class MyStack {public int[] elem;public int usedSize;public static final int DEFAULT_CAPACITY = 10;public MyStack() {elem = new int[DEFAULT_CAPACITY];}public void push(int val) { //入栈if (isFull()) {this.elem = Arrays.copyOf(elem, elem.length * 2);}elem[usedSize++] = val;}public int pop() { //出栈if (isEmpty()) {throw new StackEmptyException("当前栈为空");}usedSize--;return elem[usedSize];}public int peak() {if (isEmpty()) {throw new StackEmptyException("当前栈为空");}return elem[usedSize - 1];}public boolean isFull() {return elem.length == usedSize;}public boolean isEmpty() {return usedSize == 0;}
}
1.2.2 Stack类实现
Stack类实现了后进先出的栈结构,使用Stack类可以直接创建一个栈
java">import java.util.Stack;
public class Main {public static void main(String[] args) {//创建一个栈,栈中元素类型为Integer(int的包装类)Stack<Integer> stack = new Stack();}
}
1.3 栈的常用方法
方法 | 功能 |
---|---|
Stack( ) | 构造一个空的栈 |
E push(E e) | 将e入栈,并返回e |
E pop( ) | 将栈定元素出栈并返回 |
E peek( ) | 获取栈定元素 |
int size( ) | 获取栈中有效元素个数 |
boolean empty( ) | 检测栈是否为空 |
1.4 栈,虚拟机栈和栈帧的区别
- 栈:一种数据结构
- 虚拟机栈:JVM中的一块内存
- 栈帧:方法调用过程中,在虚拟机栈上开辟的一块内存
2.队列(Queue)
2.1 介绍
队列也是一种特殊的线性表,不同于栈,队列只允许在一端
进行插入数据操作,在另一端
进行删除数据操作。进行插入操作的一端称为队尾
,进行删除操作的一端称为队头
。队列中的数据元素遵守先进先出
的原则
2.2 队列的实现
队列也可以通过自己写代码来模拟实现,或使用Queue接口来实现
2.2.1 模拟实现队列
java">public class MyQueue {static class ListNode {int val;ListNode prev;ListNode next;public ListNode(int val) {this.val = val;}}ListNode head;ListNode last;public void offer(int val) { //入队ListNode node = new ListNode(val);if (head == null) {head = node;last = node;} else {last.next = node;node.prev = last;last = node;}}public int poll() { //出队if (head == null) {return -1;}int val = head.val;if (head.next == null) {head = null;last = null;return val;}head = head.next;head.prev = null;return val;}public int peek() {if (head == null) {return -1;}return head.val;}public boolean isEmpty() {return head == null;}
}
2.2.2 Queue接口实现
LinkedList(双链表)实现了Queue接口(底层通过链表实现
),可以使用LinkedList类来创建队列
java">import java.util.LinkedList;
import java.util.Queue;
public class Main {public static void main(String[] args) {Queue<Integer> queue = new LinkedList<>();}
}
2.3 队列的常用方法
方法 | 功能 |
---|---|
boolean offer(E e) | 入队列 |
E poll( ) | 出队列 |
E peek( ) | 获取队头元素 |
int size( ) | 获取队列中有效元素的个数 |
boolean isEmpty( ) | 检测队列是否为空 |