文档章节

数据结构与算法02 之栈与队列

乐在克里特
 乐在克里特
发布于 2017/02/23 14:57
字数 1028
阅读 0
收藏 0
点赞 0
评论 0

       我们知道,在数组中,若知道数据项的下标,便可立即访问该数据项,或者通过顺序搜索数据项,访问到数组中的各个数据项。但是栈和队列不同,它们的访问是受限制的,即在特定时刻只有一个数据项可以被读取或者被删除。众所周知,栈是先进后出,只能访问栈顶的数据,队列是先进先出,只能访问头部数据。这里不再赘述。

    栈的主要机制可以用数组来实现,也可以用链表来实现,下面用数组来实现栈的基本操作:

 

  1. public class ArrayStack {  
  2.     private long[] a;  
  3.     private int size; //栈数组的大小  
  4.     private int top; //栈顶  
  5.   
  6.     public ArrayStack(int maxSize) {  
  7.         this.size = maxSize;  
  8.         this.a = new long[size];  
  9.         this.top = -1//表示空栈  
  10.     }  
  11.       
  12.     public void push(long value) {//入栈  
  13.         if(isFull()) {  
  14.             System.out.println("栈已满!");  
  15.             return;  
  16.         }  
  17.         a[++top] = value;  
  18.     }  
  19.       
  20.     public long peek() {//返回栈顶内容,但不删除  
  21.         if(isEmpty()) {  
  22.             System.out.println("栈中没有数据");  
  23.             return 0;  
  24.         }  
  25.         return a[top];  
  26.     }  
  27.       
  28.     public long pop() { //弹出栈顶内容,删除  
  29.         if(isEmpty()) {  
  30.             System.out.println("栈中没有数据!");  
  31.             return 0;  
  32.         }  
  33.         return a[top--];          
  34.     }  
  35.       
  36.     public int size() {  
  37.         return top + 1;  
  38.     }  
  39.       
  40.     public boolean isEmpty() {  
  41.         return (top == -1);  
  42.     }  
  43.       
  44.     public boolean isFull() {  
  45.         return (top == size -1);  
  46.     }  
  47.       
  48.     public void display() {  
  49.         for(int i = top; i >= 0; i--) {  
  50.             System.out.print(a[i] + " ");  
  51.         }  
  52.         System.out.println("");  
  53.     }  
  54. }  

 

    数据项入栈和出栈的时间复杂度均为O(1)。这也就是说,栈操作所消耗的时间不依赖于栈中数据项的个数,因此操作时间很短。栈不需要比较和移动操作。

    队列也可以用数组来实现,不过这里有个问题,当数组下标满了后就不能再添加了,但是数组前面由于已经删除队列头的数据了,导致空。所以队列我们可以用循环数组来实现,见下面的代码:

 

  1. public class RoundQueue {  
  2.     private long[] a;  
  3.     private int size;   //数组大小  
  4.     private int nItems; //实际存储数量  
  5.     private int front;  //头  
  6.     private int rear;   //尾  
  7.   
  8.     public RoundQueue(int maxSize) {  
  9.         this.size = maxSize;  
  10.         a = new long[size];  
  11.         front = 0;  
  12.         rear = -1;  
  13.         nItems = 0;  
  14.     }  
  15.       
  16.     public void insert(long value) {  
  17.         if(isFull()){  
  18.             System.out.println("队列已满");  
  19.             return;  
  20.         }  
  21.         rear = ++rear % size;  
  22.         a[rear] = value; //尾指针满了就循环到0处,这句相当于下面注释内容        
  23.         nItems++;  
  24. /*      if(rear == size-1){ 
  25.             rear = -1; 
  26.         } 
  27.         a[++rear] = value; 
  28. */  
  29.     }  
  30.       
  31.     public long remove() {  
  32.         if(isEmpty()) {  
  33.             System.out.println("队列为空!");  
  34.             return 0;  
  35.         }  
  36.         nItems--;  
  37.         front = front % size;  
  38.         return a[front++];  
  39.     }  
  40.       
  41.     public void display() {  
  42.         if(isEmpty()) {  
  43.             System.out.println("队列为空!");  
  44.             return;  
  45.         }  
  46.         int item = front;  
  47.         for(int i = 0; i < nItems; i++) {  
  48.             System.out.print(a[item++ % size] + " ");  
  49.         }  
  50.         System.out.println("");  
  51.     }  
  52.       
  53.     public long peek() {  
  54.         if(isEmpty()) {  
  55.             System.out.println("队列为空!");  
  56.             return 0;  
  57.         }  
  58.         return a[front];  
  59.     }  
  60.       
  61.     public boolean isFull() {  
  62.         return (nItems == size);  
  63.     }  
  64.       
  65.     public boolean isEmpty() {  
  66.         return (nItems == 0);  
  67.     }  
  68.       
  69.     public int size() {  
  70.         return nItems;  
  71.     }  
  72. }  

 

    和栈一样,队列中插入数据项和删除数据项的时间复杂度均为O(1)。

    还有个优先级队列,优先级队列是比栈和队列更专用的数据结构。优先级队列与上面普通的队列相比,主要区别在于队列中的元素是有序的,关键字最小(或者最大)的数据项总在队头。数据项插入的时候会按照顺序插入到合适的位置以确保队列的顺序。优先级队列的内部实现可以用数组或者一种特别的树——堆来实现。堆可参考第8节内容。这里用数组实现优先级队列。

 

  1. public class PriorityQueue {  
  2.     private long[] a;  
  3.     private int size;  
  4.     private int nItems;//元素个数  
  5.       
  6.     public PriorityQueue(int maxSize) {  
  7.         size = maxSize;  
  8.         nItems = 0;  
  9.         a = new long[size];  
  10.     }  
  11.       
  12.     public void insert(long value) {  
  13.         if(isFull()){  
  14.             System.out.println("队列已满!");  
  15.             return;  
  16.         }  
  17.         int j;  
  18.         if(nItems == 0) { //空队列直接添加  
  19.             a[nItems++] = value;  
  20.         }  
  21.         else{//将数组中的数字依照下标按照从大到小排列  
  22.             for(j = nItems-1; j >= 0; j--) {  
  23.                 if(value > a[j]){  
  24.                     a[j+1] = a[j];  
  25.                 }  
  26.                 else {  
  27.                     break;  
  28.                 }  
  29.             }  
  30.             a[j+1] = value;  
  31.             nItems++;  
  32.         }  
  33.     }  
  34.       
  35.     public long remove() {  
  36.         if(isEmpty()){  
  37.             System.out.println("队列为空!");  
  38.             return 0;  
  39.         }  
  40.         return a[--nItems];  
  41.     }  
  42.       
  43.     public long peekMin() {  
  44.         return a[nItems-1];  
  45.     }  
  46.       
  47.     public boolean isFull() {  
  48.         return (nItems == size);  
  49.     }  
  50.       
  51.     public boolean isEmpty() {  
  52.         return (nItems == 0);  
  53.     }  
  54.       
  55.     public int size() {  
  56.         return nItems;  
  57.     }  
  58.   
  59.     public void display() {  
  60.         for(int i = nItems-1; i >= 0; i--) {  
  61.             System.out.print(a[i] + " ");  
  62.         }  
  63.         System.out.println(" ");  
  64.     }  
  65. }  

    这里实现的优先级队列中,插入操作需要O(N)的时间,而删除操作则需要O(1)的时间。在第8节里将介绍堆来改进插入操作的时间。

 

