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

本文共计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。

StackLength(S) 初始条件：栈 S 已存在。 操作结果：返回 S 的元素个数，即栈的长度。

GetTop(S, &e) 初始条件：栈 S 已存在且非空。操作结果：用 e 返回 S 的栈顶元素。

Push(&S, e) 初始条件：栈 S 已存在。 操作结果：插入元素 e 为新的栈顶元素。

Pop(&S, &e) 初始条件：栈 S 已存在且非空。 操作结果：删除栈顶元素，并用 e 返回其值。

StackTravers(S, visit()) 初始条件：栈 S 已存在且非空。 操作结果：从栈底开始遍历栈。 } ADT Stack

栈的表示和实现

由于栈本身就是线性表，于是栈也有顺序存储和链式存储两种实现方式。

栈的顺序存储——顺序栈

栈的链式存储——链栈

顺序栈的表示和实现

存储方式：同一般线性表的顺序存储结构完全相同

利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素。栈底一般在低地址端。

附设top指针，指示栈顶元素在顺序栈中的位置。

另设base指针，指示栈底元素在顺序栈中的位置。

但是，为了方便操作，通常top指示真正的栈顶元素之上的下标地址。

另外，用stacksize表示栈可使用的最大容量。

栈满时的处理方法：

1.报错，返回操作系统

2.分配更大的空间，作为栈的存储空间，将原栈的内容移入新栈。

使用数组作为顺序栈存储方式的特点：

简单、方便、但易产生溢出，数组大小固定

上溢（OVERFLOW）:栈已经满，又要压入元素

下溢（UNDERFLOW）：栈已经空，还要弹出元素

注：上溢是一种错误，使问题的处理无法进行；而下溢一般认为是一种结束条件，即问题处理结束。

#define MAXSIZE 1000 typedef struct { ElemType *base;//栈底指针 ElemType *top;//栈顶指针 int stacksize;//栈可用最大容量 }SqStack;

顺序栈的初始化

Status InitStack( SqStack &S) { s.base=(SElemType*)malloc(MAXSIZE*sizeof(SElemType)); if(!s.base) exit(OVERFLOW); s.top=s.base; s.stacksize=MAXSIZE; return OK; }

顺序栈判断栈是否为空

Status StackEmpty(SqStack S) { if(S.top==S.base) return TRUE; else return FALSE; }

求顺序栈的长度

int StackLength(SqStack S) { return S.top-S.base; }

清空顺序栈

Status ClearStack(SqStack S) { if(S.base) S.top=S.base; return OK; }

销毁顺序栈

Status DestroyStack(SqStack &S) { if(S.base) { delete S.base; S.stacksize=0; S.base=S.top=NULL; } return OK; }

取栈顶元素

Status GetTop(SqStack s,SElemType &e) { if(s.top==s.base) return ERROR; e=*(s.top-1); return OK; }

⭐顺序栈的入栈

1.判断是否栈满，若满则出错（上溢）

2.元素e压入栈顶

3.栈顶指针加1

