算法与数据结构之队列和栈
2021/10/9 11:38:28
本文主要是介绍算法与数据结构之队列和栈,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
先入先出的数据结构
在 FIFO 数据结构中,将首先处理添加到队列中的第一个元素。
如上图所示,队列是典型的 FIFO 数据结构。插入(insert)操作也称作入队(enqueue),新元素始终被添加在队列的末尾。 删除(delete)操作也被称为出队(dequeue)。 你只能移除第一个元素。
实现队列:
通过一个动态数组和一个指向队首的索引就可以实现。实现的思路很简单,只需要实现入队和出队的操作,入队操作只用在动态数组后添加元素即可,出队操作需要先判断队列是否为空,非空的时候只用将队首的索引加一即可,
在判断队列是否为空时只用判断索引和这个动态数组的大小,因为这个动态数组的大小不会改变,因此只要这个索引小于数组大小就证明队列中有元素。
缺点:随着队列的元素的增加,指针的往后移动,会存在很大的空间浪费。
class QueueClass { // store elements private List<Integer> data; // a pointer to indicate the start position private int p_start; public QueueClass() { data = new ArrayList<Integer>(); p_start = 0; } /** Insert an element into the queue. Return true if the operation is successful. */ public boolean enQueue(int x) { data.add(x); return true; }; /** Delete an element from the queue. Return true if the operation is successful. */ public boolean deQueue() { if (isEmpty() == true) { return false; } p_start++; return true; } /** Get the front item from the queue. */ public int Front() { return data.get(p_start); } /** Checks whether the queue is empty or not. */ public boolean isEmpty() { return p_start >= data.size(); } }; class Main { public static void main(String[] args) { QueueClass q = new QueueClass(); q.enQueue(5); q.enQueue(3); if (q.isEmpty() == false) { System.out.println(q.Front()); } q.deQueue(); if (q.isEmpty() == false) { System.out.println(q.Front()); } q.deQueue(); if (q.isEmpty() == false) { System.out.println(q.Front()); } } }
循环队列
此前,我们提供了一种简单但低效的队列实现。
更有效的方法是使用循环队列。 具体来说,我们可以使用固定大小的数组和两个指针来指示起始位置和结束位置。 目的是重用我们之前提到的被浪费的存储。
这篇关于算法与数据结构之队列和栈的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-01基于Python+Vue开发的医院门诊预约挂号系统
- 2024-10-01基于Python+Vue开发的旅游景区管理系统
- 2024-10-01RestfulAPI入门指南:打造简单易懂的API接口
- 2024-10-01初学者指南:了解和使用Server Action
- 2024-10-01Server Component入门指南:搭建与配置详解
- 2024-10-01React 中使用 useRequest 实现数据请求
- 2024-10-01使用 golang 将ETH账户的资产平均分散到其他账户
- 2024-10-01JWT用户校验课程:从入门到实践
- 2024-10-01Server Component课程入门指南
- 2024-09-30Dnd-Kit学习:新手快速入门指南