http://blog.csdn.net/eson_15/article/details/51126638

© 著作权归作者所有

共有 人打赏支持
乐在克里特
粉丝 15
博文 268
码字总数 394729
作品 0
杭州
程序员
数据结构课程主页-2016级

  新学期,再度起程!   翻转的数据结构课程再度迎来新的一批同学。   前两年,资源建设基本完备,课堂方案逐渐完善,同学们对新型的学习方式设计给予了肯定(参见2014级问卷调查和201...

sxhelijian
2017/08/30
0
0
零基础自学数据挖掘工程师必知的四大阶段 第三阶段是重点

  本文介绍的学习路线使用的是当下主流数据分析挖掘编程语言Python来掌握数据挖掘的实际工作能力与认识水平。按照 1)基础理论→2)编程能力→3)挖掘应用→4)大数据实践 的学习流程来设置...

蓝胖子讲大数据
2017/11/07
0
0
Java数据结构与算法(第四章栈和队列)

本章涉及的三种数据存储类型:栈、队列和优先级队列。 不同类型的结构 程序员的工具 数组是已经介绍过的数据存储结构,和其他结构(链表、树等等)一样,都适用于数据应用中作数据记录。 然而...

小风89
2015/10/24
250
0
《编程之美》-取队列中的最大值(读书分享)

题目:设计一种数据结构和算法,让取队列最大值的操作的事件复杂度降到最低。对队列操作后依然能够简便取出最大值。 对于栈来讲,Push和Pop均是在栈顶完成的,所以很容维护最大值,而且他的时...

吟啸_徐行
2013/03/15
0
4
数据结构和算法的选择

http://www.cnblogs.com/people/p/3291343.html 数据结构和算法的选择   本部分总结前面介绍的数据结构和算法,并讨论在不同的情况下如何进行选择。 通用数据结构:数组、链表、树、哈希表...

