C4-栈和队列

2017-08-08

栈和队列

1 概念

栈和队列的基本性质

栈：先进后出
队列：先进先出
栈和队列在实现结构上可以有数组和链表两种形式
- 数组结构容易实现
- 链表结构复杂，因为有很多指针操作

栈结构的基本操作

pop操作
top或peek操作
push操作
size操作

队列基本操作

与栈不同的是，push操作为在队头加入元素，而pop操作是从队列尾部弹出一个元素。

其他

栈和队列的基本操作，都是时间复杂度为O(1)的。
双端队列的首尾都可以亚茹和弹出元素
优先级队列根绝元素的优先级值，决定元素的弹出顺序
优先级队列的结构为堆结构，并不是线性结构

2 相关算法

DFS

一棵二叉树的深度优先遍历，可以用栈实现，遍历的顺序其实就是节点入栈的顺序

BFS

一棵二叉树的广度优先遍历，可以用队列实现，遍历的顺序其实就是节点的入队列顺序

递归

平时使用的递归函数实际上用到了系统提供的函数栈
递归函数的处理过程，可以看做是函数进栈出栈的过程
所有用递归函数可以做的过程都一定可以用非递归的方式实现

3 例题

例题1

例题2

解法

例题3

解法

例题4

解法

例题5

解法

方法1：

例题6

解法

缺失模块。
1、请确保node版本大于6.2
2、在博客根目录（注意不是yilia根目录）执行以下命令：
npm i hexo-generator-json-content --save

3、在根目录_config.yml里添加配置：

  jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

SeawayLee.<br> Male | 1993 | BeiJing <br> NCUT | CS | Postgraduate(2015-2018) <br> <br> Dream To Be A Top Programmer.<br> Just Shut Up And Show Me Your Code.<br>