品牌网站建设开发价格,WordPress建站 seo,衡水网站建设多少钱,北京seo关键词栈
栈的概念
栈#xff1a;一种特殊的线性表#xff0c;其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶#xff0c;另一端称为栈底。栈中的数据元素遵守先进后出LIFO#xff08;Last In First Out#xff09;的原则。大家可以理解为…栈
栈的概念
栈一种特殊的线性表其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶另一端称为栈底。栈中的数据元素遵守先进后出LIFOLast In First Out的原则。大家可以理解为给弹匣压子弹先压的子弹在最后才能打出概念图如下 栈的简单实用
public class Main {public static void main(String[] args) {StackInteger s new Stack(); //Integer表示栈中全是整形数据s.push(1); //向栈中压入12 3 4s.push(2);s.push(3);s.push(4);System.out.println(s.size()); // 获取栈中有效元素个数--- 4System.out.println(s.peek()); // 获取栈顶元素--- 4 peek只获取栈顶元素并不出栈s.pop(); // 4出栈栈中剩余1 2 3栈顶元素为3 pop出栈栈顶由原来的4变为3System.out.println(s.pop()); // 3出栈栈中剩余1 2 栈顶元素为3if(s.empty()){System.out.println(栈空);}else{System.out.println(s.size());}}
}
栈的模拟实现
import java.util.Arrays;public class MyStack {int[] arr; // 使用数组来模拟栈的实现int size0; //用size来记录入栈时的下标public MyStack() {arrnew int[3]; //初试化开始数组的长度为3}public void push(int val){expansion(); //定义一个函数来判断数组是否满了如果满了就为数组进行扩容arr[size]val; size; //为数组赋值后下标后移}public int peek(){if(isempty()){System.out.println(栈为空);}return arr[size-1]; //在push中将size了要获取栈顶元素将下标前移一位}public int pop(){if(isempty()){System.out.println(栈为空);}int s arr[size-1];size--; //弹出一个数据后有效位前移一位return s;}public boolean isempty(){if(size0){return true;}else return false;}public void expansion(){if(sizearr.length){ //有效位和数组长度相等表面数组不够用了需要扩容arr Arrays.copyOf(arr,size*2);}}}概念区分栈、虚拟机栈、栈帧有什么区别呢
栈一般数据结构概念用于实现LIFO先进后出行为。
虚拟机栈JVM为每个线程分配的私有栈用于存储方法调用状态。
栈帧虚拟机栈中的基本单元代表单个方法调用的执行状态。
队列Queue
概念
只允许在一端进行插入数据操作在另一端进行删除数据操作的特殊线性表和栈正好相反栈是先进后出队列是先进先出进行插入插入操作的一端称为队尾进行删除操作的一段称为对头
队列的简单使用
public static void main(String[] args) {
QueueInteger q new LinkedList();
q.offer(1);
q.offer(2);
q.offer(3);
q.offer(4);
q.offer(5); // 从队尾入队列
System.out.println(q.size());
System.out.println(q.peek()); // 获取队头元素
q.poll();
System.out.println(q.poll()); // 从队头出队列并将删除的元素返回
if(q.isEmpty()){
System.out.println(队列空);
}else{
System.out.println(q.size());
}
}
循环队列的实现
一个循环队列的实现需要实现一下功能
class MyCircularQueue {//构造器设置队列长度为 kpublic MyCircularQueue(int k) {}//向循环队列插入一个元素。如果成功插入则返回真。public boolean enQueue(int value) {}//从循环队列中删除一个元素。如果成功删除则返回真public boolean deQueue() {}//从队首获取元素。如果队列为空返回 -1public int Front() {}//获取队尾元素。如果队列为空返回 -1public int Rear() {}//检查循环队列是否为空public boolean isEmpty() {}//检查循环队列是否已满public boolean isFull() {}
}
我们使用数组来一步一步的实现在下图中红色字体代表循环队列的下标蓝色字体代表下标对应的值front代表啊队头rear代表队尾 循环队列的满与空
有上图可以得出当对头和队尾相遇的时候说明整个队列满了这时就又有一个问题如果rearfront表示队列满了当队列为空时rear也是等于front的这样就不好区分了所以我们可以浪费一个空间当rear走到下标为6的位置就表明整个队列满了下标为7的位置浪费掉以此来区分 ‘满’ 与 ‘空’ 的区别代码如下
class MyCircularQueue {public int front;public int rear;int [] elem;//构造器设置队列长度为 kpublic MyCircularQueue(int k) {elemnew int[k1]; //因为浪费了一个空间所以在初试化的时候要求给k个空间//实际给了k1个空间}//向循环队列插入一个元素。如果成功插入则返回真。public boolean enQueue(int value) {}//从循环队列中删除一个元素。如果成功删除则返回真public boolean deQueue() {}//从队首获取元素。如果队列为空返回 -1public int Front() {}//获取队尾元素。如果队列为空返回 -1public int Rear() {}//检查循环队列是否为空public boolean isEmpty() {return frontrear;}//检查循环队列是否已满public boolean isFull() {return (rear1)%elem.lengthfront;//这里大家可以当一个公式记住当前下标加1 % 整个数组的长度得到下一个下标的位//下一个下标的位置和对头相等代表数组满了}
}
入队操作
当队列不满的时候才能进行入队操作所以要先判断队列是否满了当队列不满的时候直接在队尾rear的位置上赋值rear再前移一个位置代码如下
public boolean enQueue(int value) {if(isFull()){return false; //判断队列是否满了}elem[rear]value; //给队尾赋值rear (rear1)%elem.length; //rear位置前移return true;}
删除对头操作
删除对头的时候要先判断队列是否为空当队列不为空的时候front前移一个位置得到对头元素同理
//从循环队列中删除一个元素。如果成功删除则返回真
public boolean deQueue() {if(isEmpty()){return false;}front(front1)%elem.length;return true; }//从队首获取元素。如果队列为空返回 -1public int Front() {if(isEmpty()){return -1;}return elem[front];}
获得队尾元素
队尾的元素为下标rear前一个位置的元素所以当rear为0时队尾的下标不可能时-1应为队列长度-1完整代码如下
class MyCircularQueue {public int front;public int rear;int [] elem;//构造器设置队列长度为 kpublic MyCircularQueue(int k) {elemnew int[k1];}//向循环队列插入一个元素。如果成功插入则返回真。public boolean enQueue(int value) {if(isFull()){return false;}elem[rear]value; //给队尾赋值rear (rear1)%elem.length; //rear位置后移return true;}//从循环队列中删除一个元素。如果成功删除则返回真public boolean deQueue() {if(isEmpty()){return false;}front(front1)%elem.length;return true;}//从队首获取元素。如果队列为空返回 -1public int Front() {if(isEmpty()){return -1;}return elem[front];}//获取队尾元素。如果队列为空返回 -1public int Rear() {if(isEmpty()){return -1;}int index (rear0)?elem.length-1:rear-1;return elem[index];}//检查循环队列是否为空public boolean isEmpty() {return frontrear;}//检查循环队列是否已满public boolean isFull() {return (rear1)%elem.lengthfront;}
}
有帮助麻烦点个支持哈
