数据结构中的栈，为何能处理长尾词？

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

栈的定义和特点：栈是一个特殊的线性表，限定仅在表的一端进行插入和删除操作。这种线性表又称为后进先出（LIFO）结构，仅在表尾进行插入和删除操作。

栈的定义和特点

栈是一个特殊的线性表，是限定仅在一端（通常是表尾）进行插入和删除操作的线性表。

又称为后进先出的线性表，简称LIFO结构。

栈是仅在表尾进行插入、删除操作的线性表。

表尾称为栈顶top，表头称为栈底base

插入元素到栈顶（即表尾）的操作，称为入栈。

从栈顶（即表尾）删除最后一个元素的操作，称为出栈

“入”=压入push（x) "出"=弹出pop（y)

重要结论

栈的抽象数据类型的类型定义

ADT Stack {

数据对象：D＝{ ai | ai ∈ElemSet, i=1,2,...,n, n≥0 } 数据关系：R1＝{ <ai-1, ai >| ai-1, ai∈D, i=2,...,n } 约定an 端为栈顶，a1 端为栈底。

基本操作：

InitStack(&S) 操作结果：构造一个空栈S

DestroyStack(&S) 初始条件：栈 S 已存在。 操作结果：栈 S 被销毁。

ClearStack(&S) 初始条件：栈 S 已存在。 操作结果：将 S 清为空栈。

StackEmpty(s) 初始条件：栈 S 已存在。 操作结果：若栈 S 为空栈，返回 TRUE，否则返回 FALSE。