学习数据结构--第三章:栈和队列(栈的基本操作)

学习数据结构--第三章:栈和队列(栈的基本操作)

Scroll Down

1.栈的基本概念

栈(Stack) 只允许在 一端 (这一端叫做栈顶) 进行插入或者删除操作的 线性表

在栈中先进入栈的元素会后出栈即:先进后出 (LIFO)

在这里插入图片描述

2.栈的基本操作

InitStack(&s) 初始化一个空栈S
StackEmpty(S) 判断一个栈是否为空,若栈为空则返回true,否则返回 false
Push(&S,x) 进栈,若栈S未满,则将加入使之成为新栈顶。
Pop(&S,&x) 出栈,若栈非空,则弹出栈顶元素,并用x返回。
GetTop(S,&x) 读栈顶元素,若栈非空则用x返回栈顶元素。
ClearStack(&S) 销毁栈,并释放S占用的内存空间。

这里发现:PopGetTop 这两个函数都可以返回栈顶元素,不同的是Pop 会移除栈顶元素,而 GetTop只会获取栈顶元素的值,而不会出栈。

3.栈的顺序存储结构

顺序栈:采用顺序存储的栈

#define MaxSize 50
typedef struct{
     ElemType date[MaxSize];
     int top; //数组的下标
}SqStack;

在这里插入图片描述

3.1判断栈空&满&长度

栈空条件:S.top==-1 ,在栈里面没有内容的时候top代表数组的下标此时值为-1;
栈的长度:S.top+1 ,top代表数据下标,所以栈的长度等于数组下标+1;
栈满条件:S.top==MaxSize-1,如果栈的top下标为数组长度-1说明栈满了。

在这里插入图片描述

3.2 栈的基本操作

3.2.1初始化

void InitStack(SqStack &S){
    S.top == -1;
}

3.2.2判断栈空

boll StackEmpty(SqStack &S){
    if(S.top == -1){
        return true;
    }else{
        return false;
    }
}

3.2.3进栈

boll Push(SqStack &S,ElemType x){
    if(S.top == MaxSize-1){ //栈满
        return fase;
    }
    S.data[++S.top] = x;
    return true;
}

3.2.4出栈

boll Pop(SqStack &S,ElemType &x){
    if(S.top == -1){ //栈空
        return fase;
    }
    x = S.data[S.top--]; 
    return true;
}

3.2.5获取栈顶元素

boll GetTop(SqStack S,ElemType &x){
    if(S.top == -1){ //栈空
        return fase;
    }
    x = S.data[S.top] //只需读取,不需移动下标
    return true; 
}

3.3.共享栈

共享栈:将两个栈底设置在共享空间的两端,栈顶向空间中间延伸;

判空:

  • 0号栈 top==-1
  • 1号栈 top==MaxSize

在这里插入图片描述

判满: tpp1-top0==1

共享栈的优点:存取时间复杂度仍为O(1),且空间利用更加有效。

4.栈的链式存储结构

链栈 采用链式存储的栈

这里不需要头节点,这里规定了第一个结点为栈顶结点所以:所有的操作都要在表头进行

在这里插入图片描述

4.1链栈基本操作

因为相当于是单链表,所以链栈的判空,出栈,栈的长度和单链表的操作基本相同。

欢迎关注公众号 理木客 更多精彩等你发现