文档章节

Java数据结构与算法(第四章栈和队列)

小风89
 小风89
发布于 2015/10/24 01:11
字数 1977
阅读 258
收藏 10


本章涉及的三种数据存储类型:栈、队列和优先级队列。

不同类型的结构

程序员的工具

        数组是已经介绍过的数据存储结构,和其他结构(链表、树等等)一样,都适用于数据应用中作数据记录。

        然而,本章要讲解的是数据结构和算法更多的是作为程序员的工具来运用。它们组要作为构思算法的辅助工具,而不是完全的数据存储工具。这些数据结构的生命周期比那些数据库类型的结构要短的多。在程序操作执行期间它们才被创建,通常它们去执行某项特殊的任务,当完成之后,它们就被销毁。

受限访问

        在数组中,只要知道下标就可以访问数据项。或顺序访问等。

        而本章的数据结构中,访问时受限制的,即在特定时刻只有一个数据项可以被读取或者被删除(除非“作弊”);

        这些结构接口的设计增强了这种受限访问。访问其他数据项(理论上)是不允许的。

更加抽象

        栈、队列和优先级队列是比数组和其他数据存储结构更为抽象的结构。主要通过接口对栈、队列和优先级队列进行定义,这些接口表明通过他们可以完成的操作,而它们的主要实现机制对用户来说是不可见的。

        例如,栈的主要机制可以用数组来实现,但它也可以用链表了实现。优先级队列的内部实现可以用数组或一种特别的书———堆来实现。


        栈只允许访问一个数据项:即最后插入的数据项。移除这个数据项后才能访问倒数第二个插入的数据,以此类推。

栈的Java代码

public class Stack {
    private int maxSize;
    private long[] stackArray;
    private int top;
    public Stack(int s){
        maxSize = s;
        stackArray = new long[maxSize];
        top=-1;
    }
    public void push(long j){
        stackArray[++top] = j;
    }
    public long pop(){
        return stackArray[top--];
    }
    public long peek(){
        return stackArray[top];
    }
    public boolean isEmpty(){
        return (top==-1);
    }
    public boolean isFull(){
        return top==maxSize-1;
    }
}
public static void main(String[] args) {
    Stack theStack = new Stack(10);
    theStack.push(10);
    theStack.push(20);
    theStack.push(30);
    theStack.push(40);
    while(!theStack.isEmpty()){
        long value = theStack.pop();
        System.out.print(value);
        System.out.print("    ");
    }
}
//输出:
40	30	20	10

栈的效率

        栈操作所耗的时间不依赖与栈中数据项的个数,因此操作时间很短。栈不需要比较和移动操作。

队     列

        “队列”(queue)这个单词是英国人说的“排”(line)(一种等待服务的方式)。

        队列是一种数据结构,有点类似栈,只是在队列中第一个插入的数据项也会最先被移除(先进先出,FIFO),而在栈中,最后插入的数据项最先移除。

队列的Java代码

public class Queue {
    private int maxSize;
    private long[] queueArray;
    private int front;
    private int rear;
    private int nItems;
    
    public Queue(int s){
        maxSize = s;
        queueArray = new long[maxSize];
        front = 0;
        rear = -1;
        nItems = 0;
    }
    public void insert(long j){
        if(rear == maxSize-1)
            rear = -1;
        queueArray[++rear]=j;
        nItems++;
    }
    public long remove(){
        long temp = queueArray[front++];
        if(front==maxSize)
            front = 0;
        nItems--;
        return temp;
    }
    public long peekfront(){
        return queueArray[front];
    }
    public boolean isEmpty(){
        return nItems ==0;
    }
    public boolean isFull(){
        return nItems == maxSize;
    }
    public int size(){
        return nItems;
    }
}
public static void main(String[] args) {
    Queue theQueue = new Queue(5);
    
    theQueue.insert(10);
    theQueue.insert(20);
    theQueue.insert(30);
    theQueue.insert(40);
    
    theQueue.remove();
    theQueue.remove();
    theQueue.remove();
    
    theQueue.insert(50);
    theQueue.insert(60);
    theQueue.insert(70);
    theQueue.insert(80);
    theQueue.insert(90);
    theQueue.insert(100);
    
    while(!theQueue.isEmpty()){
        long n = theQueue.remove();
        System.out.print(n);
        System.out.print(" ");
    }
    System.out.println("");
}

