Day-20 堆叠(Stack)

堆叠介绍

堆叠是限制插入元素和删除元素只能在同一个位置的表(list)，该位置一般来说称为栈顶(Top)。对堆叠的基本操作有 Push(推入，将资料加到栈顶) 和 Pop(弹出，将栈顶的资料移出) 这两种操作。

Push可以把它想像成把洋芋片放到洋芋片罐里，Pop则是拿出洋芋片

堆叠有时候也会被称为先进後出表(LIFO，Last In First Out)，最先进入的资料会最後被弹出，如同函式呼叫，最先呼叫的函式会最後弹出记忆体。

堆叠在软件中是相当常见的应用，像是浏览器的上一页就是一种应用，会按照你所存取的网页，依照堆叠的顺序进行存取(事实上，上一页其实并非逻辑上的上一页，如果现在在yahoo，上一页是google，我们按下上一页後会回到google，但再按上一页事实上并不是回到yahoo...要不然就是死循环了...)

堆叠实做

一般来说我们有两种方法可以实作出堆叠，一种为使用单向链结串列的方式，另一种则是使用阵列的方式，以下先举单向链结串列的实作方式。

堆叠的ADT，使用单向链结串列(single linked list)

我们透过在表的顶端插入来实现Push的操作，通过删除顶端资料来实作Pop，Top表示回传最顶端的值，以下为堆叠的ADT

#ifndef _Stack_h

struct Node;
typedef struct Node *PtrToNode;
typedef PtrToNode Stack;

int IsEmpty(Stack S);
Stack CreateStack(void);
void DisposeStack(Stack S);
void MakeEmpty(Stack S);
void Push(int X, Stack S);
int Top(Stack S);
void Pop(Stack S);

#endif

/* Place in implementation file */
/* Stack implementation is a linked list with a header*/
struct NODE{
    ElementType Element;
    PtrToNode next;
};

IsEmpty实作

int IsEmpty(Stack S)
{
    return S->next == NULL; 
}

为空则回传true，否则false。

CreateStack实作

Stack CreateStack(void)
{
    Stack S = (Stack)malloc(sizeof(Stack));

    if(S == NULL)
    {
        printf("Out of space!!!");
    }
    S->next = NULL;
    MakeEmpty(S);
    return S;
}

令节点S为指向Node的指标(typedef取代成 Stack)，并将分配到记忆体空间的指标回传给S，下一个节点为空，并回传S。

MakeEmpty实作

void MakeEmpty(Stack S)
{
    if(S == NULL)
    {
        printf("Must use CreateStack first");
    }
    else
    {
        while(!IsEmpty(S))
        {
            Pop(S);
        }
    }
}

当传入的Stack S不为空时，将所有的元素Pop，建立出空的Stack。

Push实作

void Push(int X, Stack S)
{
    Stack TmpCell = (Stack)malloc(sizeof(Stack));

    if(TmpCell == NULL)
    {
        printf("Out of space!!!");
    }
    else
    {
        TmpCell->value = X;
        TmpCell->next = S->next;
        S->next = TmpCell;
    }
}

第一步:建立节点，如果成功建立，则填入传入值X

第二步:将原先链结串列的内容接续到TmpCell

第三步:将原链结串列的头的下一个元素设为TmpCell

Top实作

int Top(Stack S)
{
    if(!IsEmpty(S))
    {
        return S->next->value;
    }
    printf("Empty Stack");
    return 0;
}

直接回传头的元素

Pop实作

void Pop(Stack S)
{
    PtrToNode FirstCell;

    if(IsEmpty(S))
    {
        printf("Empty Stack");
    }
    else
    {
        FirstCell = S->next;
        S->next = S->next->next;
        free(FirstCell);
    }
}

第一步，将FirstCell指向S->next，也就是将FirstCell与原先串链串接

第二步，将S->next指向S->next->next，也就是将头的下一个节点指到下下个节点

第三步，将FirstCell所指到的节点，也就是S->next记忆体空间释放

小节

我们所有的操作，都是线性时间，，因为我们不需要任何涉及堆叠大小的操作(遍历等等...)，但是缺点为使用链结串列进行实作会大量的使用到malloc和free函式，而这一些函式操作是相当的耗费时间的。

堆叠的ADT，使用阵列(Array)

除了使用链结串列进行实作，我们也可以使用阵列的方式进行实作，相较於链结串列的实作，我们需要注意阵列大小的问题，但是一般来说，我们不会太在意阵列大小问题，原因为同一时间，堆叠内的元素个数通常不会太大，因此宣告一个足够大小的阵列便足够。

若同一时间可能存在大量的元素，导致我们需要宣告较大的阵列时，使用链结串列的方式可以减少空间的浪费。

以下为使用阵列实作的堆叠ADT模型。

#ifndef _Stack_h

struct StackRecord;
typedef struct StackRecord *Stack;

int IsEmpty(Stack S);
int IsFull(Stack S);
Stack CreateStack(int MaxElements);
void DisposeStack(Stack S);
void MakeEmpty(Stack S);
void Push(ElementType X, Stack S);
ElementType Top(Stack S);
void Pop(Stack S);
ElementType TopAndPop(Stack S);

#endif /*_Stack_h */

/* Place in implementation file */
/* Stack implementation is a dynamically allocated array */
#define EmptyTOS (-1)
#define MinStackSize (5)

struct StackRecord{
    int Capacity;
    int TopOfStack;
    ElementType *array;
};

我们在ADT模型中，

CreateStack实作

Stack CreateStack(int MaxElements)
{
    Stack S;
    if(MaxElements < MinStackSize)
    {
        printf("Stack size is too small");
    }
    
    S = (Stack *)malloc(sizeof(sturct StackRecord));
    if(S == NULL)
    {
        printf("Out of space!!!");
    }
    S->array = malloc(sizeof(ElementType) * MaxElements);
    if(S->array == NULL)
    {
        printf("Out of space!!!");
    }
    S->Capacity = MaxElements;
    MakeEmpty(S);
    
    return S;
}

DisposeStack实作

void DisposeStack(Stack S)
{
    if(S != NULL)
    {
        free(S->array);
        free(S);
    }
}

IsEmpty实作

int IsEmpty(Stack S)
{
    return S->TopOfStack == EMptyTOS;
}

MakeEmpty实作

void MakeEmpty(Stack S)
{
    S->TopOfStack = EmptyTOS;
}

Push实作

void Push(ElementType X, Stack S)
{
    if(IsFull(S))
    {
        printf("Full Stack");
    }
    else
    {
        S->array[++S->TopOfStack] = X;
    }
}

Top实作

ElementType Top(Stack S)
{
    if(!IsEmpty(S))
    {
        return S->array[S->TopOfStack];
    }
    printf("Empty Stack");
    return 0;
}

Pop实作

void Pop(Stack S)
{
    if(IsEmpty(S))
    {
        printf("Empty Stack");
    }
    else
    {
        S->TopOfStack--;
    }
}

参考资料: 大话数据结构，C语言程序设计现代方法第2版，Introduction to algorithms 3rd，图片源於网路(没有工商洋芋片~)