JAVA_数据结构_栈和队列
1.栈（Stack）
1.1概念
栈是一种特殊的线性表，它只允许一端进行增删查改操作，它的头称为栈顶，进行压栈和出栈的操作，则另一端称为栈底，并且它遵循着先进后出的操作。
压栈：也可称为进栈/入栈，该功能为为栈添加数据，在栈顶操作。
出栈：该功能为栈删除数据，在栈顶操作。
先进后出：也可称为后进先出，相当于几个人进到一个细小的胡同里，里面只能一人并排走，则第一人进去后，第二个第三个依次进去，可这是个胡同，前面无路可走，要想出去就只能让最后一个人进来的人先出去，而最先进来的人是最后一个出去的，这就是先进后出/后进先出。
1.2栈的使用
- Stack：创建一个空的栈
- E push(E e)：为一个栈添加元素
- E peek()：取得栈顶元素不删除
- E pop()：取得栈顶元素并删除
- int size()：取得栈中的元素个数
- boolean isEmpty()：判断栈是否为空 是为true 不是为false
public static void main(String[] args) {
//1.创建栈
Stack<Integer> stack=new Stack<>();
//2.为栈添加元素
stack.push(1);
stack.push(1);
stack.push(1);
//3.取得栈顶元素 不删除
stack.peek();
//4.取得栈顶元素并删除
stack.pop();
//5.取得栈中的元素个数
stack.size();
//6.判断栈是否为空
stack.isEmpty();
}1.3栈的模拟实现
由于栈是单向进行操作，所以我们可以用数组来模拟实现栈。
public class MyStack {
//用数组模拟栈
public int []elem;
//有效数
public int usesize;
//初始数组大小
public static final int DEFAULT_SIZE=10;
//初始化数组
public MyStack(){
elem=new int[DEFAULT_SIZE];
}
//模拟入栈
public void push(int val){
//如果栈为满就扩容
if(isFull()){
grow();
}
//反之，插入元素，并增加有效数
elem[usesize]=val;
usesize++;
}
//模拟出栈
public int pop(){
//如果栈为空 就放回-1
if(isEmpty()){
return -1;
}
//先定义一个返回值
int val=elem[usesize];
//将数组减一 达到出栈的效果
usesize--;
//返回出栈的数字
return val;
}
//模拟返回栈顶元素
public int peek(){
//如果栈为空 就放回-1
if(isEmpty()){
return -1;
}
//放回数组第一个元素，模拟返回栈顶元素
return elem[usesize];
}
//模拟返回栈中元素的个数
public int size(){
//这边的有效数即栈的个数
return usesize;
}
//打印栈中元素个数
public void printStack(){
for(int i=0;i<usesize;i++){
System.out.println(elem[i]+" ");
}
}
//判断是否为满
public boolean isFull(){
//如果有效数==数组的长度 那么该数组就满了
return usesize==elem.length;
}
//扩容
public void grow(){
//扩容2倍
elem=Arrays.copyOf(elem,elem.length*2);
}
//判断是否为空
public boolean isEmpty(){
//如果有效数为0，那么就表示该数组中一个元素都没有，即栈为空
return usesize==0;
}
}2.队列（Queue）
2.1概念
队列是一端进行增加数据，另一端进行删除数据，增加数据的一端为尾，而它的头就进行删除数据，依据先进先出原则。
队头：进行数据的删除。
队尾：进行数据的增加。
先进先出：也可称为后进后出，就像现实中的排队打饭，从队尾开始排队，要想打到饭出去就只能到队头的时候，这就是先进先出/后进后出。
2.2队列的使用
在Java中，队列（Queue）是一个接口，底层通过链表来实现，所以示例化时需要依附于LinkedList对象，因为LinkedList实现了队列的接口。
1.Queue： 创建空的队列
2.void offer（E e）：为一个栈添加元素
3.E poll（）：取得队头元素并删除
4.E peek（）：取得队头元素不删除
5.int size（）：取得队列中元素的个数
6.boolean isEmpty（）： 判断队列是否为空，是返回treu 不是返回false
public static void main(String[] args) {
//1.创建空队列
Queue<Integer> queue=new LinkedList<>();
//2.为队列增加元素
queue.offer(1);
queue.offer(2);
queue.offer(3);
System.out.println(queue);
//3.取得队头元素并删除
queue.poll();
//4.取得队头元素不删除
queue.peek();
//5.取得队列中元素的个数
queue.size();
//6.判断队列是否为空
queue.isEmpty();
}2.3队列模拟实现
由于栈是进行双向操作的，所以这边我们使用链表来模拟实现栈。
public class MyQueue {
//因为使用链表模拟
//所以先创建Node节点
static class Node {
private int val;
private Node next;
private Node prev;
public Node(int val) {
this.val = val;
}
}
//链表头
public Node front;
//链表尾
public Node rear;
//模拟实现增加元素
public void offer(int val) {
//创建node变量接收要增加的元素
Node node = new Node(val);
//如果列表初始状态为空，
//那么加入的第一个元素就是这个链表的头尾
if (front == null) {
front = node;
rear = node;
}
//反之
//因为队列增加元素是在队尾
//所以这边我们使用尾插法模拟增加元素
rear.next = node;//将队列的的最后一个元素的下一个指向指向node
node.prev = rear;//将node的上一个指向指向列表的最后一个元素
rear = node;//将队列的尾部标识移动到新增加的元素的位置
}
//模拟实现取得队头元素
public int peek() {
//如果队列为空，返回-1
if (front == null) {
return -1;
}
//反之 返回头元素的值
return front.val;
}
//模拟实现取得队头元素并删除
public int poll() {
//如果队列为空，返回-1
if (front == null) {
return -1;
}
//先取得队头的元素
int val = front.val;
//将队头的元素移除
front = front.next;//队头为队头的下一元素
front.prev = null;//将对头的上一个指向改为null
return val;
}
//模拟实现取得队列中的元素个数
public int size() {
//定义一个cur元素为队头
Node cur = front;
//计数
int count = 0;
//但cur不为空时，计数一次并间cur往后移动一位
while (cur == null) {
count++;
cur = cur.next;
}
return count;
}
//模拟实现判断队列是否为空
public boolean isEmpty() {
//如果队头没有元素 那么这个队列就为空
return front == null;
}
//打印队列的元素
public void printfQueue() {
Node cur = front;
while (cur != null) {
System.out.print(cur.val + " ");
cur = cur.next;
}
}
}