😽个人主页： tq02的博客_CSDN博客-C语言,Java,Java数据结构领域博主
🌈梦的目标：努力学习，向Java进发，拼搏一切，让自己的未来不会有遗憾。
🎁欢迎各位→点赞👍 + 收藏⭐ + 评论📝+关注✨
本章讲解内容：栈与队列 的讲解
使用编译器：idea
一. 栈
1.1栈的概念
栈，一种特殊的线性表，只允许在固定的一端进行插入和删除元素操作，可以想象为储物箱，可以放东西进去，也可以把东西取出来，但重点是，想取先放的东西，必须先将上层的东西取出。俗称：先进后出。
如图，C想入栈，只能放在最顶层，当要出栈时，也只能先取最高层 。
专业术语： 压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据在栈顶。
1.2.栈的实现
栈的实现，可以采取数组方式，也可以采取链表方式。无论代码怎么敲，只要可以实现栈的基本概念就行。
1.2.1数组实现 栈
栈的创建
class Mystack{ private in[] elem; //存储的元素个数 private int size; //如果没有给予空间，自动初始化 Mystack(){ elem=new int[10]; } //主动赋值空间。 Mystack(int num){ elem=new int[num]; } }
栈的基本方法实现
判断栈是否为空
//判断是否为空 public boolean isEmpty() { return size == 0; }
只需要判断记录数组储存元素数量的变量是否为零即可。
判断栈是否需要扩容
public void isFull(){ if(size==elem.length) { this.elem = Arrays.copyOf(this.elem,this.size*2); } }
只需要判断数组存储元素是否等于容器大小。
向栈添加元素（入栈）
public void Put(int num) { isFull(); elem[size]=num; size++; }
元素入栈需要判断是否栈是否满，需要扩容。
从栈中移出元素（出栈）
public void Pop() { if(!isEmpty()) { elem[size]=0; size--; } }
先判断是否为空栈，如果为空，无法移除元素，如果不为空直接size--；元素减一。
1.2.2链表实现 栈
栈的创建
public class MyStack{ static class stack{ private int val; private stack next; stack(){}; stack(int num){ this.num=num; } //定义一个节点，为栈顶； stack pophead=null; //判断栈是否为空 public boolean isEmple(){}; //添加元素入栈 public void Pop(int num){}; //移出元素 出栈 public void remove(){};
栈的基本方法实现
判断栈是否为空
public boolean isEmpty() { return pophead==null?true:false ; }
向栈添加元素（入栈）
public void Pop(int num) { if(isEmpty()) { head.val=num; } else if{ stack kk=new stack(num); kk.next=pophead; pophead=kk; } }
先判断头结点是否为空，如果头结点为空，则直接赋值给头结点，使用链表的头插法，将元素放在首位。
从栈中移出元素（出栈）
public void remove() { if(isEmpty()) { return; } pophead=pophead.next; }
移出首位元素，链表的头删法。
二.队列
2.1队列的概念
队列：相当于单行车道，只允许一端出，一端进。分别对应删除元素和增加元素
2.2队列的实现
哪种存储方式符合队列的性质呢？第一种：数组 第二种：链表。
数组实现：
如图所示：使用数组，如果插入元素，则全体元素向后移动一位，再将首元素为 8。就可以实现了。但是需要记 末尾元素的下标值。
链表实现：
链表存放，采取头插法，每一个新进入的元素，插在头部。
2.3代码实现
2.3.1队列代码的构建
我们采取使用链表的方法实现，以下是链表的构建。
public class Queue { // 双向链表节点 public static class ListNode{ ListNode next; int value; ListNode(int value){ this.value = value; } } ListNode first; // 队头 ListNode last; // 队尾 int size = 0; // 入队列---向链表位置插入新节点 public void offer(int e){}; // 出队列---将双向链表第一个节点删除掉 public int poll(); // 获取队头元素---获取链表中第一个节点的值域 public int peek(); //获取队列长度 public int size(); //判断队列是否为空 public boolean isEmpty()；
2.3.2 队列 基础方法实现
入队：
public void offer(int e){ ListNode newNode = new ListNode(e); //设置一个新的结点，存放该元素，此时会面临2种情况 第一种，该链表为空链表，第一次插入元素。 第二种，该链表有元素，此时需要使用头插法。 if(first == null){ first = newNode; }else{ newNode.next= first; first=newNode; } size++; //元素加一 }
出队：
// 1. 队列为空 // 2. 队列中有元素---链表中有一至多个节点----将末尾节点删除 public int poll(){ ListNode newNode =first; int value = 0; if(first == null){ return null; }else { while(newNode.next!=null) { newNode=newNode.next; } value=newNode.value; newNode=null; //将最后的一个结点置空。 } --size; return value; }
获取队头元素：
public int peek(){ if(first == null){ return null; } return first.value; }
获取队列长度：
public int size() { return size; }
判断队列是否为空：
1. public boolean isEmpty(){ 2. return first == null; 3. }
总结
栈与队列，说到底也就是一种逻辑结构，可以用很多种方法实现。
