数据结构_堆栈

线性结构 - 堆栈的顺序存储表示及其操作

结构 SNode - PtrToSNode - Stack

1. 堆栈中的数组，用于存放数据Data
2. 栈顶指针Top,可用于判断是否空或满
3. 栈的最大容量MaxSize

创建

1. 动态申请栈空间Stack
2. 初始化Top指针为-1，及最大容量
3. 动态申请Stack中数组的空间

是否已满

1. 栈顶指针Top是否与数组最大容量-1相等

是否为空

1. 判断Top指针是否为-1

压栈

1. 先判断是已经满了
2. 将元素存放到Stack的数组的最后一个空位上
3. Stack的Top指针加1

弹栈

1. 判断Stack是否为空
2. 将栈顶元素返回，即Stack中数组的最末位,Top
3. 栈顶指针Top下移一位，原来的栈顶元素就无法被访问了，可不删除或覆盖

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

typedef int ElementType;
typedef int Position;
typedef struct SNode *PtrToSNode;
struct SNode{
    // 1. 堆栈中的数组，用于存放数据
    ElementType *Data;
    // 2. 栈顶指针,可用于判断是否空或满
    Position Top;
    // 3. 栈的最大容量
    int MaxSize;
};
typedef PtrToSNode Stack;

// 创建
Stack CreateStack(int MaxSize){
    Stack stack;
    // 1.动态申请栈空间Stack
    stack = (Stack)malloc(sizeof(struct SNode));
    // 2. 初始化Top指针为-1，及最大容量
    stack->MaxSize = MaxSize;
    stack->Top = -1;
    // 3. 动态申请Stack中数组的空间
    stack->Data = (ElementType *)malloc(sizeof(ElementType) * MaxSize);
    return stack;
}

// 是否已满
bool isFull(Stack stack){
    // 栈顶指针Top是否与数组最大容量-1相等
    bool result = stack->Top == stack->MaxSize -1;
    return result;
}

// 是否为空
bool isEmpty(Stack stack) {
    // 判断Top指针是否为-1
    return stack->Top == -1;
}

// 压栈
void Push(Stack stack, ElementType item){
    if (stack == NULL) {
        return;
    }
    // 1.先判断是已经满了
    if(stack->Top == stack->MaxSize -1){
        printf("stack is full");
        return;
    }
    // 2. 将元素存放到Stack的数组的最后一个空位上
    // 3. Stack的Top指针加1
    stack->Data[++(stack->Top)] = item;
}

// 弹栈
ElementType Pop(Stack stack) {
    if (stack == NULL) {
        return -1;
    }
    // 1、判断Stack是否为空
    if (stack->Top == -1) {
        return -1;
    }
    // 2. 将栈顶元素返回，即Stack中数组的最末位,Top
    // 3. 栈顶指针Top下移一位，原来的栈顶元素就无法被访问了，可不删除或覆盖
    return stack->Data[(stack->Top)--];
}

线性结构 - 堆栈的链式存储表示及其操作

结构 SNode - PtrToSNode - Stack

1. 结点的数据Data
2. 下一个结点Next

创建

1. 动态申请Stack空间，并初始化下一个结点Next为NULL

判断是否为空

1. 判断头结点的下一个结点是否为NULL

压栈

1. 动态申请新结点的空间，创建新结点node
2. 将新值item赋值给新结点node
3. 新结点的下一个结点指向栈的头结点下一个结点（第一个结点）
4. 头结点的下一个结点(第一个结点)为新结点node，链表头插入头删除

弹栈

1. 判断栈是否为空
2. 用临时结点firstItem暂存第一个结点，value暂存第一个结点的值
3. 头结点的下一个结点指向第一个结点的下一个结点(第二个结点)，删除原来的第一个结点
4. 释放原来的第一个结点firstItem

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

typedef int ElementType;
typedef struct SNode *PtrToSNode;
typedef PtrToSNode Stack;

struct SNode{
    // 1.结点的数据Data
    ElementType Data;
    // 2.下一个结点Next
    PtrToSNode Next;
};

// 创建
Stack CreateStack(){
    Stack stack;
    // 1.动态申请Stack空间，并初始化下一个结点Next为NULL
    stack = (Stack)malloc(sizeof(struct SNode));
    stack->Next = NULL;
    return stack;
}

// 判断栈是否为空
bool isEmepty(Stack stack){
    // 判断头结点的下一个结点是否为NULL
    return stack->Next == NULL;
}

// 压栈
void Push(Stack stack, ElementType item){
    if(stack == NULL){
        return;
    }
    PtrToSNode node;
    // 1.动态申请新结点的空间，创建新结点node
    node = (PtrToSNode)malloc(sizeof(struct SNode));
    // 2.将新值item赋值给新结点node
    node->Data = item;
    // 3.新结点的下一个结点指向栈的头结点下一个结点（第一个结点）
    node->Next = stack->Next;
    // 4.头结点的下一个结点(第一个结点)为新结点node，链表头插入头删除
    stack->Next = node;
}

// 弹栈
ElementType Pop(Stack stack){
    // 1.判断栈是否为空
    if(isEmepty(stack)){
        printf("stack is empty");
        return -1;
    }
    PtrToSNode firstItem;
    ElementType value;
    // 2.用临时结点firstItem暂存第一个结点，value暂存第一个结点的值
    firstItem = stack->Next;
    value = firstItem->Data;
    // 3. 头结点的下一个结点指向第一个结点的下一个结点(第二个结点)，删除原来的第一个结点
    stack->Next = firstItem->Next;
    // 4. 释放原来的第一个结点firstItem
    free(firstItem);
    return value;
}