同步操作将从 turnon/blog 强制同步,此操作会覆盖自 Fork 仓库以来所做的任何修改,且无法恢复!!!
确定后同步将在后台操作,完成时将刷新页面,请耐心等待。
title: 栈和队列
date: 2014-01-25 16:46:13
categories:
- 数据结构和算法
- 线性表
tags:
- 数据结构
- 线性表
- 栈
- 队列
permalink: /pages/dd3588/
队列和栈都是操作受限的线性表:前者先进先出,后者先进后出。
在 LIFO(后进先出) 数据结构中,将首先处理添加到队列中的最新元素。
栈是一个 LIFO(后进先出) 数据结构。栈是一种“操作受限”的线性表,只允许在一端插入和删除数据。通常,插入操作在栈中被称作入栈 push 。与队列类似,总是在堆栈的末尾添加一个新元素。但是,删除操作,退栈 pop ,将始终删除队列中相对于它的最后一个元素。
当某个数据集合只涉及在一端插入和删除数据,并且满足后进先出、先进后出的特性,我们就应该首选“栈”这种数据结构。
从栈的定义可以看出,栈只支持两个基本操作:入栈 push()
和 出栈 pop()
,也就是在栈顶插入一个数据和从栈顶删除一个数据。在入栈和出栈过程中,只需要一两个临时变量存储空间,所以空间复杂度是 O(1)
。
栈既可以用数组来实现,也可以用链表来实现。用数组实现的栈,我们叫作顺序栈,用链表实现的栈,我们叫作链式栈。
相比数组和链表,栈只是对操作进行了限制,似乎并没有任何优势。为什么不直接使用数组或者链表?为什么还要用这个“操作受限”的“栈”呢?
特定的数据结构是对特定场景的抽象,而且,数组或链表暴露了太多的操作接口,操作上的确灵活自由,但使用时就比较不可控,自然也就更容易出错。
(1)函数调用栈
(2)表达式求值
(3)表达式匹配
可以借助栈来检查表达式中的括号是否匹配
在 FIFO 数据结构中,将首先处理添加到队列中的第一个元素。
队列是典型的 FIFO 数据结构。插入(insert)操作也称作入队(enqueue),新元素始终被添加在队列的末尾。 删除(delete)操作也被称为出队(dequeue)。 你只能移除第一个元素。
队列:先进先出的线性表。
队列是一种“操作受限”的线性表,只允许在一端插入数据,在另一端删除数据。
队列的最基本操作:入队 enqueue()
,放一个数据到队列尾部;出队 dequeue()
,从队列头部取一个元素。
队列可以用数组来实现,也可以用链表来实现。用数组实现的队列叫作顺序队列,用链表实现的队列叫作链式队列。
队满的判断条件是 tail == n
,队空的判断条件是 head == tail
。
循环队列是一种较为特殊的队列。
循环队列的要点是确定好 队空和队满的判定条件。
在用数组实现的非循环队列中,队满的判断条件是 (tail+1) % n == head
,队空的判断条件是 head == tail
。
为什么需要队列和为什么需要栈,是同样的道理,参考 为什么需要栈
(1)阻塞队列
阻塞队列其实就是在队列基础上增加了阻塞操作。简单来说,就是:
(2)并发队列
线程安全的队列我们叫作并发队列。最简单直接的实现方式是直接在 enqueue()、dequeue() 方法上加锁,但是锁粒度大并发度会比较低,同一时刻仅允许一个存或者取操作。实际上,基于数组的循环队列,利用 CAS 原子操作,可以实现非常高效的并发队列。这也是循环队列比链式队列应用更加广泛的原因。
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。