原文链接：https://blog.csdn.net/fear_wolf/article/details/127459611
文章目录
一、栈（Stack）
（一）概念
（二）栈的使用
（三）栈的模拟实现
（四）问题思考
1. 栈，虚拟机栈，栈帧有什么区别？
2.单链表能否实现栈，如果可以，为什么？
二、队列（Queue）
（一）概念
（二）队列的使用
（三）队列模拟实现
1.顺序表的写法
2.链表的写法
（四）循环队列
1.如何区分空与满
（五）顺序结构和链式结构比较
三、双端队列（Deque）
一、栈（Stack）
（一）概念
栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In FirstOut）的原则
压栈：栈的插入操作，叫做进栈/压栈/入栈，入数据在栈顶
出栈：栈的删除操作叫做出栈，出数据在栈顶。
（二）栈的使用
方法 功能
Stack() 构造一个空的栈
E push(E e) 将e入栈，并返回e
E pop() 将栈顶元素出栈并返回
E peek() 获取栈顶元素但不弹出
int size() 获取栈中有效元素个数
boolean empty() 检测栈是否为空
（三）栈的模拟实现
class MyStack{
private int[] arr;
private int usedSize = 0;
private static final int DEFAULT_QUANTITY = 10;
public MyStack() {
this.arr = new int[DEFAULT_QUANTITY];
}
//push方法，向栈中增加元素
public int push(int data) {
if(isFull()) {
arr = Arrays.copyOf(arr,arr.length * 2);
}
arr[usedSize] = data;
usedSize++;
return data;
}
//判断是否栈满
public boolean isFull() {
return usedSize == arr.length;
}
//让最上面的元素出栈
public int pop() {
if(empty()) {
throw new MyEmptyStackException("栈为空！");
}
usedSize--;
return arr[usedSize];
}
//查看最上面的元素但不出栈
public int peek() {
if(empty()) {
throw new MyEmptyStackException("栈为空！");
}
return arr[usedSize - 1];
}
//判断栈是否为空
public boolean empty() {
return usedSize == 0;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
我们可以从集合那一节的图中看出，Stack继承了Vector，Vector和ArrayList类似，都是动态的顺序表，不同的是Vector是线程安全的
（四）问题思考
1. 栈，虚拟机栈，栈帧有什么区别？
栈：是一种先进后出的数据结构
虚拟机栈：是JVM的一块内存空间
栈帧：是在调用方法（函数）的过程当中，在Java虚拟机栈上开辟的一块内存
2.单链表能否实现栈，如果可以，为什么？
目前实现的栈，底层是数组实现，所以也可以叫做顺序栈。那么，单链表能否实现栈，如果可以，为什么？
答：
首先可以实现。
我们可以采用头插法来入栈，每次出栈时删除的也是头节点，时间复杂度也是O（1），但仍没有顺序栈方便，毕竟顺序栈不用修改指向
二、队列（Queue）
（一）概念
队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out)
入队列：进行插入操作的一端称为队尾（Tail/Rear）
出队列：进行删除操作的一端称为队头（Head/Front）
（二）队列的使用
在Java中，Queue是个接口，底层是通过链表实现的
方法 功能
boolean offer(E e) 入队列
E poll() 出队列
E peek() 获取队头元素但不出队
int size() 获取队列中有效元素个数
boolean isEmpty() 检测队列是否为空
除上述介绍的offer方法可以增加元素之外，本身Queue还有一个add方法也可以增加元素，二者使用场景不同，add主要用在队列长度受限制的时候，此时如果队列满但调用add就会抛出异常， 而offer主要用在队列长度不受限制的时候，offer不会抛出异常，因为根本没有队列满的概念
注意：Queue是个接口，在实例化时必须实例化LinkedList的对象，因为LinkedList实现了Queue接口
（三）队列模拟实现
队列中既然可以存储元素，那底层肯定要有能够保存元素的空间，通过前面线性表的学习了解到常见的空间类型有两种：顺序结构和链式结构，那么思考队列的实现是使用顺序结构好还是链式结构好？
我们将两种方法都写明，并分别画图介绍两种方法
1.顺序表的写法
class MyCircularQueue {
private int[] arr;
private int usedSize;
private int front;
private int rear;
public MyCircularQueue(int k) {
arr = new int[k];
}
public boolean enQueue(int value) {
if(isFull()) {
return false;
}
arr[rear] = value;
rear = (rear + 1) % arr.length;
usedSize++;
return true;
}
public boolean deQueue() {
if(isEmpty()) {
return false;
}
front = (front + 1) % arr.length;
usedSize--;
return true;
}
public int Front() {
if(isEmpty()) {
return -1;
}
return arr[front];
}
public int Rear() {
if(isEmpty()) {
return -1;
}
int temp = (rear - 1 + arr.length) % arr.length;
return arr[temp];
}
public boolean isEmpty() {
if(usedSize == 0) {
return true;
}
return false;
}
public boolean isFull() {
if(usedSize == arr.length) {
return true;
}
return false;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
2.链表的写法
public class MyLinkedQueue {
public static class ListNode{
int val;
ListNode next;
public ListNode(int val) {
this.val = val;
}
}
ListNode head = new ListNode(0);
private int usedSize;
private ListNode front = head.next;
private ListNode rear = head.next;
//用链表作为队列的元素，不再存在队列满的情况，只有堆满的情况
//入队
public boolean enQueue(int value) {
ListNode Node = new ListNode(value);
if(isEmpty()) {
head.next = Node;
front = Node;
rear = Node;
}else {
rear.next = Node;
rear = rear.next;
}
usedSize++;
return true;
}
//出队，删除队首元素
public boolean deQueue() {
if(isEmpty()) {
return false;
}
if(front == rear) {
head.next = null;
front = null;
rear = null;
}else {
head.next = front.next;
front = head.next;
}
usedSize--;
return true;
}
//返回队首元素
public ListNode Front() {
if(isEmpty()) {
return null;
}
return front;
}
//返回队尾元素
public ListNode Rear() {
if(isEmpty()) {
return null;
}
return rear;
}
public boolean isEmpty() {
return usedSize == 0;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
（四）循环队列
循环队列就是通过顺序表实现的成果
front作为队列头
rear作为队列尾
数组下标循环的技巧
(front/rear + array.length) % array.length
1.如何区分空与满
通过添加 size 属性记录
直接判断if(size >= array.length)即可
保留一个位置
我们采取舍弃一个位置的方法，让rear永远指向队尾的下一个位置。那么当队空时rear == front，队不为空时，rear都是front之后，随着入队出队的操作，最终当(rear + array.length) % array.length + 1 == front，就表示队满
使用标记
即当第一次相遇的时候置为 什么，第二次相遇的时候置为 什么
（五）顺序结构和链式结构比较
队列采用顺序结构还是链式结构我们从它的存储方式来看
顺序存储在物理逻辑上都是连续的，链式存储只是在物理上是连续的，相比较而言顺序存储在主观上似乎更符合队列的数据结构
顺序结构的入队出队需要计算位置坐标，链式结构入队出队操作需要修改指向，链表修改指向的操作我们更加熟练
顺序结构的空间一般在实例化的时候就要给出，并且之后很难扩容，要么会造成浪费，要么就是出现队满的情况。而链式结构就没有队满的概念
综合来看，链式结构是最优的选择
三、双端队列（Deque）
双端队列（deque）是指允许两端都可以进行入队和出队操作的队列，deque 是 “double ended queue” 的简称。
那就说明元素可以从队头出队和入队，也可以从队尾出队和入队
Deque是一个接口，使用时必须创建LinkedList的对象
由于在实际开发中Deque使用的并不是非常多，所以不再做过多说明
————————————————
版权声明：本文为CSDN博主「求索1024」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/fear_wolf/article/details/127459611