数据结构导论(第三章栈）

一、栈

栈和队列可看作是特 殊的线性表，它们是 运算受限的线性表

定义：栈是只能在表的一端（表尾）进行 插入和删除的线性表

• 允许插入及删除的一端（表尾）称为栈顶(top)； .
• 另一端（表头）称为栈底(bottom)。 .
• 当表中没有元素时称为空栈
• 进栈——在栈顶插入一元素；
• 出栈——在栈顶删除一元素

特点：后进先出

　　栈中元素按a1，a2，a3，…an的次序进栈，出栈的第一个元素应 为栈顶元素。换句话说，栈的修改是按后进先出的原则进行的。 因此，栈称为后进先出线性表（lifo）。

栈的用途：常用于暂时保存有待处理的数据。

栈的基本操作

• （1）初始化栈：initstack(s);
• （2）判栈空：emptystack (s);
• （3）进栈：push (s,x);
• （4）出栈：pop (s);
• （5）取栈顶： gettop(s);

栈的分类：按照顺序结构存储是顺序栈、按照链式结果存储是链栈

二、顺序栈

顺序栈—— 即栈的顺序实现；

栈容量——栈中可存放的最大元素个数；

栈顶指针 top——指示当前栈顶元素在栈中的位置；

栈空——栈中无元素时，表示栈空；

栈满——数组空间已被占满时，称栈满；

下溢——当栈空时，再要求作出栈运算，则称“下溢”；

上溢——当栈满时，再要求作进栈运算，则称“上溢”。

 

1、顺序栈的类型定义

const int maxsize=6;
typedef struct seqstack {
　　datatype data[maxsize];
　　int top;
}seqstk;

seqstk *s ; 定义一顺序栈s
约定栈的第1个元素存在data[1]中,则
s->top==0 代表顺序栈s为空；
s->top==maxsize-1 代表顺序栈s为满

2、初始化：

int initstack(seqstk *stk){
    stk->top=0;
    return 1;
}

3、判栈空（栈空时返回值为1，否则返回值为0）

int emptystack(seqstk *stk){
    if(stk->top= =0) return 1;
    else return 0;
}

4、进栈

int push(seqstk *stk, datatype x){
    /*数据元素x进顺序栈sq*/
    if（stk->top==maxsize -1) /*判是否上溢*/
    { error(“栈满”);return 0;} /*上溢*/
    else {
        stk->top++；/*修改栈顶指针，指向新栈顶*/
        stk->data[stk->top]=x; /*元素x插入新栈顶中*/
        return 1;
    }
    }
}

 5、出栈

int pop(seqstk *stk){
    /*顺序栈sq的栈顶元素退栈*/
    if(stk->top==0) /*判是否下溢*/
    { error(“栈空”);return 0;} /*下溢*/
    else {
    stk->top-- ； /*修改栈顶指针，指向新栈顶*/
    return 1;
    }
}/*pop*/

6、取栈顶元素

datatype gettop(seqstk *stk)
{
if(emptystack(stk))
return nulldata;
else
return stk->data[stk->top];
}

三、链栈

链栈的定义： 栈的链式存储结构称为链栈，它是运算受限的单链表， 插入和删除操作仅限制在表头位置上进行。栈顶指针就是链 表的头指针

 

 

 

 

1、初始化

void initstack(lkstk *ls)
{
　　ls=(lkstk *)malloc(sizeof(lkstk));
　　ls->next=null;
}

2、判栈空

int emptystack(lkstk *ls)
{
    if(ls->next= =null) return 1;
    else return 0;
}

3、进栈——在栈顶插入一元素x

 

 

void push (lkstk *ls, datatype x){ 
    lkstk *temp;
    temp= (lkstk *) malloc (sizeof (lkstk));
    temp->data=x;
    temp->next=ls->next;
    ls->next=temp;
}

4、出栈——在栈顶删除一元素，并返回

 

 

int pop (lkstk *ls)
{
    lkstk *temp;
    if (!emptystack (ls))
    {
        temp=ls->next;
        ls->next=temp->next;
        free(temp);
        return 1;
    }
    else return 0;
}

5、取栈顶元素

datatype gettop(lkstk *ls)
{
    if (!emptystack(ls))
    return ls->next->data;
    else
    return nulldata;
}