栈

数据结构

应用:如使用浏览器上网时,不管什么浏览器都有一个"后退"键,你点击后可以按访问顺序的逆序加载浏览过的网页.
<撤销>这种操作就是使用栈来实现的.

栈(stack)是限定仅在表尾进行插入和删除的线性表.

我们把允许插入和删除的一端称为栈顶(top),另一端称为栈底(bottom),不含任何数据元素的栈称为空栈.栈又称为先进后出的线性表.简称LIFO结构.

注:栈就是一个有特殊约束的线性表.

最先进栈的元素就一定最后出栈吗?
不一定,要看什么情况.栈对线性表的插入,删除的位置都进行了限制,并没有对元素的进出时间进行限制,也就是说,在不是所有元素都近栈的情况下,实现进去的元素也可以出栈,只要保证是栈顶元素出栈就可以.
如: 1,2,3依次进栈
① 1,2,3进,再3,2,1出. 出栈顺序为321
② 1进,1出,2进,2出,3进,3出. 出栈顺序为123
③ 1进,2进,2出,1出,3进,3出.出栈次序为213
④ 1进,1出,2进,3进,3出,2出. 出栈次序为132
⑤ 1进,2进,2出,1出,3进,3出. 出栈次序为231

栈的抽象数据模型

插入和删除操作操作会有变化改名为push pop

ADT 栈(stack)
Data
    同线性表.元素具有相同的类型,相邻元素具有前驱和后继的关系
Operation
    InitStack(*S);初始化操作,建立一个空栈S
    DestoryStack(*S);若栈存在,则销毁他
    ClearStack(*S);将栈清空
    StackEmpty(S);若栈为空,返回true,否则返回faluse
    GetTop(S*e);若栈存在非空,用e返回S的栈顶元素
    Push(*S,e);若栈存在,插入新元素e到栈S中并成为栈顶元素
    Pop(*S,e);删除S中的栈顶元素,并用e返回其值.
    StackLength(S);返回栈S的元素个数
endADT

栈的结构定义

typedef int SElemType;/*假定int类型*/
typedef struct
{
    SElemType data[MAXSIZE];
    int top;/*用于栈顶指针*/
}SeqStack;

顺序栈的基本操作:

①初始化

void InitStack(SeqStack *s)
{
    S->top = -1;
}

②判栈空

int IsEmpty(SeqStack *S)
{
    return(S->top==-1? TURE :FALSE);
}

③判栈满

int IsFull(SeqStack *S)
{
    return(S->top==MAXSIZE-1?TRUE:FALSE);
}

④进栈

int Push(SeqStack *S, SElemType x)
{
    if(S->top == MAXSIZE-1)/*栈满*/
        return FALSE;
    S->top++;
    S->data[S->top] = e;
    return TRUE;
}

⑤出栈

int pop(SeqStack *S, SElemType*x)
{
    if(S->top == -1)
        return FALSE;
    *x = S->data[S->top];
    S->top--;
    return TRUE;
}

⑥取栈顶

int GetTop(SeqStack *S,SElemtype*x)
{
    if(S->top == -1)
        return FALSE;
    *x = S->data[S->top];
    return TRUE;
}

注:进栈出栈取栈顶的代码时间复杂度为O(1)

缺陷:必须事先确定数组存储空间的大小

如果我们有两个相同的类型的栈,我们为他们重新开辟了数组空间,极有可能是第一个栈已经满了,再进栈就溢出了,而另一个栈还有很多存储空间,我们完全可以使用一个数组来存储两个栈,只不过我们得使用点小技巧.

双端栈

空间有限的情况下充分利用
两栈共享技术---双端栈

主要利用了栈"栈底位置不变,栈顶位置动态变化"的特性
首先为两个栈申请一个共享的一维数组空间S[M],将两个栈的栈底分别放在一位数组的两端,分别是0,M-1

两栈共享数据结构定义

#define M 100
typedef struct 
{
    SElemType data[M];
    SElemType top[2];/*与上不同的是top指针现在有两个*/
}DqStack;

使用top[0]和top[1]来表示两栈栈顶
注意:1.操作需要表明具体栈(top[0]还是top[1])
2.栈空判断: 栈S1: top[0]=-1;
栈S2: top[1]=M;
3.栈满判断: 当两个栈迎面相迎时才会溢出,即top[0]+1=top[1]

①初始化

void InitStack(DqStack *S)
{
    S->top[0]=-1;
    S->top[1]=M;
}

②进栈

int Push(Dqstack *S, StackElemType x, int i)
{
    if(S->top[0]+1 == S->top[1])/*栈满*/
        return FALSE;
    switch(i)
    {
        case 0: S->top[0]++;
                S->data[S->top[0]]=x;
                break;
        case 1: S->top[1]++;
                S->data[S->top[1]]=x;
                break;
        default: return FALSE;
    }
    return TRUE;
}

栈的链式存储

注意入栈与出栈要检查站是否为空(是否为满)

入栈检查 是否栈满:

if(s = (slStacktype *)malloc(sizeof(slStacktype)) == NULL)
    return FALSE;

出栈检查 是否栈空:

if(top->next == NULL)
    return FALSE;

链栈的c语言定义为:

typedef ELemtype int; //初始数据类型
typedef struct Stacknode
{
    Elemtype data;
    struct Stacknode *next;
}slStacktype;

入栈操作:

int pushLstack(slStacktype *top, Elemtype x)
{/*将元素s压入链栈top之中*/
    slStacktype *p;
    if(p = (slStacktype *)malloc(sizeof(slStacktype)) == NULL)
        return FALSE;
    p->data = x;
    p->next = top->next;
    top->next = p;
    return TRUE;
}

出栈操作:

Elemtype popLstack(slStacktype *top)
{/*从链栈top中删除栈顶元素*/
    slStacktype *p;
    Elemtype x;
    p = top->next;
    top->next = p->next;
    p->data = x;
    free(p);
    return x;
}

多个链栈的操作

我们可以将多个链栈的栈顶指针放在一个一维数组中统一管理

slStacktype *top[M];

其中，top[0],top[1],...,top[M-1]指向M个不同的链栈,分别是M个链栈的栈顶指针,操作时只需确定链栈号i,然后以top[i]为栈顶指针进行栈操作,就可以实现各种操作.
①入栈操作

int pushDupLs(slStacktype *top[M], int i, Elemtype x)
{/*将元素x压入链栈top[i]中*/
    slStacktype *p;
    if( (p = (slStacktype*)malloc(sizeof(slStacktype))) == NULL)
    return FALSE;
    /*申请一个节点*/
    p->data = x;
    p->next = top[i]->next;
    top[i]->next = p;
    return TRUE;
}

②出栈操作

Elemtype popDupLs(slStacktype *top[M], int i)
{/*从链栈top[i]中删除栈顶元素*/
    slStacktype *p;
    Elemtype x;
    if(top[i]->next == NULL)/*空栈*/
        return NULL;
    p = top[i]->next;
    top[i]->next = p->next;
    x = p->data;
    free(p);
    return x;
}