队列的效率

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

双端队列

        双端队列,就是一个两端都是结尾的队列。队列的 每一端都可以插入数据项和移除数据项。这些方法可以叫做insertLeft()和insertRight(),以及removeLeft()和removeRight()。

        双端队列与栈或队列相比,是一种多用途的数据结构,在容器类库中有时会用双端队列来提供栈和队列的两种功能。但是,双端队列不像栈和队列那么常用。。。。。。。

优先级队列

        优先级队列是比栈和队列更专用的数据结构。但它在很多的情况下都很有用。像普通队列一样,优先级队列有一个对头和一个队尾,并且也是从头移除数据项。不过在优先级队列中,数据项按关键字的值有序,这样关键字最小的数据项(或者在某些实现中关键字最大的数据项)总是在队头。数据项插入的时候会按照顺序插入到合适的位置以确保队列的顺序。

优先级队列Java代码

public class PriorityQueue {
    private int maxSize;
    private long[] queueArray;
    private int nItems;
    
    public PriorityQueue(int s){
        maxSize = s;
        queueArray = new long[maxSize];
        nItems = 0;
    }
    
    public void inser(long item) {
        int i;
        if(nItems==0)
            queueArray[nItems++] = item;
        else
        {
            for (i = nItems-1; i>=0; i--) {
                if(item>queueArray[i])
                    queueArray[i+1] = queueArray[i];
                else
                    break;
            }
            queueArray[i+1] = item;
            nItems++;
        }
    }
    
    public long remove(){
        return queueArray[--nItems];
    }
    
    public long meekMin(){
        return queueArray[nItems-1];
    }
    
    public boolean isEmpty(){
        return nItems
            ==0;
    }

    public boolean isFull(){
        return nItems==maxSize;
    }
}
public static void main(String[] args) {
    PriorityQueue queue = new PriorityQueue(5);
    
    queue.inser(30);
    queue.inser(50);
    queue.inser(10);
    queue.inser(40);
    queue.inser(20);
    
    while(!queue.isEmpty()){
        long item = queue.remove();
        System.out.print(item);
        System.out.print(" ");
    }
    System.out.println("");
}
//输出:10 20 30 40 50

    在main()方法中随机插入5个数据项,随后移除并显示它们。最小的数据项总是最先移除,所以输出是:

10 20 30 40 50

优先级队列的效率

        在本章实现的优先级队列中,插入操作需要O(N)的时间,而删除则需要O(1)的时间。

解析算术表达式

后缀表达法

        日常算术表达式是将操作符(operator)(+,-,*,/)放在两个操作数(operands)(数字或代表数字的字母)之间的。因为操作符写在操作数的中间,所以把这表写法成为中缀表达法。

        在后缀表达式中【也称为波兰逆序表达式(Reverse Polish Natation),或者RPN】,它是由以为波兰数学家发明的,操作符跟在两个操作数的后面。这样,A+B就成为AB+,A/B成为AB/。更复杂的如下表:

中缀表达式 后缀表达式
A+B-C AB+C-
A*B/C AB*C/
A+B*C ABC*+
A*B+C AB*C+
A*(B+C) ABC+*
A*B+C*D AB*CD*+
(A+B)*(C-D) AB+CD-*
((A+B)*C)-D AB+C*D-
A+B(C-D/(E+F)) ABCDEF+/-*+

后缀表达式求职。。。。。

