基于顺序存储/链式存储设计栈结构

基于顺序存储/链式存储设计栈结构

栈结构示意图.jpg

栈限定性数据结构，先进后出。

顺序存储栈

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

#define MAXSIZE 100
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

typedef int SElemType;
typedef int Status;

//数据结构定义
typedef struct {
    SElemType data[MAXSIZE];
    int top;
}SqStack;

//顺序栈初始化
Status InitStack(SqStack *stack) {
    stack->top = -1;
    return OK;
}

//清空栈
Status CleanStack(SqStack *stack) {
    stack->top = -1;
    return OK;
}

//判断栈空
Status IsStackEmpty(SqStack stack) {
    if (stack.top == -1) {
        return TRUE;
    }
    return FALSE;
}

//栈长度
int StackLength(SqStack stack) {
    return stack.top + 1;
}

//获取栈顶元素
Status getTop(SqStack stack, SElemType *e) {
    if (-1 == stack.top) {
        return ERROR;
    }
    *e = stack.data[stack.top];
    return OK;
}

//入栈
Status PushData(SqStack *stack, SElemType e) {
    if (MAXSIZE - 1 == stack->top) {
        return ERROR;
    }
    stack->top++;
    stack->data[stack->top] = e;
    return OK;
}

//出栈
Status PopData(SqStack *stack, SElemType *e) {
    if (-1 == stack->top) {
        return ERROR;
    }
    *e = stack->data[stack->top];
    stack->top--;
    return OK;
}

//打印栈
Status PrintStack(SqStack stack) {
    if (-1 == stack.top) {
        printf("空栈\n");
    }
    printf("栈的所有元素：\n");
    int i = 0;
    while (i <= stack.top ) {
        printf("%d\n",stack.data[i]);
        i++;
    }
     printf("\n");
    return OK;
}

int main(int argc, const char * argv[]) {
    SqStack stack;
    int e;
    if (InitStack(&stack) == OK) {
        for (int i = 0; i < 10; i++) {
            PushData(&stack, i);
        }
        PrintStack(stack);
    }
    PopData(&stack, &e);
    PrintStack(stack);
    return 0;
}

链式存储栈

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

#define MAXSIZE 100
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

typedef int SElemType;
typedef int Status;

typedef struct StackNode {
    SElemType data;
    struct StackNode * next;
}StackNode;

typedef StackNode * StackNodePtr;

typedef struct {
    StackNodePtr top;
    int count;
}LinkStack;

//构建一个空栈
Status InitLinkStack(LinkStack *stack) {
    stack->top = (StackNodePtr)malloc(sizeof(StackNode));
    if (NULL == stack->top) {
        return ERROR;
    }
    stack->top = NULL;
    stack->count = 0;
    return OK;
}


//清空栈
Status CleanLinkStack(LinkStack *stack) {
    StackNodePtr p,q;
    p = stack->top;
    while (p) {
        q = p->next;
        free(p);
        p = q;
    }
    stack->count = 0;
    return OK;
}

//判断是否空栈
Status ISLinkStackEmpty(LinkStack stack) {
    if (stack.count == 0) {
        return TRUE;
    }
    return FALSE;
}

//判断栈长度
int StackLength(LinkStack stack) {
    return stack.count;
}

//获取栈顶元素
Status getTop(LinkStack stack, SElemType *e) {
    if (NULL == stack.top) {
        return ERROR;
    }
    *e = stack.top->data;
    return OK;
}

//入栈
Status PushData(LinkStack *stack, SElemType e) {
    StackNodePtr node = (StackNodePtr)malloc(sizeof(StackNode));
    
    node->data = e;
    node->next = stack->top;
    stack->top = node;
    stack->count++;
    return OK;
}


//出栈
Status PopData(LinkStack *stack, SElemType *e) {
    if (stack->count == 0) {
        return ERROR;
    }
    StackNodePtr top = stack->top;
    *e = top->data;
    stack->top = top->next;
    free(top);
    return OK;
}

//打印
Status PrintLinkStack(LinkStack stack) {
    StackNodePtr p = stack.top;
    printf("链式栈所有元素:\n");
    while (p) {
        printf("%d\n",p->data);
        p = p->next;
    }
    printf("\n");
    return OK;
}


int main(int argc, const char * argv[]) {
    LinkStack stack;
    InitLinkStack(&stack);
    for (int i = 0; i < 10; i++) {
        PushData(&stack, i);
    }
    PrintLinkStack(stack);
    SElemType e;
    PopData(&stack, &e);
    PrintLinkStack(stack);
    return 0;
}