专栏首页Kevin-ZhangCG数据结构之栈和队列

数据结构之栈和队列

 栈或者队列是经典的数据结构,虽然平时都在用,但是都是别人封装好的集合,我们不用手写了,但是这些内功,作为开发人员来说是必须要掌握的。

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

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

public class ArrayStack {
    private long[] a;
    //栈数组大小
    private int size;
    //栈顶
    private int top;

    //初始化栈
    public ArrayStack(int maxSize) {
        this.size = maxSize;
        a = new long[size];
        //表示空栈
        top = -1;
    }

    //入栈
    public void push(int value) {
        if (isFull()) {
            System.out.println("Stack is Full!");
            return;
        }
        a[++top] = value;
    }

    //出栈,返回栈顶元素并删除
    public long pop() {
        if (isEmpty()) {
            System.out.println("Stack is Empty!");
            return 0;
        }
        return a[top--];
    }

    //获取并返回栈顶元素
    public long peak() {
        if (isEmpty()) {
            System.out.println("Stack is Empty!");
            return 0;
        }
        return a[top];
    }

    public boolean isFull() {
        return top == size - 1;
    }

    public boolean isEmpty() {
        return top == -1;
    }

    //遍历栈元素
    public void display() {
        if (isEmpty()) {
            System.out.println("Stack is Empty!");
            return;
        }
        for (int i = top; i >= 0; i--) {
            System.out.print(a[i] + " ");
        }
        System.out.println();
    }
}

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

队列

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

public class RoundQueue {
    private long[] a;
    //数组大小
    private int size;
    //队头
    private int front;
    //队尾
    private int rear;
    //实际存储元素个数
    private int nItems;

    //初始化队列
    public RoundQueue(int maxSize) {
        this.size = maxSize;
        a = new long[size];
        front = 0;
        rear = -1;
        nItems = 0;
    }

    //插入数据
    public void insert(int value) {
        if (isFull()) {
            System.out.println("Queue is Full!");
            return;
        }
        //尾指针满了就循环到0处
        rear = ++rear % size;
        a[rear] = value;
        nItems++;
        /*if (rear == size - 1) {
            rear = -1;
        }
        a[++rear] = value;*/
    }

    //删除数据
    public long remove() {
        if (isEmpty()) {
            System.out.println("Queue is Empty!");
            return 0;
        }
        nItems--;
        front = front % size;
        return a[front++];
    }

    //返回队头数据
    public long peak() {
        if (isEmpty()) {
            System.out.println("Queue is Empty!");
            return 0;
        }
        return a[front];
    }

    public boolean isFull() {
        return nItems == size;
    }

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

    public void display() {
        if (isEmpty()) {
            System.out.println("Queue is Empty!");
            return;
        }
        int item = front;
        for (int i = 0; i < nItems; i++) {
            System.out.print(a[item++ % size] + " ");
        }
        System.out.println();

    }
}

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

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

public class PriorityQueue {
    private long[] a;
    //数组大小
    private int size;
    //实际存储元素个数
    private int nItems;

    public PriorityQueue(int maxSize) {
        this.size = maxSize;
        a = new long[size];
        nItems = 0;
    }

    public void insert(int value) {
        if (isFull()) {
            System.out.println("Queue is Full!");
            return;
        }
        int j;
        //空队列直接添加
        if (nItems == 0) {
            a[nItems++] = value;
        } else {
            //将数组元素从小到大排列
            for (j = nItems - 1; j >= 0; j--) {
                if (value > a[j]) {
                    a[j + 1] = a[j];
                } else {
                    break;
                }
            }
            a[j + 1] = value;
            nItems++;
        }

    }

    public long remove() {
        if (isEmpty()) {
            System.out.println("Queue is Empty!");
            return 0;
        }
        return a[--nItems];
    }

    public long peekMin() {
        return a[nItems - 1];
    }

    public boolean isFull() {
        return nItems == size;
    }

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

    public int size() {
        return nItems;
    }

    public void display() {
        for (int i = nItems - 1; i >= 0; i--) {
            System.out.print(a[i] + " ");
        }
        System.out.println();
    }
}

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

原文参考【Java知音网

本文参与 腾讯云自媒体分享计划 ,欢迎热爱写作的你一起参与!
本文分享自作者个人站点/博客:http://www.cnblogs.com/Kevin-ZhangCG/复制
如有侵权,请联系 cloudcommunity@tencent.com 删除。
登录 后参与评论
0 条评论

