美文网首页大数据
栈与队列简介

栈与队列简介

作者: 热衷技术的Java程序员 | 来源:发表于2020-09-01 17:25 被阅读0次

栈与队列和数组、链表、树这几种数据结构不太一样。栈与队列主要是做为程序员的工具来使用,它们主要做为构思算法的辅助工具,而不是完全的数据存储工具。

它们的生命周期比数组那些要短得多,在程序执行期间它们才会被创建,任务执行完就会被销毁。

一 栈

栈是一种只能在一端进行插入和删除数据的数据结构,这一端被称为栈顶(top)。其特点简单来讲就是先进后出。栈的主要机制可以用数组来实现,当然也可以用链表来实现。

用数组实现栈,并完成常用操作——出栈、入栈、查看元素(只能查看栈顶元素)、判断栈是否为空等操作。


publicclassStackTest{



privatelong[]arr;

// 栈顶

    private int top;

    public StackTest(){

        arr = new long[10];

        top = -1;

    }

    public StackTest(int maxsize){

        arr = new long[maxsize];

        top = -1;

    }

    /**

* 添加数据     * @param value     */

    public void push(int value){

        arr[++top] = value;

    }

    /**

* 移除数据     * @return     */

    public long pop() {

        return arr[top--];

    }

    /**

* 查看数据     * @return     */

    public long peek(){

        return arr[top];

    }

    public boolean isEmpty(){

        return top == -1;

    }

    /***

* 判断是否满了     * @return     */

    public boolean isFull(){

        return top == arr.length-1;

    }

}

栈的所有操作复杂度都为O(1),栈的操作不依赖栈中元素大小,栈不需要移动和比较操作。

二 队列

队列的特点是先进先出。队列也是用数组来实现。

用数组实现队列,并完成常用操作——出队、入队、查看元素、判断队列是否为空等操作。


publicclassQueueTest{

privatelong[]arr;

// 有效数据的大小

    private int elements;

    // 队头

    private int front;

    // 队尾

    private int end;

    public QueueTest(){

        arr = new long[10];

        elements = 0;

        front = 0;

        end = -1;

    }

    public QueueTest(int maxsize){

        arr = new long[maxsize];

        elements = 0;

        front = 0;

        end = -1;

    }

    /**

* 插入数据     * @param value     */

    public void insert(long value){

        arr[++end] = value;

        elements++;

    }

    /**

* 删除数据     * @return     */

    public long remove(){

        elements--;

        return arr[front++];

    }

    /**

* 查看数据,从对头查看     * @return     */

    public long peek(){

        return arr[front];

    }

    /**

* 判断是否为空     * @return     */

    public boolean isEmpty(){

        return elements == 0;

    }

    public boolean isFull(){

        return elements == arr.length;

    }

}

队列的插入、删除等操作的复杂度都为O(1)。

三 优先级队列

优先级队列和普通队列一样,也是一个队头,一个队尾,从队头移除元素,优先级队列中,数据项是有序的,这样插入数据的时候就会根据某种规则去比较,然后插入到队列合适的位置。因此,优先级队列插入的复杂度为O(N),删除和查看元素的复杂度为O(1)。

用数组实现优先级队列,并完成常用操作——出队、入队、查看元素、判断队列是否为空等操作。

publicclassFirstQueueTest{

privatelong[]arr;

// 有效数据的大小

    private int elements;

    // 队头

    private int front;

    // 队尾

    private int end;

    public FirstQueueTest(){

        arr = new long[10];

        elements = 0;

        front = 0;

        end = -1;

    }

    public FirstQueueTest(int maxsize){

        arr = new long[maxsize];

        elements = 0;

        front = 0;

        end = -1;

    }

    /**

* 插入数据     * @param value     */

    public void inser(long value){

        if(elements == 0){

            arr[++end] = value;

            elements++;

        }else{

            // 按某种规则进行比较,这里使用value的大小比较,按从小到大排序

            for(int i = elements-1;i>=0;i--){

                if(value<arr[i]){

                    arr[i+1] = arr[i];

                    arr[i] = value;

                }else{

                    arr[i+1] = value;

                    break;

                }

            }

            elements++;

            end++;

        }

    }

    /**

* 删除数据     * @return     */

    public long remove(){

        elements--;

        return arr[front++];

    }

    /**

* 查看数据,从对头查看     * @return     */

    public long peek(){

        return arr[front];

    }

    /**

* 判断是否为空     * @return     */

    public boolean isEmpty(){

        return elements == 0;

    }

    public boolean isFull(){

        return elements == arr.length;

    }

}

四 总结

栈的特点是先进后出,栈只能查看栈顶的一个元素

队列的特点是先进先出,只能查看队头的一个元素

优先级队列插入一条元素,平均需要移动2/N个元素,因此插入的复杂度为O(N)

栈和队列,可以用数组实现,也可以用其他数据结构实现

栈和队列是为了完成某些工作,手动构造的数据结构

相关文章

  • 栈与队列简介

    栈与队列和数组、链表、树这几种数据结构不太一样。栈与队列主要是做为程序员的工具来使用,它们主要做为构思算法的辅助工...

  • Swift 队列&栈 相关操作

    栈 LIFO(后进先出) 队列 FIFO(先进先出) 队列与栈相互的实现 栈 - 队列实现 队列 - 栈实现 相关...

  • 数据结构与算法之队列(五)

    目录 队列简介队列的接口设计用栈实现队列双端队列实现循环队列实现循环双端队列 一 简介 队列是一种特殊的线性表,只...

  • 队列

    队列简介 数据结构中的队列与日常生活中排队是一致的,最早进入队列的元素最早离开,与栈(先进后出)相反。在队列中允许...

  • 数据结构学习 | 队列和栈

    栈 后进先出 栈顶允许插入(压栈)、删除(弹栈) 应用:数制转换数制转换与栈 队列 先进先出 队列头部允许删除,队...

  • Algorithm小白入门 -- 队列和栈

    队列和栈队列实现栈、栈实现队列单调栈单调队列运用栈去重 1. 队列实现栈、栈实现队列 队列是一种先进先出的数据结构...

  • 常见数据结构

    栈、队列、数组、链表、树、哈希表 栈 与 队列 首先我们需要了解【栈】与【列队】的区别,它们的最大区别就是数据进出...

  • 栈和队列

    用栈定义队列(出入栈) 用队列定义栈(数据队列和辅助队列)

  • LeetCode刷题笔记(三)栈与队列

    三. 栈与队列 python中的栈直接用list实现,队列用deque,需要导入外部包。 155. 最小栈 题目:...

  • 实 验 四 栈和队列

    一、实验目的与要求:## 1、理解栈和队列抽象数据类型。 2、掌握栈和队列的存储结构和操作实现。 3、理解栈和队列...

网友评论

    本文标题:栈与队列简介

    本文链接:https://www.haomeiwen.com/subject/degvsktx.html