不会飞的章鱼

熟能生巧,勤能补拙;念念不忘,必有回响。

算法训练营-栈和队列的实现与特性

想象成一个先入后出的容器:

队列

像排队,先来先出:

栈和队列关键点

  • 栈(Stack):先入后出;添加、删除操作的时间复杂度都为O(1),查询为O(n)
  • 队列(Queue):先入后出;添加、删除操作的时间复杂度都为O(1),查询为O(n)

双端队列(Double End Queue)

首端和尾端都可以添加、删除元素:

  • 简单理解:两端都可以进出的队列;
  • 插入和删除都是O(1)的操作。

Stack、Queue、Deque的工程实现

优先队列(Priority Queue)

  • 插入操作:O(1)
  • 取出操作:O(logN)-按照元素的优先级取出
  • 底层具体实现的数据结构较为多样和复杂:heap、bst、treap

Java源码分析

Stack-source Java

时间复杂度

作业

  • 1,用新的api-addfirst,addlast去改写
  • 2,分析Queue,Priority Queue源码

参考链接

Stack Java 12 doc

1
2
3
4
5
6
7
The Stack class represents a last-in-first-out (LIFO) stack of objects. It extends class Vector with five operations that allow a vector to be treated as a stack. The usual push and pop operations are provided, as well as a method to peek at the top item on the stack, a method to test for whether the stack is empty, and a method to search the stack for an item and discover how far it is from the top.
When a stack is first created, it contains no items.

A more complete and consistent set of LIFO stack operations is provided by the Deque interface and its implementations, which should be used in preference to this class. For example:


Deque<Integer> stack = new ArrayDeque<Integer>();

Priority Queue Java 12 doc

------ 本文结束------
如果本篇文章对你有帮助,可以给作者加个鸡腿~(*^__^*),感谢鼓励与支持!