---

1.栈

1.1 栈的定义

栈是一种特殊的线性表，其只允许在固定的一段进行数据的插入或者删除。一般，插入或删除元素的一端叫栈顶，栈顶的另一端一般叫做栈底。栈中的元素均遵循后进先出(LIFO)的原则。

1.2 栈的使用

栈的常用方法为：

方法	功能
Stack()	构造空栈
E push(E e)	将元素入栈，并返回该元素
E pop()	栈顶元素出栈并返回该元素
E peek()	获取栈顶元素
int size()	获取栈中的元素个数
boolean empty()	判断栈是否为空

public static void main(String[] args) {Stack<Integer> s=new Stack<>();s.push(1);s.push(2);s.push(3);System.out.println("栈的大小为:"+s.size());System.out.println("栈顶元素为:"+s.peek());System.out.println("出栈元素为:"+s.pop());System.out.println("出栈后的栈顶元素为:"+s.peek());s.pop();s.pop();if(s.empty()) {System.out.println("当前栈为空");}
}

1.3 栈的模拟实现

图中可以看出，Stack继承了Vector类，Vector和ArrayList类似，都是会动态增长的顺序表。

public class MyStack<E> {  private Object[] elem;private int elemSize;//构造方法public MyStack() {}public MyStack(int capacity) {}//元素入栈并返回public E push(E e) {}//元素出栈并返回public E pop() {}//获取栈顶元素public E peek() {}//获得栈中元素个数public int size() {}//判断是否为空栈public boolean empty() {}
}

1.入栈：

public E push(E e) {if(elem.length==elemSize) {this.elem=Arrays.copyOf(elem,2*elem.length);}elem[elemSize++]=e;return e;
}

2.出栈：

public E pop() {if(size()==0) {throw new RuntimeException("栈中不存在元素，无法删除");}E obj=peek();elemSize--;return obj;
}

3.获取栈顶元素

public E peek() {int len=size();if(len==0) {throw new RuntimeException("栈中不存在元素");}return (E)elem[len-1];
}

4.判空与获取大小

//获得栈中元素个数
public int size() {return elemSize;
}//判断是否为空栈
public boolean empty() {return elemSize==0;
}

5.测试结果：

2.队列

2.1 队列的定义

队列是一种特殊的线性表。其是只允许在一端进行插入，在另一端进行删除的结构。

插入端即队尾(Tail/Rear)，删除端为队头(Head/Front)。对元素的操作遵循先入先出(FIFO)的原则。

2.2 队列的使用

可以看到，LinkedList类实现了Queue接口，因此需要用LinkedList类来实例化对象；

方法	功能
boolean offer(E e)	将元素入队
E poll()	队头元素出队并返回该元素
E peek()	获取队头元素
int size()	获取队列中的元素个数
boolean isEmpty()	判断队列是否为空

public static void main(String[] args) {Queue<Integer> q=new LinkedList<>();q.offer(1);q.offer(2);q.offer(3);  //1,2,3System.out.println(q.poll()); System.out.println(q.peek());System.out.println("队列为空吗？"+q.isEmpty());
}

2.3 队列的模拟实现

队列的实现既可以用数组也可以用列表实现；虽然在Java中使用链表来实现队列，但其常数时间的并不是很好，因此，如果在刷题，尤其是竞赛等场景(数据量确定)，用数组去模拟队列会是更好的写法；

这里使用双端链表来模拟实现:

public class MyQueue<E> {class ListNode{private E val;private ListNode prev;private ListNode next;public ListNode(E val) {this.val=val;}}private ListNode head;  //头指针private ListNode tail;  //尾指针private int usedSize;   //当前队列大小//元素从队尾入队列public boolean offer(E e) {}//队头元素出队列public E poll() {}//获取队头元素public E peek() {}//获取队列元素个数public int size() {return usedSize;}//判断队列是否为空public boolean isEmpty() {return usedSize==0;}
}

1.入队列:

public boolean offer(E e) {ListNode node=new ListNode(e);//空队列if(usedSize==0) {head=tail=node;}else {tail.next=node;node.prev=tail;tail=tail.next;}this.usedSize++;return true;
}

2.出队列：

public E poll() {if(usedSize==0) {throw new RuntimeException("当前队列为空");}E obj=head.val;if(head==tail) {head=tail=null;}else {head=head.next;head.prev=null;}usedSize--;return obj;
}

3.获取队头元素：

public E peek() {if(usedSize==0) {throw new RuntimeException("队列为空");}return head.val;
}

4.测试结果：

3.循环队列

3.1 循环队列的概念

循环队列简单来说就是一个将队列的首尾相连接的特殊队列；循环队列通常采用数组实现；

3.2 循环队列判断空和满

1.使用size记录循环队列大小：

if(front==rear&&size==0)System.out.println("循环队列为空")
if(front==rear&&size!=0)System.out.println("循环队列为满")

2.使用标记：

1. 初始状态：队列为空，front==rear&&isFull=false
2. 入队前，检查front与rear是否重合，重合则isFull=true，即队列满，否则rear移动
3. 出队时，front移动，isFull=false

3.保留一个位置：

• 队列为空：front==rear
• 队列为满：(rear+1)%capacity
• rear的循环移动：rear=(rear+1)%capacity

4.双端队列Deque

双端队列是可以在两端均进行插入和删除的队列；即队头队尾均可以进行出队入队，

因此Deque既可以当作队列也可以当作栈使用。

Deque是接口，因此使用时必须用LinkedList创建对象。

Deque常见的实现类为：

Deque<Integer> stack=new ArrayDeque<>();
Deque<Integer> queue=new LinkedList<>();

-----------------------------------------------------------------------------完-----------------------------------------------------------------------------