Java~数据结构三~栈和队列Stack\Queue\Deque的常用方法和模拟实现栈和队列等
知识框架
- 栈和队列本质上都是线性表,只不过是特殊的线性表,操作收到了限制。
- 栈是线性表只允许在一端进出,而队列是线性表只允许一端进,一端出。
- Java中有栈的具体类Stack,而队列(Queue)只是定义了接口,所有实现了这个接口的具体类都可以当做一个队列来使用。
栈(Stack)
- 什么是栈?栈是一种特殊的线性表。只能在表的一端进行插入和删除。可以进行数据插入和删除的一端称为栈顶。另一端称为栈底。
- 栈中的元素遵循“先进后出”原则。(也就是后进先出,
Last In First Out
,所以也称为LIFO结构) - 空栈:不含有任何元素的空表。
如何实现一个栈?
- 在Java中,实现栈有两个方法:一个是Java本身的集合类型Stack类型。另一个是借用LinkedList来间接实现栈(其实链表或者数组都可以间接实现一个栈的功能,LinkedList就是链表,下面会用数组模拟实现一个栈)。
- Stack集合类型继承于Vector,由于Vector是通过数组实现的,所以Stack集合类型也是通过数组来实现的。
- 注意:我们平时所说的栈,是一种按照先入后出的线性存储结构。这种结构不仅用Java可以写,用C 也可以写。在Java中的栈,有两种实现方式,一种是本身的集合Stack,我们平常说的也就是这种。另一种就是用别的实现类来实现这种功能,比如LinkedList。(平时的Stack就是指Stack集合类型。而不是栈这种更广泛的概念。)
- LinkedList是双向链表,不仅仅能用来实现栈,还可以被用来实现队列或者双端队列。是一个比较“全能”的数据结构。因为LinkedList实现了List接口,所以可以进行队列的操作,还实现了Deque接口,所及还能当做双端队列使用。
栈(Stack)常用方法
常用方法使用:
使用1:
public static void main(String[] args) {
Stack<Integer> stack=new Stack<>();
//入栈
stack.push(1);
stack.push(2);
stack.push(3);
stack.push(4);
System.out.println("栈中有效元素个数:" stack.size());
System.out.println("获取栈顶元素" stack.peek());//获取栈顶元素,但是不弹出。
stack.pop();//出栈,元素4出栈,栈中剩余元素3,2,1
System.out.println("获取栈中的元素:" stack.pop());
System.out.println("栈中有效元素个数:" stack.size());//获取栈的长度
System.out.println("stack是否为空:" stack.isEmpty());//判断栈是否为空
}
模拟实现一个栈(包括栈常用方法)
class MyStack{
private int[] arr;
//size记录数组中元素个数
private int size;
public MyStack(){
this(12);//调用无参构造,默认最大容量12
}
public MyStack(int MaxSize){
this.arr=new int[MaxSize];
}
//入栈
public int push(int value){
if(this.size == arr.length){
//栈满 需要扩容
int[] copyArr;
//复制数组arr,数组扩充一倍
copyArr=Arrays.copyOf(arr,2*arr.length);
arr=copyArr;
}
//将元素添加到size位置
this.arr[size]=value;
//元素个数 1;
this.size ;
//返回添加元素
return value;
}
//出栈
public int pop(){
if(this.size == 0){
//没有元素
//抛出时运行异常,此处也可以自定义异常。
throw new RuntimeException("栈中没有元素,不能出栈..");
}
//获得栈顶元素
int value=this.arr[size-1];
//size-1之后,下一次插入时会覆盖原数据,利用覆盖替代删除。
this.size--;
return value;
}
//获取栈顶元素(peek)
public int peek(){
if(this.size == 0){
//没有元素
//抛出时运行异常,此处也可以自定义异常。
throw new RuntimeException("栈中没有元素,不能出栈..");
}
return this.arr[this.size - 1];
}
//获取元素个数
public int getSize(){
return this.size;
}
//判断栈是否为空
public boolean isEmpty(){
return this.size==0;
}
}
单向队列(Queue)和双端队列(Deque)
- 什么是队列?只允许在一端进行插入数据,在另一端进行删除数据的特殊线性表。进行插入操作的一端是队尾。进行删除操作的一端是队头。
- 队列具有先进先出的特性。
- 详细图:
- Java中有单向队列(Queue)和双向队列(Deque),Queue是个接口,实现了队列的基础方法。Deque是在继承Queue的基础上,增加了反向队列的方法,也包括栈的基础方法。
- (上图)Java中虽然有Queue接口,但是Java并没有给出具体的实现类(栈是直接给出了Stack实现类),而是让LinkedList实现了Queue接口,所以一般用LinkedList来实现链表。
单向队列Queue常用方法
- 注意:Queue中插入和删除都有两个方法可以实现,当我们使用队列时,通常采用
offer
添加元素和poll
删除元素。不适用add与remove方法。
使用:
public static void main(String[] args) {
Queue<Integer> q = new LinkedList<>();
//插入元素
q.offer(1);
q.offer(2);
q.offer(3);
q.offer(4);
q.offer(5);
System.out.println("元素个数 : " q.size()); // 获取元素个数 输出5
System.out.println("获取队头元素 : " q.peek()); // 获取队头元素,但不删除元素
q.poll();
System.out.println("出队列元素 : " q.poll()); // 从队头出队列,并将删除的元素返回
if(q.isEmpty()){
System.out.println("队列空");
}else{
System.out.println("元素个数 : " q.size());
}
}
双向队列Deque常用方法
循环队列
- 实际使用时,可能还会接触到循环队列,循环队列一般用数组实现。就是首尾相连。
- 使用循环队列可以解决用数组实现队列时的空间浪费问题。
- 代码实现:
public class MyCircularQueue {
private final int[] elem;
private int front; //队头下标
private int rear; //队尾下标
private int size;
public MyCircularQueue() {
elem = new int[24];
}
//入队列
public void offer(int val){
if(size == elem.length){
//可扩容,此处不实现
throw new RuntimeException("队列已满...");
}
elem[rear] = val;
//如果rear到达数组长度,则置0
if(rear 1 >= elem.length){
rear = 0;
}else {
rear ;
}
size ;
}
public int poll(){
if(size == 0){
throw new RuntimeException("队列为空...");
}
int val = elem[front];
if(front 1 >= elem.length){
front = 0;
}else {
front ;
}
size--;
return val;
}
//判断元素个数
public int size(){
return size;
}
//获取队首元素
public int peek(){
if(size == 0){
throw new RuntimeException("队列为空...");
}
return elem[front];
}
// 判断是否为空
public boolean isEmpty(){
return size == 0;
}
}
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanhgejaab
系列文章
更多
同类精品
更多
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
excel下划线不显示怎么办
PHP中文网 06-23 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
怎样阻止微信小程序自动打开
PHP中文网 06-13 -
TikTok加速器哪个好免费的TK加速器推荐
TK小达人 10-01