欢迎来到尧图网

客户服务 关于我们

您的位置:首页 > 文旅 > 游戏 > 数据结构系列五:栈和队列

数据结构系列五:栈和队列

2025/3/17 6:28:26 来源:https://blog.csdn.net/Hi_Lyn/article/details/146232989  浏览:    关键词:数据结构系列五:栈和队列

一、栈

(一)概念

:是一种特殊的线性表,其只允许在固定的一段进行插入和删除元素操作,进行数据插入和删除操作的一端称为栈顶,另一端称为栈底,栈中的数据元素遵守后进先出的原则
压栈:栈的插入操作叫做进栈,入数据在栈顶
出栈:栈的删除操作叫做出栈,出数据在栈顶
在这里插入图片描述

栈在现实生活中的例子:

在这里插入图片描述

(二)栈的使用

我们可以看到Java中的Stack给了如下方法
在这里插入图片描述

import java.util.Stack;public class test {public static void main(String[] args) {Stack<Integer> stack = new Stack<>();stack.push(12);stack.push(23);stack.push(34);System.out.println(stack.peek());//看一下栈顶的元素但是不删除System.out.println(stack.pop());//删除栈顶元素System.out.println(stack.peek());//看一下栈顶的元素但是不删除System.out.println(stack.isEmpty());//判断栈是否为空System.out.println(stack.size());//栈中元素个数}
}//输出结果
34
34
23
false
2Process finished with exit code 0

(三)栈的模拟实现

栈的底层实际上就是一个数组,接下来我们来实现一下其中的操作

添加元素

//往栈中添加元素public void push(int val){if (isFull()){elem = Arrays.copyOf(elem,2*elem.length);}elem[usedSize] = val;this.usedSize++;}

判断是否为空栈

    public boolean isEmpty(){return usedSize == 0;}

弹出元素

public int pop(){if (isEmpty()){throw new no();}int oldVal = elem[usedSize-1];usedSize--;return oldVal;}

返回栈顶元素

public int peek(){if (isEmpty()){throw new no();}return elem[usedSize-1];}

(四)利用栈的特性逆序打印链表

在一个链表中,我们可以利用栈的特性,先进后出,来逆序打印这个链表

 public void reservePrintList(){Stack<ListNode> stack = new Stack<>();ListNode cur = head;while (cur != null){stack.push(cur);cur = cur.next;}while (!stack.isEmpty()){ListNode top =  stack.pop();System.out.print(top.val + " ");}}

二、队列

(一)概念

队列:只允许在一段进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先进先出的特征
入队列:进行插入操作的一端叫做队尾
出队列:进行删除操作的一端称为队头
在这里插入图片描述

(二)队列的使用

在这里插入图片描述

public static void main(String[] args) {Queue<Integer> queue1 = new LinkedList<>();//单向队列Deque<Integer> queue2 = new LinkedList<>();//双端队列queue1.offer(1);queue1.offer(2);queue1.offer(3);//从队尾入队列System.out.println(queue1.poll());//从队头出队列System.out.println(queue1.peek());//看一眼队头元素System.out.println(queue1.isEmpty());//判断队列是否为空}
//输出结果
1
2
falseProcess finished with exit code 0

(三)队列的模拟实现

队列中既然可以存储元素,那么底层肯定要有能够保存元素的空间,通过前面线性表的学习了解到常见的空间类型有两种:顺序结构链式结构,从实际情况来看,链式结构操作队列相对简单一些

插入元素

//头插法public void offer(int x){ListNode node = new ListNode(x);if (front == null){front = rear = node;}else {node.next = front;front.prev = node;front = node;}usedSize++;}

删除元素

//出队列public int poll() {if (front == null) {return -1;}int ret = front.val;if (front == rear) {front = null;rear = null;usedSize--;return ret;}front = front.next;front.prev = null;usedSize--;return ret;}

获取队头元素

public int peek(){if (front == null){return -1;}return front.val;}

求出队列长度

public int getUsedSize(){return usedSize;}

判断是否为空

public boolean isEmpty(){return usedSize == 0;}

三、循环队列

环形队列通过循环利用存储空间,避免了普通队列中因元素出队而导致的空间浪费问题。在普通队列中,当队列头部的元素被移除后,前面的存储空间无法再被利用,而环形队列则可以将这些空闲的空间重新用于存储新的元素
在这里插入图片描述

循环队列的方法

public class MuCircularQueue {private int[] elem;private int front;private int rear;public MuCircularQueue(int k){//采用浪费一个位置来判断是否为满,所以要多开辟一个格子的空间this.elem = new int[k+1];}public boolean isEmpty(){return  front == rear;}public boolean isFull(){if ((rear+1)%elem.length == front){return true;}return false;}//入队操作public boolean enQueue(int value){if (isFull()){return false;}elem[rear] = value;rear = (rear+1)%elem.length;return true;}//出队操作public boolean deQueue(){if (isEmpty()){return false;}front = (front+1)%elem.length;return true;}//得到队头元素public int Front(){if (isEmpty()){return -1;}return  elem[front];}//得到队尾元素public int Rear(){if (isEmpty()){return -1;}int index = (rear == 0)?elem.length-1:rear-1;return  index;}
}

四、双端队列

双端队列是指允许两端都可以进行入队和出队操作的队列,那就说明元素可以从队头出队和入队,也可以从队尾出队和入队

在这里插入图片描述
Deque是一个接口,使用时必须创建LinkedList的对象

在实际工程中,使用Deque接口是比较多的,栈和队列均可以使用该接口

public class demo {public static void main(String[] args) {Deque<Integer> stack = new ArrayDeque<>();//双端队列的线性实现Deque<Integer> queue = new LinkedList<>();//双端队列的链式实现stack.push(1);stack.pop();queue.offer(1);queue.poll();}
}

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

热搜词