线性结构-栈的顺序存储和链式存储实现

栈的顺序存储表示

栈的顺序存储结构简称为顺序栈，和线性表相类似，用一维数组来存储栈。根据数组是否可以根据需要增大，又可分为静态顺序栈和动态顺序栈。静态顺序栈实现简单，但不能根据需要增大栈的存储空间；动态顺序栈可以根据需要增大栈的存储空间，但实现稍为复杂。

栈的动态顺序存储表示

采用动态一维数组来存储栈。所谓动态，指的是栈的大小可以根据需要增加。

• 用bottom表示栈底指针，栈底固定不变的；栈顶则随着进栈和退栈操作而变化。用top(称为栈顶指针)指示当前栈顶位置。
• 用top=bottom作为栈空的标记，每次top指向栈顶数组中的下一个存储位置。
• 结点进栈：首先将数据元素保存到栈顶(top所指的当前位置)，然后执行top加1，使top指向栈顶的下一个存储位置;
• 结点出栈：首先执行top减1，使top指向栈顶元素的存储位置，然后将栈顶元素取出。

栈的静态顺序存储表示

采用静态一维数组来存储栈。

• 栈底固定不变的；栈顶则随着进栈和退栈操作而变化，用一个整型变量top(称为栈顶指针)来指示当前栈顶位置。

• 用top=0表示栈空的初始状态，每次top指向栈顶在数组中的存储位置。
• 结点进栈：首先执行top加1，使top指向新的栈顶位置，然后将数据元素保存到栈顶(top所指的当前位置)。
• 结点出栈：首先把top指向的栈顶元素取出，然后执行top减1，使top指向新的栈顶位置。

若栈的数组有Maxsize个元素，则top=Maxsize-1时栈满。

/*!
 * file 栈的顺序存储实现.cpp
 *
 * author ranjiewen
 * date 2017/03/17 11:13
 *
 * 
 */

#include <stdio.h>
#include <stdlib.h>

typedef int Position;
typedef int ElemType;
#define  ERROR NULL
#define  MAXSIVE 100

struct SNode
{
    ElemType *Data; /*存储元素的数组，动态分配内存*/
    Position Top; /*栈顶元素数组下标*/
    int MaxSize; // 堆栈最大容量
};

typedef struct SNode* Stack;

Stack CreateStack(int MaxSize)
{
    Stack S = (Stack)malloc(sizeof(struct SNode));
    S->Data = (ElemType*)malloc(MaxSize*sizeof(ElemType));
    S->Top = -1; //顺序存储结构时，表示空
    S->MaxSize = MaxSize;
    return S;
}

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

bool Push(Stack S, ElemType x)
{
    if (IsFull(S))
    {
        printf("堆栈满.
");  //栈满时可以再申请空间
        return false;
    }
    else
    {
        S->Data[++(S->Top)] = x;
        return true;
    }
}

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

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

int main()
{
    struct SNode *S = CreateStack(MAXSIVE);
    for (int i = 9; i >= 0;i--)
    {
        Push(S,i);
    }
    for (int i = 0; i < S->Top;i++)
    {
        printf("%d ", S->Data[i]);
    }
    printf("
");
    Pop(S);
    Pop(S);
    for (int i = 0; i < S->Top; i++)
    {
        printf("%d ", S->Data[i]);
    }
    printf("
");
    return 0;
}

存储栈的链式表示

栈的链式存储结构称为链栈,是运算受限的单链表。其插入和删除操作只能在表头位置上进行。因此,链栈没有必要像单链表那样附加头结点,栈顶指针top就是链表的头指针。记住栈顶指针Top只能在表尾，在表头时删除操作不行。

/*!
 * file 线性结构栈的链式存储实现.cpp
 *
 * author ranjiewen
 * date 2017/03/17 14:27
 *
 * 
 */

#include<stdio.h>
#include <stdlib.h>
typedef int ElementType;
#define  ERROR NULL

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 IsEmpty(Stack S)
{ /* 判断堆栈S是否为空，若是返回true；否则返回false */
    return (S->Next == NULL);
}

bool Push(Stack S, ElementType X)
{ /* 将元素X压入堆栈S */
    PtrToSNode TmpCell;

    TmpCell = (PtrToSNode)malloc(sizeof(struct SNode));
    if (!TmpCell)
    {
        printf("申请结点失败!");
        exit(-1);
    }
    TmpCell->Data = X;        //相当于在表头插入
    TmpCell->Next = S->Next;
    S->Next = TmpCell;
    return true;
}

ElementType Pop(Stack S)
{ /* 删除并返回堆栈S的栈顶元素 */
    PtrToSNode FirstCell;
    ElementType TopElem;

    if (IsEmpty(S)) {
        printf("堆栈空");
        return ERROR;
    }
    else {
        FirstCell = S->Next;
        TopElem = FirstCell->Data;
        S->Next = FirstCell->Next;
        free(FirstCell);
        return TopElem;
    }
}

int main()
{
    PtrToSNode stack;
    stack = CreateStack();
    for (int i = 9; i >= 0;i--)
    {
        Push(stack, i);
    }
    PtrToSNode pTemp;
    for (pTemp = stack->Next; pTemp != NULL;pTemp=pTemp->Next) //链式不能用++
    {
        printf("%d ", pTemp->Data);
    }
    printf("
");
    Pop(stack);
    Pop(stack);
    for (pTemp = stack->Next; pTemp != NULL; pTemp=pTemp->Next)
    {
        printf("%d ", pTemp->Data);
    }
    printf("
");
}

reference：[数据结构]线性结构——栈