堆栈_顺序栈与链式栈

逻辑结构：一对一关系(1:1)
存储结构：顺序栈与链栈，顺序栈常见
运算规则：后进先出（先进后出）
操作集合：
(1)StackInitiate(S) 初始化堆栈S
(2)StackNotEmpty(S) 堆栈S非空否
(3)StackPush(S,x) 入栈
(4)StackPop(S,d) 出栈
(5)StackTop(S,d) 取栈顶数据元素
(6)Destroy(S) 销毁

顺序栈：

定义

//栈的定义 
typedef struct
{
    int stack[MaxStackSize];
    int size;
}SequenceStack;

初始化

//栈的初始化
void StackInitialize(SequenceStack *S)
{
    S->size = 0;
}

入栈（压栈）

int StackPush(SequenceStack *S, int x)
{
    if(S->size >= MaxStackSize)
    {
        printf("栈已满，无法再插入！\n");
        return 0;
    }
    else
    {
        S->stack[S->size] = x;
        S->size++;
        return 1;
    }
} 

出栈

int StackPop(SequenceStack *S, int *d)
{
    if(S->size <= 0)
    {
        printf("栈已空，无法再出栈！\n");
        return 0;
    }
    else
    {
        S->size--;//栈的下标从0开始，获取栈顶元素时得先减一
        *d = S->stack[S->size];
        return 1;
    }
}

取顶

//取栈顶数据元素
int StackTop(SequenceStack S, int *d)
{
    if(S.size <= 0)
    {
        printf("栈已空\n");
        return 0;
    }
    else
    {
        *d = S.stack[S.size - 1];
        return 1;       
    }
} 

总结：
1、顺序堆栈的定义与初始化与顺序表一样：用数组存数据、设立最大值（MaxSize）与当前大小（Size）；
2、入栈与出栈操作要点：先压后加，先减后弹；而顺序表的插入与删除则需要移动大量元素。

测试代码：
建立一个顺序堆栈，首先依次输入数据元素1, 2, 3,......,10，然后依次出栈堆栈中的数据元素并显示。

#include<stdio.h>
#include<stdlib.h>
#define MaxStackSize 10
#include "SequenceStack.h"
void main(void)
{
    SequenceStack myStack;//声明
    int i, x;
    StackInitialize(&myStack); //初始化
    
    for(i = 0; i < 10; i++)
    {
        StackPush(&myStack, i+1); //压栈  
    }
    StackTop(myStack, &x); //取顶
    printf("当前栈顶数据元素为：%d\n", x);
    while(StackIsNotEmpty(myStack)) //判空
    {
        StackPop(&myStack, &x); //出栈
        printf("%d\n", x);
    }
}

---

分界线

---

链栈：

将头指针的一段作为栈顶指针。
定义：

typedef struct linklist
{
    ElemType data;
    struct linklist *next;
}SingleLinkList;

StackInit 初始化

void StackInit(SingleLinkList **head)
{
    *head = (SingleLinkList *)malloc(sizeof(SingleLinkList));
    if(*head == NULL)
    {
        exit(1);    //异常结束；exit(0)：正常结束 
    }
    (*head)->next = NULL;
}

StackNotEmpty 判空

int StackNotEmpty(SingleLinkList *head)
{
    if(head->next == NULL) return 0;
    else return 1;
}

StackPush 入栈

int StackPush(SingleLinkList *head, ElemType x)
{
    SingleLinkList *p = (SingleLinkList *)malloc(sizeof(SingleLinkList));
    if(p == NULL)
    {
        printf("内存空间不足无法插入！\n");
        return 0;
    }
    p->data = x;
    p->next = head->next;
    head->next = p;
    return 1;
}

StackPop 出栈

int  StackPop(SingleLinkList *head, ElemType *x)
{
    SingleLinkList *p;
    p = head->next;
    if(p == NULL)
    {
        printf("栈空，无法出栈");
        return 0;
    }
    
    *x = p->data;
    head->next = p->next;
    free(p);
    return 1;
}

StackTop 取顶

int StackTop(SingleLinkList *head, ElemType *x)
{
    SingleLinkList *p = head->next;
    if(p == NULL)
    {
        printf("栈已空！");
        return 0;
    }
    *x = p->data;
    return 1;
}

DestroyStack 销毁

void DestroyStack(SingleLinkList **head)
{
    SingleLinkList *p,*q;
    p = *head;
    while(p != NULL)
    {
        q = p;
        p = p->next;
        free(q);
    }
    *head = NULL;
}

总结：
1、链式栈数据的写入与读取只能在栈顶操作，即不需要遍历找对应下标，直接从头结点后插入或删除；
2、其他的操作跟单链表的一蕉样。

测试代码：

#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
typedef int ElemType;
#include "LinkStack.h"
void main(void)
{
    SingleLinkList *head;
    StackInit(&head);
    int i, x;
    for(i = 0; i < 10; i++)
    {
        StackPush(head, i+1);
    }
    StackTop(head, &x);
    printf("%d\n", x);
    while(StackNotEmpty(head))
    {
        StackPop(head, &x);
        printf("%d ", x);
    }
    DestroyStack(&head);    
}