从简单的线性数据结构开始:栈与队列

在计算机领域离不开算法和数据结构,而在数据结构中尤为重要与基础的便是两个线性数据结构:队列,本文将简单的介绍栈(Stack)队列(Queue)的实现。

栈与队列

  1. 栈 (Stack)是一种后进先出(last in first off,LIFO)的数据结构
  2. 队列(Queue)则是一种先进先出 (fisrt in first out,FIFO)的结构

动画如下:

队列

栈 (Stack)

栈是一种线性结构,与数组相比,栈对应的操作是数组的子集。

它只能从一端添加元素,也只能从一端取出元素(这一端称之为栈顶)。

Stack这种数据结构用途很广泛,在计算机的使用中,大量的运用了栈,比如编译器中的词法分析器、Java虚拟机、软件中的撤销操作(Undo)、浏览器中的回退操作,编译器中的函数调用实现等等。

栈的实现

接口

说明

复杂度

void push(E e)

向栈中加入元素

O(1) 均摊

E pop()

弹出栈顶元素

O(1) 均摊

E peek()

查看栈顶元素

O(1)

int getSize()

获取栈中元素个数

O(1)

boolean isEmpty()

判断栈是否为空

O(1)

说明:push和pop操作在最后面进行,有可能触发resize,但均摊来算是O(1)的。 如果你想了解更多时间复杂度的分析,欢迎关注笔者后续要更新的文章:O(n)说明的是什么问题?

栈的实现可以通过 数组 或者 链表 实现,在这里我们使用 数组来实现上述接口。

在栈的设计中,用户只关注栈顶元素存取和栈长度,因此设计代码如下:

读者可以使用 这种数据结构去解决LeetCode上的第20号问题:有效的括号,也可以查看 每天一算:Valid Parentheses

队列 Queue

队列也是一种线性数据结构,与数组相比,队列对应的操作是数组的子集。

只能从一端 (队尾) 添加元素,只能从另一端 (队首) 取出元素。

队列的应用可以在播放器上的播放列表,数据流对象,异步的数据传输结构(文件IO,管道通讯,套接字等)上体现,当然最直观的的就是排队了。

队列的实现

接口

说明

复杂度

void enqueue(E e)

入队

O(1) 均摊

E dequeue()

出队

O(n)

E getFront()

获取队首元素

O(1)

int getSize()

获取队列元素个数

O(1)

boolean isEmpty()

判断队列是否为空

O(1)

入队是从队尾开始,有可能触发resize,因此均摊下来是O(1)。出队是在队首,数组实现每次都要挪动所有元素,O(n)。

原文发布于微信公众号 - 五分钟学算法(blgczzz)

原文发表时间:2018-12-03

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券