线性结构笔记（二）

（二）堆栈（先入后出，后入先出）

1.堆栈的顺序存储

定义（Top 是数组下标，对应栈顶元素，Data 用于指向之后定义的数组）

typedef int Position;
typedef struct SNode * PtrToSNode;
struct SNode
{
    ElementType * Data;
    Position Top;
    int MaxSize;
};
typedef PtrToSNode Stack;

生成堆栈

/*创建堆栈，其中有一个指针，指向动态分配的数组*/
Stack CreateStack(int MaxSize)
{
    Stack S = (Stack)malloc(sizeof(struct SNode));
    S->Data = (ElementType *)malloc(MaxSize * sizeof(ElementType));
    S->Top = -1;
    S->MaxSize = MaxSize;
    return S;
}

判断堆栈是否已满

bool IsFull(Stack S)
{
    /*S->Top 是数组下标，例如数组a有5个元素，最后一个元素下标是5-1，所以是MaxSize-1*/
    return (S->Top==S->MaxSize-1);
}

压栈

bool Push(Stack S, ElementType X)
{
    if(IsFull(S))
    {
        printf("堆栈已满\n");
        return false;
    }
    else
    {
        /*S->Data[S->Top] 指向末尾元素，下面对最后一个的下一个元素赋值，此时 S->Data[S->Top] 又指向新的末尾元素*/
        S->Data[++(S->Top)] = X;
        return true;
    }
}

判断堆栈是否为空

bool IsEmpty(Stack S)
{
    return (S->Top==-1);
}

出栈

ElementType Pop(Stack S)
{
    if(IsEmpty)
    {
        printf("堆栈为空\n");
        return ERROR;
    }
    else
    {
        return S->Data[(S->Top)--];
    }
}

总结：顺序栈就是在数组末尾进行添加和删除操作。

2.双栈顶的顺序栈

定义

typedef int Position;
typedef struct SNode * PtrToSNode;
struct SNode
{
    ElementType * Data;
    Position Top1;
    Position Top2;
    int MaxSize;
};
typedef PtrToSNode Stack;

创建堆栈（Top1 和 Top2 都在数组之外）

Stack CreateStack(int MaxSize)
{
    Stack S = (Stack)malloc(sizeof(struct SNode));
    S->Data = (ElementType *)malloc(MaxSize*sizeof(ElementType));
    S->Top1 = -1;
    S->Top2 = MaxSize;
    return S;
}

判断堆栈是否已满（当 Top1 和 Top2 连起来的时候就是满了）
1
2
3
4
bool IsFull(Stack S)
{
return (S->Top1+1==S->Top2);
}

压栈（根据 Tag 判断加在左边还是右边）

bool Push(Stack S, ElementType X, int Tag)
{
    if(IsFull(S))
    {
        printf("堆栈已满\n");
        return false;
    }
    else
    {
        if(Tag==1)
            S->Data[++(S->Top1)] = X;
        else
            S->Data[--(S->Top2)] = X;
        return true;
    }
}

出栈（先根据 Tag 判断那边出栈，再判断那边是否为空）

ElementType Pop(Stack S, int Tag)
{
    if(Tag==1)
    {
        if(S->Top1==-1)
        {
            printf("左堆栈为空\n");
            return ERROR;
        }
        else
            return S->Data[(S->Top1)--]
    }
    else
    {
        if(S->Top2==S->MaxSize)
        {
            printf("右堆栈为空\n");
            return ERROR;
        }
        else
            return S->Data[(S->Top2)++];
    }
}

总结：双栈顶和单栈顶操作相似，都是在栈顶添加和删除元素。

3.堆栈的链式存储

定义

typedef struct SNode * PtrToSNode;
struct SNode
{
    ElementType Data;
    PtrToSNode Next;
};
typedef PtrToSNode Stack;

创建头结点

Stack CreateStack()
{
    /*创建堆栈头结点，返回该结点指针*/
    Stack S;
    S = (Stack)malloc(sizeof(struct SNode));
    S->Next = NULL;
    return S;
}

入栈（添加在头结点之后）

bool Push(Stack S, ElementType X)
{
    PtrToSNode temp;
    temp = (PtrToSNode)malloc(sizeof(struct SNode));
    temp->Data = X;
    temp->Next = S->Next;
    S->Next = temp;
    return true;
}

判断堆栈是否为空

bool IsEmpty(Stack S)
{
    return (S->Next==NULL);
}

出栈（删除头结点，返回栈顶元素）

ElementType Pop(Stack S)
{
    PtrToSNode temp;
    ElementType top;
    if(IsEmpty(S))
    {
        printf("堆栈为空\n");
        return ERROR;
    }
    temp = S->Next;
    top = temp->Data;
    S->Next = temp->Next;
    free(temp);
    return top;
}

总结：用链表实现堆栈，入栈就是在头结点之后添加一个结点，出栈就是释放头结点指向的结点，并返回该结点的数据。头结点那头是栈顶，如果用末尾作为头结点不好。（注意：链表实现跟数组实现的栈顶是位置不一样的）

（二）堆栈（先入后出，后入先出）

1.堆栈的顺序存储

2.双栈顶的顺序栈

3.堆栈的链式存储