数据结构重学日记（十一）栈

概念

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

栈顶

栈中允许进行插入和删除的那一端。

栈底

固定的，不允许进行插入和删除的另一端。

C -- new top
B -- top
A -- bottom

栈的特点

• 栈是受限的线性表，所以依然具有线性关系
• 栈中的元素遵循先入后出

顺序栈

栈是线性表的特例，栈的顺序存储是线性表顺序存储的简化。

栈的顺序存储结构也叫做顺序栈。

实现

#define MaxSize 50
typedef int ElemType;

typedef struct {
    ElemType data[MaxSize];
    int top;

}SqStack;

• top 值不能超过 MaxSize
• 空栈的判定条件通常定位 top == -1
• 满栈的判定条件通常为 top == MaxSize -1
• 栈中数据元素个数为 top + 1

顺序栈的操作

#define MaxSize 50
typedef int ElemType;
typedef struct {
    ElemType data[MaxSize];
    int top;

}SqStack;

int StackEmpty(SqStack S){
    if(S.top == 1) return 1;
    else return 0;
}


int Push(SqStack * S, ElemType * x){
    if(S->top == MaxSize - 1) return 0;
    S->data[++S->top] = x; // 上移指针并赋值
    return 1;
}

int Pop(SqStack * S, ElemType * x){
    if(S->top == 1) return 0;
    x = S->data[S->top --];
    return x;
}

int GetTop(SqStack * S, ElemType * x){
    if(S->top == -1) return 0;
    x = S->data[S->top];
    return x;
}

共享栈

即把存储空间共享的栈。

0	1	2	3	4	5	6	7	8	9
A	B				E	D	C	B	A

左边 A 为栈1 的底，右边 A 为栈2 的底。

栈满的条件：指针 top1 + 1 = top2

实现

#define MaxSize 100
typedef struct{
    ElemType data[MaxSize];
    int top1;
    int top2;
}SqDoubleStack;

进栈操作

int PushD(SqDoubleStack * S, ElemType x, int StackNum){
    if(S->top1 + 1 == S->top2) return 0; // 栈满
    if(StackNum == 1) S->data[++S->top1] = x; // 栈1有元素进栈
    else if(StackNum == 2) S->data[--S->top2] = x; // 栈2 有元素进栈
    return 1;
}