栈——栈的定义及基本操作(初始化、判空、进栈、出栈、遍历栈、销毁栈等)

文章目录

    • 栈的定义
    • 栈的存储
    • 栈上的基本操作
      • 初始化
      • 判空操作
      • 进栈操作
      • 出栈操作
      • 读栈顶元素
      • 遍历栈
      • 销毁栈
    • 完整代码及实例
    • 共享栈

栈的定义

栈(Stack)是只允许在一端进行插入或删除操作的线性表。

栈的示意图:
栈——栈的定义及基本操作(初始化、判空、进栈、出栈、遍历栈、销毁栈等)_第1张图片

  • 栈顶Top:线性表允许插入和删除的那一端。
  • 栈底Bottom:固定的,不允许进行插入和删除的另一端。

 假设某个栈S={a1,a2, … ,an},如上图所示,则a1为栈底元素,an为栈顶元素。由于只能在栈顶进行插入和删除操作,故进栈顺序为a1,a2, … ,an,出栈顺序为an, … ,a2,a1。故栈的操作特性是后进先出LIFO(Last In First Out),称为后进先出的线性表。

 空栈:不含任何元素的空表。


栈的存储

 栈的存储方式有两种:顺序栈和链栈,即栈的顺序存储和链式存储。
 采用顺序存储的栈称为顺序栈,它利用一组地址连续的存储单元存放自栈底到栈顶的元素,同时附设一个指针(top)指示当前栈顶的位置。
 栈的顺序存储类型描述:

#define MaxSize 100 //定义栈中元素的最大个数
typedef struct SqStack{
    int data[MaxSize]; //存放栈中的元素
    int top; //栈顶指针
}SqStack;

 采用链式存储的栈称为链栈,链栈便于多个栈共享存储空间和提高其效率,且不存在栈满上溢的情况。通常采用单链表实现,并且所有操作都是在单链表的表头进行的。在本文中主要是介绍了顺序栈下的一些基本操作,关于链栈的实现与单链表类似,可以参考单链表的定义及其基本操作。

 栈的链式存储类型描述:

typedef struct LinkNode{
    int data; //数据域
    struct LinkNode *next; //指针域
}*LiStack; //栈类型定义


栈上的基本操作

 栈的基本操作包括:

  • 初始化InitStack(&S);
  • 判空Empty(S);
  • 进栈Push(&S, x);
  • 出栈Pop(&S, &x);
  • 读栈顶元素GetTop(S);
  • 遍历栈PrintStack(&S);
  • 销毁栈DestroyStack(&S);

 [注]以上操作均采用顺序栈来实现。


初始化

初始时设置S.top = -1。

//初始化
void InitStack(SqStack &S){
    S.top = -1;
}

判空操作

 栈空条件:S.top == -1; 栈满条件:S.top ==MaxSize-1。

//判栈空
bool Empty(SqStack S){
    if(S.top == -1){
        return true;
    }else{
        return false;
    }
}

进栈操作

 由于初始设置S.top=-1,故栈顶指针先加一,再入栈。

栈——栈的定义及基本操作(初始化、判空、进栈、出栈、遍历栈、销毁栈等)_第2张图片

//入栈
void Push(SqStack &S, int x){
    if(S.top == MaxSize-1){
        cout<<"栈满"<<endl;
        return;
    }
    S.data[++S.top] = x; //指针先加一,再入栈
}

出栈操作

 先出栈,指针再减一。

栈——栈的定义及基本操作(初始化、判空、进栈、出栈、遍历栈、销毁栈等)_第3张图片

//出栈
void Pop(SqStack &S, int &x){
    if(S.top == -1){
        cout<<"栈空"<<endl;
        return;
    }
    x = S.data[S.top--]; //先出栈,指针再减一
}

读栈顶元素

//读栈顶元素
int GetTop(SqStack S){
    if(S.top == -1){
        cout<<"栈空"<<endl;
        return -1;
    }else{
        return S.data[S.top];
    }
}

遍历栈

 当栈不为空时,循环输出当前栈顶元素。

//遍历栈
void PrintStack(SqStack S){
    while(S.top != -1){
        cout<<S.data[S.top--]<<" ";
    }
    cout<<endl;
}

销毁栈

 栈的销毁令S.top = -1即可。

//销毁栈
void DestroyStack(SqStack &S){
    S.top = -1;
}

完整代码及实例

 完整代码及实例:

#include
using namespace std;

#define MaxSize 100 //定义栈中元素的最大个数
typedef struct SqStack{
    int data[MaxSize]; //存放栈中的元素
    int top; //栈顶指针
}SqStack;

//初始化
void InitStack(SqStack &S){
    S.top = -1;
}

//判栈空
bool Empty(SqStack S){
    if(S.top == -1){
        return true;
    }else{
        return false;
    }
}

//入栈
void Push(SqStack &S, int x){
    if(S.top == MaxSize-1){
        cout<<"栈满"<<endl;
        return;
    }
    S.data[++S.top] = x;
}

//出栈
void Pop(SqStack &S, int &x){
    if(S.top == -1){
        cout<<"栈空"<<endl;
        return;
    }
    x = S.data[S.top--];
}

//读栈顶元素
int GetTop(SqStack S){
    if(S.top == -1){
        cout<<"栈空"<<endl;
        return -1;
    }else{
        return S.data[S.top];
    }
}

//遍历栈
void PrintStack(SqStack S){
    while(S.top != -1){
        cout<<S.data[S.top--]<<" ";
    }
    cout<<endl;
}

//销毁栈
void DestroyStack(SqStack &S){
    S.top = -1;
}

int main(){
    SqStack S;
    InitStack(S);
    Push(S,1);//入栈
    Push(S,2);
    Push(S,3);
    Push(S,4);
    cout<<"栈顶元素为:"<<GetTop(S)<<endl;
    cout<<"出栈顺序为:";
    PrintStack(S);
    int x;
    Pop(S,x);
    cout<<x<<"出栈"<<endl;
    cout<<"栈中剩余元素:";
    PrintStack(S);
    Pop(S,x);
    cout<<x<<"出栈"<<endl;
    cout<<"栈中剩余元素:";
    PrintStack(S);
    if(!Empty(S)){
        cout<<"当前栈不为空"<<endl;
    }else{
        cout<<"当前栈为空"<<endl;
    }
    return 0;
}

 运行结果:
栈——栈的定义及基本操作(初始化、判空、进栈、出栈、遍历栈、销毁栈等)_第4张图片


共享栈

 利用栈底位置相对不变的特性,可以让两个顺序栈共享一个一维数据空间,将两个栈的栈底分别设置在共享空间的两端,两个栈顶向共享空间的中间延伸。如下图所示:

栈——栈的定义及基本操作(初始化、判空、进栈、出栈、遍历栈、销毁栈等)_第5张图片
两个栈的栈顶指针都指向栈顶元素。

判空:top0 = -1 时0号栈为空, top1 = MaxSize-1 时1号栈为空。

栈满:当且仅当两个栈顶指针相邻,即top1 - top0 = 1 时栈满。

进栈:0号栈进栈时,top0先加一再赋值, 1号栈进栈时top1先减一再赋值。

出栈:0号栈出栈时,先出栈top0再减一, 1号栈出栈时先出栈top1再加一。

你可能感兴趣的