小    结

  • 栈、队列和优先级队列是经常用于简化某些程序操作的数据结构。

  • 在这些数据结构中,只有一个数据项可以被访问。

  • 栈允许访问最后一个插入的数据项。

  • 栈中重要的操作是在栈顶插入(压入)一个数据项,以及从栈顶移除(弹出)一个数据项。

  • 队列只允许访问第一个插入的数据项。

  • 队列的重要操作是在队尾插入数据项和在队头移除数据项。

  • 队列可以实现为循环队列,它基于数组,数组下标可以从数组末端回绕到数组的开始位置。

  • 优先级队列允许访问最小(或者有时是最大)的数据项。

  • 优先级队列的重要操作是有序地插入新数据项和移除关键字最小的数据项。

  • 这些数据结构可以用数组实现,也可以用其他机制(例如链表)来实现。

  • 普通算术表达式是用中缀表达法表示的,这种命名的原因是操作符写在两个操作的中间。

  • 在后缀表达法中,操作符跟在两个操作数的后面。

  • 算术表达式求值通常都是先转换成后缀表达式,然后再求后缀表达式的值。

  • 在中缀表达式转换到后缀表达式以及求后缀表达式的值过程里,栈都是很有用的工具。

© 著作权归作者所有

共有 人打赏支持
小风89
粉丝 19
博文 93
码字总数 94191
作品 0
杭州
高级程序员
私信 提问
Android--面试中遇到的问题总结(三)

《Android 开发工程师面试指南 LearningNotes 》,作者是陶程,由梁观全贡献部分。大家可以去知乎关注这两位用心的少年。这份指南包含了大部分Android开发的基础、进阶知识,不仅可以帮助准备...

sealin
2017/02/22
0
0
可视化的数据结构和算法

还记得之前发布过的那个关于可视化排序的文章吗?在网上又看到了一个旧金山大学David Galles做的各种可视化的数据结构和基本算法的主页,网址在这里,大家可以看看。我把这个页面的目录列在下...

戴威
2011/05/12
962
5
JAVA区块链项目实战视频课程

课程介绍 全国首套,基于java的区块链实战教程。目的是让更多的java编程者了解区块链,掌握区块链开发。 1、区块链理论:以node.js例子区块链原理有深刻理解; 2、区块链java实战:深刻理解区...

小红牛
2018/09/14
0
0
BAT等大厂Android面试书单和知识点清单

java是Android开发的基础,在BAT的初面中,会涉及到比较多的java基础知识,所以比较重要,下面我介绍的书籍内容是由浅到深。 1.Thinking in java:这本书被称为Java的三大圣经之一,虽然书比...

android自学
2018/07/25
0
0
可视化的数据结构和算法

还记得之前发布过的那个关于可视化排序的文章吗?在网上又看到了一个旧金山大学David Galles做的各种可视化的数据结构和基本算法的主页,网址在这里,大家可以看看。我把这个页面的目录列在下...

戴威
2011/05/12
16
0

没有更多内容

加载失败,请刷新页面

加载更多

java框架学习日志-13(Mybatis基本概念和简单的例子)

在mybatis初次学习Mybatis的时候,遇到了很多问题,虽然阿里云的视频有教学,但是视频教学所使用的软件和我自己使用的软件不用,我自己用的数据库是oracle数据库,开发环境是idea。而且视频中...

白话
今天
4
0
Java基础:String、StringBuffer和StringBuilder的区别

1 String String:字符串常量,字符串长度不可变。Java中String是immutable(不可变)的。 String类的包含如下定义: /** The value is used for character storage. */private final cha...

watermelon11
今天
2
0
mogodb服务

部署MongoDB 官网: https://www.mongodb.com/download-center/community 创建mongo数据目录 mkdir /data/mongodb 二进制部署 wget -c https://fastdl.mongodb.org/linux/mongodb-linux-x8......

以谁为师
昨天
5
0
大神教你Debian GNU/Linux 9.7 “Stretch” Live和安装镜像开放下载

Debian项目团队于昨天发布了Debian GNU/Linux 9 "Stretch" 的第7个维护版本更新,重点修复了APT软件管理器中存在的安全漏洞。在敦促每位用户尽快升级系统的同时,Debian团队还发布了Debian ...

linux-tao
昨天
4
0
PHP 相关配置

1. php-fpm的pool 编辑php-fpm配置文件php-fpm.con vim /usr/local/php/etc/php-fpm.conf //在[global]部分增加以下内容 include = etc/php-fpm.d/*.conf # 相当与Nginx的虚拟主机文件 “vho......

Yue_Chen
昨天
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部