栈与队列（详解）

大家好，欢迎来到IT知识分享网。

日升时奋斗，日落时自省 

目录

一、栈

1.1栈的基本概念

 1.2栈的模拟实现

1.3栈的使用 

1.4栈的应用场景

 二、队列

2.1队列的概念

 2.2模拟实现队列

2.3队列的使用

 2.4循环队列

一、栈

1.1栈的基本概念

栈：是一种特殊的线性表，栈只允许在固定的一端进行插入和删除元素操作，进行数据删除和插入时，一端是栈顶，另一端是栈低，栈中遵循元素先入后出

压栈：就是将数据放入栈中。

出栈：栈的删除操作叫做出栈。弹出栈

 1.2栈的模拟实现

栈的底层实现时依靠顺序表也就是数组实现的，这里模拟实现也是数组构成的栈

 栈入通过这张图比较好理解

栈出下图解释：

 栈出并不是真的删除某个值，而是将有效值的个数减一。

问题？下次还会栈出吗，不会因为我们栈出有效栈的数据个数，下次push时就会将原来的数据覆盖

public class MyStack { public int[] elem; //建立当前数组 构建栈空间 public int usedSize; //计算当前栈中的个数 public static final int DEFULT_SIZE=10; //暂时给定栈中为10个空间 public MyStack(){ this.elem=new int[DEFULT_SIZE]; //构造方法传值 } public int push(int val){ //入栈 //1、入栈限制，栈是否满了 //2、将传入的数据给数组，入栈结束 if(isFull()){ this.elem= Arrays.copyOf(this.elem,2*this.elem.length); //如果空间不够，进行扩容 } this.elem[usedSize]=val; //将只当前值直接给数组的最后一位 usedSize++; //数组个数加一 return val; //直接返回当前传入值就行了 } private boolean isFull(){ //栈满的条件 有效数据个数与数组长度相等 return this.usedSize==elem.length; } public int pop(){ //出栈 //1、栈是否为空 为空就抛出异常 //2、栈出数据，将当前数据存给一个变量 if(Empty()){ throw new EmptyWrongExpection("为空"); } int ret=this.elem[usedSize-1]; //usedSize-1表示的最后一个数据 usedSize--; //这里是栈出所以要删除 有效个数减减 return ret; } public boolean Empty(){ //为空条件 数据个数为零 return this.usedSize==0; } public int peek(){ //探 栈顶元素 与栈出相近 //1、先判断是否为空 为空抛出异常 //2、后来在进行当前值返回即可 if(Empty()){ throw new EmptyWrongExpection("为空"); } return this.elem[this.usedSize-1]; } }

1.3栈的使用 

模拟实现中，已经实现了栈出（push）、栈入（pop）、和探顶（peek）、检测栈空（empty）

 调用数据库中的函数库中的栈

1.4栈的应用场景

1. 若进栈序列为 1,2,3,4 ，进栈过程中可以出栈，则下列不可能的一个出栈序列是（C）
A: 1,4,3,2 B: 2,3,4,1 C: 3,1,4,2 D: 3,4,2,1
 

 二、队列

2.1队列的概念

出队列：进行删除操作的一端称为队头

 2.2模拟实现队列

队列在库函数中是有双向链表实现的，我们这里模拟实现就用单链表来实现

public class MyQueue { //单链表实现队列 以尾插来入队，从头开始出队 static class ListNode{ public int val; public ListNode next; public ListNode(int val){ this.val=val; } } public ListNode head; //设置一个头结点 public ListNode tail; //设置一个尾结点 public int usedSize; //计算队列的个芜湖市 public void offer(int val){ //插入队列，尾插 ListNode node=new ListNode(val); if(head==null){ //队中没有东西的时候，直接尾插，要动用头和尾 head=tail=node; }else{ tail.next=node; //没有特殊情况下，尾巴移动构成尾插 tail=node; } usedSize++; //当前是单链表实现的，所以对于 } public int poll(){ //出队，头结点 if(head==null){ return -1; } int ret=head.val; head=head.next; if(head==null){ //特殊情况，当前只有一个的时候被覆盖掉了当前head就是null然而这时候tail也与head相同了，两个域都应该被置空 tail=null; } usedSize--; return ret; } public int peek(){ if(head==null){ return -1; } return head.val; } public boolean empty(){ return usedSize==0; } public int getUsedSize(){ return usedSize; } }

2.3队列的使用

模拟队列中，实现了出队列，入队列，探队列头

 2.4循环队列

循环队列有数组构成

public class MyQueue_Elem_Second { private int[] elem; private int usedSize; public int front; //开头 public int rear; //末尾 public MyQueue_Elem_Second(int k){ elem=new int[k+1]; //为什么是k+1，使用数组循环队列就到导致有一个空间是空下来的 } public boolean enQueue(int value) { //入队 if(isFull()){ return false; } elem[rear]=value; //将当前传入值给数组的末尾 rear=(rear+1)% elem.length; //末尾以当前这种方法是为了，能够跳过7—》0的位置，构成循环 return true; } public boolean isFull(){ if((rear+1)% elem.length==front){ //判满的方法也是相同，当rear的下一个就是front 满 return true; } return false; } public boolean deQueue() { //出队 if(isEmpty()){ return false; } int ret=elem[front]; front=(front+1)% elem.length; return true; } public boolean isEmpty(){ //判空如何判断 rear在开始与front在相同位置，只要头与尾相同为空 if(rear ==front){ return true; } return false; } public int Rear(){ //找当前尾位置的时候不能直接找，可能在循环处就找不到 rear-1 if(isEmpty()){ return -1; } int index=(rear+1)% elem.length==0? elem.length -1:rear-1; //避免在循环处 return elem[index]; } public int Front(){ //为什么头位置不需要像位置一样麻烦 if(isEmpty()){ return -1; } return elem[front]; //本身的数据可以直接取，不需要 } }

队列循环的要点： 

 下标往后移动rear与front移动都不能直接+1，都会有从末尾到0的时候

所以向前的代码：

（rear+1）%数组长度

（front+1）%数组长度

三、队列与栈的区别

队列：数据是一端入队，另一端出队

原则：先入先出

栈：数据一端入栈，同一端出栈

原则：先入后出