Status Push(SqStack &s , SElemType e){ if(s.top-s.base>=s.stacksize) { s.base=(SElemType*) realloc (s->base,(s.stacksize+STACKINCREMENT)*sizeof(SElemType)); if(!s.base) exit(OVERFLOW); s.top=s.base+s.stacksize; s.stacksize+=STACKINCREMENT; } *s.top++ = e;//*S.top=e; S.top++; return OK; }

⭐顺序栈的出栈

1.判断是否栈空，若空则出错（下溢）

2.获取栈顶元素e

3.栈顶指针减1

Status Pop(SqStack &s,SElemType &e) { if(s.top==s.base) //等价if(StackEmpty(S)) return ERROR; e = *--s.top ;//--S.top; e=*S.top return OK; }

顺序栈代码实现

#include<stdio.h> #include<stdlib.h> #define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 #define OK 1 #define OVERFLOW -2 #define ERROR 0 typedef int SElemType; typedef int Status; typedef struct{ SElemType *base; SElemType *top; int stacksize; }SqStack; Status InitStack(SqStack *s) { s->base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType)); if(!s->base) exit(OVERFLOW); s->top=s->base; s->stacksize=STACK_INIT_SIZE; return OK; } Status GetTop(SqStack s,SElemType* e) { if(s.top==s.base) return ERROR; *e=*(s.top-1); return OK; } Status Push(SqStack *s,SElemType e) { if(s->top-s->base>=s->stacksize) { s->base=(SElemType*) realloc (s->base,(s->stacksize+STACKINCREMENT)*sizeof(SElemType)); if(!s->base) exit(OVERFLOW); s->top=s->base+s->stacksize; s->stacksize+=STACKINCREMENT; } *s->top++=e; return OK; } Status Pop(SqStack *s,SElemType *e) { if(s->top==s->base) return ERROR; *e=* -- s->top; return OK; } Status StackEmpty(SqStack s) { return s.top==s.base; } Status StackLength(SqStack *S) { if(S->top==S->base) return 0; else return (Status)(S->top-S->base); } Status DestroyStack(SqStack *S) { free(S->base); S->base=S->top=NULL; S->stacksize=0; return OK; } Status ClearStack(SqStack S) { if(S.base) S.top=S.base; return OK; } Status StackTraverse(SqStack *S) { SElemType *p; if(S->top==S->base) { printf("NULL\n"); return 0; } p=S->top; while(p>S->base) { p--; printf("%d\t",*p); } printf("\n"); return OK; } int main() { SqStack S; InitStack(&S); SElemType e; int x,i; printf("请输入栈的长度："); scanf("%d",&x); for(i=1;i<=x;i++) { scanf("%d",&e); Push(&S,e); } if(StackEmpty(S)) { printf("栈空！\n"); } else { printf("栈不空！\n"); } printf("栈的长度为%d\n",StackLength(&S)); printf("顺序栈为：\n"); StackTraverse(&S); GetTop(S,&e); printf("栈顶元素为%d\n",e); printf("请输入要插入的元素:\n"); scanf("%d",&e); Push(&S,e); printf("新栈为：\n"); StackTraverse(&S); printf("删除栈顶元素：\n"); e=Pop(&S,&e); printf("%d\n",e); printf("新栈为：\n"); StackTraverse(&S); printf("销毁\n"); DestroyStack(&S); StackTraverse(&S); return 0; }

链栈的表示和实现

链栈是运算受限的单链表，只能链表头部进行操作

链栈可以有头结点，也可以不设头结点。

带有头结点时，空栈时head->next=NULL 不带头结点，空栈时head=NULL 链栈的栈顶元素以头指针唯一标识，即链栈的头指针即为栈顶指针。 链栈不设置栈底指针。

typedef struct StackNode { ElemType data; struct StackNode *next; }StackNode,*LinkStack; LinkStack S;

链表的头指针就是栈顶

不需要头结点

基本不存在栈满的情况

空栈相当于头指针指向空，链栈的空其实就是top=NULL的时候

插入和删除仅在栈顶处执行

链栈的结构代码

typedef struct SNode { SElemType data; struct SNode *next; }SNode, *LinkStack;

链栈初始化

void InitStack(LinkStack &S) { S=NULL; return OK; }

判断链栈是否为空

Status StackEmpty(LinkStack S) { if(S==NULL) return TRUE; else return FALSE; }

链栈的入栈

Status Push(LinkStack &S,ElemType e) { LinkStack s; s=(LinkStack)malloc(sizeof(Node)); s->data=e;//将新结点数据域置为e s->next=S->top;//把当前的栈顶元素赋给新结点的直接后继，如图中① S->top=s;//将新的结点e赋值给栈顶指针，如图中② return OK; }

链栈的出栈

至于链栈的出栈操作，也是简单的三句操作。假设变量p用来存储要删除的栈顶结点，将栈顶指针下移一位，最后释放p即可。

//若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK，否则返回ERROR； Status Pop(LinkStack *S,ElemType *e) { LinkStack p; if(StackEmpty(*S)) return ERROR; *e=S->top->data; p=S->top;//将栈顶结点赋值给p，如图中③ S->top=S->top->next;//使得栈顶指针下移一位，指向后一结点，如图中④ free(p); return OK; }

链栈的出栈和入栈时间复杂度皆为O（1）

取栈顶元素

ElemType GetTop(LinkStack S) { if(S!=NULL) return S->data; }

对比下顺序栈与链栈，它们在时间复杂度上是一样的，均为 O(1) 。对于空间性能，顺序栈需要事先确定一个固定的长度，可能会存在内存空间浪费的问题，但它的 优势是存取时定位很方便，而链栈则要求每个元素都有指针域，这同时也增加了一些 内存开销，但对于栈的长度无限制。所以它们的区别和线性表中讨论的一样， 如果栈的使用过程中元素变化不可预料，有时很小，有时非常大，那么最好是用链栈，反之，如果它的变化在可控范围内，建议使用顺序栈会更好一些。

链栈代码实现

#include<stdio.h> #include<stdlib.h> #define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 typedef int Status; typedef int SElemType; //定义链栈 typedef struct SNode { SElemType data; struct SNode *next; }SNode,*SNodeptr; typedef struct LinkStack { SNodeptr top; int count; }LinkStack; int InitStack(LinkStack *S) { S->top=(SNodeptr)malloc(sizeof(SNode)); if(S->top=NULL) return 0; else { S->top=NULL; S->count=0; return 1; } return OK; } Status StackEmpty(LinkStack S) { if(S.top=NULL) return TRUE; else return FALSE; } Status Push(LinkStack *S,SElemType e) { SNodeptr s; s=(SNodeptr)malloc(sizeof(SNode)); s->data=e;//将新结点数据域置为e s->next=S->top;//把当前的栈顶元素赋给新结点的直接后继 S->top=s;//将新的结点e赋值给栈顶指针 return OK; } //若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK，否则返回ERROR； Status Pop(LinkStack *S,SElemType *e) { SNodeptr p; if(StackEmpty(*S)) return ERROR; *e=S->top->data; p=S->top;//将栈顶结点赋值给p S->top=S->top->next;//使得栈顶指针下移一位，指向后一结点 free(p); return OK; } SElemType GetTop(LinkStack S) { SNodeptr p; p=S.top; if(StackEmpty(S)) return ERROR; else return p->data; } Status StackLength(LinkStack S) { int n=0; SNodeptr p; p=S.top; while(p) { n++; p=p->next; } return n; } Status ClearStack(LinkStack *S) { SNodeptr p,q; p=S->top; while(p) { q=p; p=p->next; free(q); } S->count=0; return OK; } Status DestroyStack(LinkStack *S) { SNodeptr p=S->top,q; while(p) { q=p->next; free(p); p=q; } return OK; } void Print(LinkStack S) { SNodeptr p=S.top; while(p) { printf("%d\t",p->data); p=p->next; } } int main() { LinkStack S; InitStack(&S); int x,i; SElemType e; printf("请输入栈的长度："); scanf("%d",&x); for(i=1;i<=x;i++) { scanf("%d",&e); Push(&S,e); } Print(S); e=StackLength(S); printf("\n该链栈的长度为%d\n",e); e=GetTop(S); printf("\n该链栈的栈顶元素为%d\n",e); printf("\n删除栈顶元素\n"); Pop(&S,&e); printf("删除后的栈为：\n"); Print(S); return 0; }