数据结构与算法 －顺序栈及其相关算法

顺序栈及常用名词

1. 顺序栈－ 即栈的顺序实现。

2. 栈容量－ 栈中可存放的最大元素个数。

3. 栈顶指针 top－指示当前栈顶元素在栈中的位置。

4. 栈空－栈中无元素时，表示栈空；

5. 栈满－数组空间已被占满时，称栈满；

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

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

 

顺序栈的类型定义

const int maxsize=6;
typedef struct seqstack {
    DataType data[maxsize];
    int top;
}SeqStk;
// 定义一个顺序栈
SeqStk *s 

s->top==0 代表顺序栈s为空；

s->top==maxsize-1 代表顺序栈s为满 ；

 

顺序栈的运算

1. 初始化

int Initstack(SeqStk *stk){
    stk->top=0;
    return 1;
}

2. 判断栈空

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

3. 进栈

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

4. 出栈

int Pop(SeqStk *stk){
    // 判是否下溢
    if(stk->top==0) { 
        error(“栈空”);
        return 0;
    } else {
        // 修改栈顶指针，指向新栈顶
        stk->top--;
        return 1;
    }
}

5. 取栈顶元素

DataType GetTop(SeqStk *stk){
    if(EmptyStack(stk)){
        return NULLData;
    }else{
        return stk->data[stk->top];
    }
}

 

顺序栈的特殊应用－双栈

在某些应用中，为了节省空间，让两个数据元素类型一致的栈共享一维数组空间data[max]，成为双栈，两个栈的栈底分别设在数组两端，让两个栈彼此迎面“增长”，两个栈的栈顶变量分别为top1，top2，仅当两个栈顶位置在中间相遇时才会发生“上溢”，即top1+1=top2