😽个人主页： 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. }
总结
栈与队列，说到底也就是一种逻辑结构，可以用很多种方法实现。