相关文章

  • 数据结构之栈和队列

     我们知道,在数组中,若知道数据项的下标,便可立即访问该数据项,或者通过顺序搜索数据项,访问到数组中的各个数据项。但是栈和队列不同,它们的访问是受限制的,即在...

    xiangzhihong
  • 数据结构 - 栈和队列

    栈(stack) 是一个特殊的线性表,是限定仅在一端(通常是表尾)进行插入和删除操作的线性表。表尾的一端有其特殊含义,称为 栈顶(top) ,相应地,表头称为 ...

    忆想不到的晖
  • 数据结构-栈和队列

    栈是一种特殊的线性表。其特殊性在于限定插入和删除数据元素的操作只能在线性表的一端进行。如下所示:

    黄规速
  • 数据结构-栈和队列

    我们把类似于弹夹那种先进后出的数据结构称为栈,栈是限定仅在表尾进行插入和删除操作的线性表,我们把允许插入和删除的一端称为栈顶,另一端称为栈底,不含任何数据元素的...

    张俊红
  • 数据结构|数组,栈和队列[1]

    数组的大小固定,如果存储数量过多,需要重建新数组;同时存储的数据类型单一,每个元素占用内存大小相同;添加,删除,移动操作比较慢,因为需要改变受影响的元素

    rare0502
  • 栈 数据结构_单调栈和单调队列

    笔者在做leetcode的题(下一个出现的最大数字)时,接触到了单调栈这一种数据结构,经过研究之后,发现单调栈在解决某些问题时出奇的好用,下面是对单调栈的性质和...

    全栈程序员站长
  • JavaScript 数据结构:栈和队列

    上周小编已经介绍了什么是数据结构,没看过的同学,可以点击《JavaScript 数据结构:什么是数据结构》,今天小编会和大家一起学习栈和队列。

    前端达人
  • 数据结构基础-栈和队列

    栈是一个有序线性表,只能在表的一端(成为栈顶,top)执行插入和删除操作。最后插入的元素将第一个被删除。所以栈也称为后进先出(Last In First Out...

    1025645
  • 数据结构(3) - 栈和队列

    惊羽-布壳儿
  • 数据结构之栈与队列(优先队列/堆)

    栈与队列是两种重要的特殊线性表,从结构上讲,两者都是线性表,但从操作上讲,两者支持的基本操作却只是线性表操作的子集,是操作受限制的线性表。栈与队列两者最大的区别...

    我是东东东
  • 数据结构之链表、栈和队列 java代码实现

    定义抽象节点类Node: 1 package cn.wzbrilliant.datastructure; 2 3 /** 4 * 节点 5 * ...

    欠扁的小篮子
  • [第 3 期]JavaScript数据结构之数组栈队列

    桃翁
  • 数据结构之队列and栈总结分析

    数据结构中队列和栈也是常见的两个数据结构,队列和栈在实际使用场景上也是相辅相成的,下面简单总结一下,如有不对之处,多多指点交流,谢谢。

    小小许
  • 疯狂java笔记之栈和队列栈队列双端队列

    栈的英文单词是Stack,它代表一种特殊的线性表,这种线性表只能在固定一端(通常认为是线性表的尾端)进行插入,删除操作。

    HelloJack
  • 搞定数据结构-栈和队列

    如下,使用栈结构操作. “网”这个错别字在栈顶,“网”改成”望”只需要将“网”从栈顶移除重新写入”望”.

    用户3045442
  • 期末复习之数据结构 第3章 栈和队列

    五:写出下列程序段的输出结果(栈的元素类型SElem Type为char)。 1.void main( ){ Stack S; Char x,y...

    henu_Newxc03
  • 数据结构—栈/队列

    仔细一想 似乎自己已经有半年已经没有手写栈/队列了 STL里面的栈/队列好用是好用但是速度令人堪忧啊。 于是乎今天自己手写了一份栈&&队列, 以后就用这种格式了...

    attack
  • 数据结构:栈&队列

    栈的顺序存储称为顺序栈,它是利用一组地址连续的存储单元存放自栈底到栈顶的数据元素,同时附设一个指针(top)指示当前栈顶的位置。

    HLee
  • 数据结构 栈&队列

    2-4 依次在初始为空的队列中插入元素a,b,c,d以后,紧接着做了两次删除操作,此时的队头元素是( ) 删除,移动头指针; 增加,移动尾指针; 删除a,b ,...

    Kindear

扫码关注腾讯云开发者

领取腾讯云代金券