污湖洞主
2017/06/12
0
0
LeetCode题集整理- 栈、队列、堆

1、预备知识点 栈(Stack)和队列(Queue)是两种操作受限的线性表。 (线性表:线性表是一种线性结构,它是一个含有n≥0个结点的有限序列,同一个线性表中的数据元素数据类型相同并且满足“...

Blank_佐毅
2017/11/28
0
0
C 算法与数据结构 队列

队列 线性数据结构的一种。 特点 先进先出 入队的那一头叫队尾,出队的那一头叫队首。 队列里的指针域总是指向下一个节点。 下面是队列的链式存储结构C代码实现 #include <stdio.h>#include...

起什么name呢
2016/03/28
19
0
技能篇-数据结构和算法篇-基础算法与结构( 一 )

一 : 科普一分钟 什么是数据结构和算法,二者有和联系呢. 其实一种是数据存储的方式,一种是一种实现功能的手段. 我最近经常做饭,打个比方,就好比做菜一样,我们所用的食材就是数据结构,我们做同...

TianTianBaby223
2017/08/06
0
0
第一章 基础

什么是算法 ? 算法是编写一段计算机程序一般是实现一种已有的方法来解决某个问题. 在计算机领域里,我们用算法这个词来描述一种有限定,确定,有效的并适用计算机程序来实现解决的方法. 例 : 求...

Jonson
2016/04/21
27
0
面试常考的常用数据结构与算法【简】

数据结构与算法,这个部分的内容其实是十分的庞大,要想都覆盖到不太容易。在校学习阶段我们可能需要对每种结构,每种算法都学习,但是找工作笔试或者面试的时候,要在很短的时间内考察一个人...

anlve
05/01
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

Java基础——异常

声明:本栏目所使用的素材都是凯哥学堂VIP学员所写,学员有权匿名,对文章有最终解释权;凯哥学堂旨在促进VIP学员互相学习的基础上公开笔记。 异常处理: 可以挖很多个陷阱,但是不要都是一样...

凯哥学堂
21分钟前
0
0
180723-Quick-Task 动态脚本支持框架之结构设计篇

文章链接:https://liuyueyi.github.io/hexblog/2018/07/23/180723-Quick-Task-动态脚本支持框架之结构设计篇/ Quick-Task 动态脚本支持框架之结构设计篇 相关博文: 180702-QuickTask动态脚本...

小灰灰Blog
25分钟前
0
0
SBT 常用开发技巧

SBT 一直以来都是 Scala 开发者不可言说的痛,最主要的原因就是官方文档维护质量较差,没有经过系统的、循序渐进式的整理,导致初学者入门门槛较高。虽然也有其它构建工具可以选择(例如 Mill...

joymufeng
29分钟前
0
0
HBase in Practice - 性能、监控及问题解决

李钰(社区ID:Yu Li),阿里巴巴计算平台事业部高级技术专家,HBase开源社区PMC&committer。开源技术爱好者,主要关注分布式系统设计、大数据基础平台建设等领域。连续4年基于HBase/HDFS设计和...

中国HBase技术社区
30分钟前
1
0
ES18-JAVA API 批量操作

1.批量查询 Multi Get API public static void multiGet() {// 批量查询MultiGetResponse response = getClient().prepareMultiGet().add("my_person", "my_index", "1")// 查......

贾峰uk
35分钟前
0
0
SpringBoot2.0使用health

1,引入actuator <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-actuator</artifactId></dependency> 2,application.properties ......

暗中观察
42分钟前
0
0
阿里巴巴Java开发规约

###编程规约 命名风格 【强制】代码中的命名均不能以下划线或美元符号开始,也不能以下划线或美元符号结束 【强制】代码中的命名严禁使用拼音与英文混合的方式,更不允许直接使用中文的方式。...

简心
46分钟前
0
0
如何用TypeScript来创建一个简单的Web应用

转载地址 如何用TypeScript来创建一个简单的Web应用 安装TypeScript 获取TypeScript工具的方式: 通过npm(Node.js包管理器) npm install -g typescript 构建你的第一个TypeScript文件 创建...

durban
51分钟前
0
0
分享好友,朋友圈自定义分享链接无效

这个问题是微信6.5.6版本以后,修改了分享规则:分享的连接必须在公众号后台设定的js安全域名内

LM_Mike
今天
0
0
2018年7月23日课程

一、LVS-DR介绍 director分配请求到不同的real server。real server 处理请求后直接回应给用户,这样director负载均衡器仅处理客户机与服务器的一半连接。负载均衡器仅处理一半的连接,避免了...

人在艹木中
今天
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部