数据结构与算法中的栈，如何实现长尾词的存储与检索？

本文共计1239个文字，预计阅读时间需要5分钟。

栈是一种特殊的线性表，它只允许在固定的一端进行插入和删除操作。对数据进行的插入和删除操作的一端称为栈顶，另一端称为栈底。对栈的操作分为两种：入栈和出栈。

一、什么是栈

栈是一种特殊的线性表，它只允许在固定的一端进行插入和删除的操作。

对数据进行插入和删除的一端叫做栈顶，另一端是栈底。

对栈的两项操作分别叫做入栈、出栈。

入栈就是对栈进行插入操作，除此之外，入栈也叫做进栈、压栈。

出栈就是对栈进行删除的操作。

不管是入栈的数据还是出栈的数据都在栈顶。

栈的元素数据遵循后进先出（Last In First Out）的原则，即后进入的数据先出来。

以下是栈以及栈的操作的一张示意图：

如果一组数据的入栈顺序为1234

那么它的出栈顺序可能为

4321

1234

2134

······

二、缓存利用率

栈可以用顺序表实现，也可以用链表来实现。

但是，顺序表的缓存利用率更高，链表的缓存利用率低于顺序表。

结构上来说顺序表物理上是连续的，链表是一个一个的节点。

众所周知计算机的存储体系是分级的，CPU的速度远远大于RAM的速度，所以在CPU和RAM之间会有三级的缓存和寄存器。

如果现在分别对顺序表和链表进行遍历访问或是修改数据，这时是CPU对这些数据进行访问，也就是说CPU要访问内存。

CPU要想对内存进行访问，会先去访问缓存，如果数据在缓存中就访问了数据。如果数据不在缓存中，那么内存中的数据会先进入缓存再供CPU访问。由于缓存大小有限，当数据量很大时，大概率不会一下将内存中的数据放入缓存。