数据结构之栈

一、栈

栈是一种限定性的线性表，只能在栈顶进行插入和删除操作。先出后进的线性表。

二、顺序栈

1. 顺序栈的结构体设计

#define MAXSIZE 10//线性表长度的最大值

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

typedef int Status;//状态值
typedef int ElemType;//结点的数据类型，视实际情况而定。在此以int为例。

typedef struct {
    ElemType data[MAXSIZE];
    int top;
}SqStack;

2.初始化一个空栈

Status InitStack(SqStack *S) {
    S-> top = -1;    
    return OK;
}

3.清空栈

Status ClearStack(SqStack *S) {
    S->top = -1;    
    return OK;
}

4.栈的长度

栈的长度为：S.top+1

5.获取栈顶

if(S.top == -1) return ERROR;

*e = S.data[S.top];
return OK;

6.入栈

Status Push(SqStack *S, ElemType e) {
    //栈满，不能压栈
    if (S->top == MAXSIZE -1) return ERROR;
    S->top++;
    S->data[S->top] = e;
    
    return OK;
}

7.出栈

Status Pop(SqStack *S, ElemType *e) {
    //空栈，不能出栈
    if (S->top == -1) return ERROR;
    *e = S->data[S->top];
    S->top--;
    
    return OK;
}

8.遍历

void TraverseStack(SqStack S) {
    
    for (int i = 0; i<=S.top; i++) {
        printf("栈元素：%d ",S.data[S.top]);
    }
    printf("\n");
}

二、链式栈

1. 链式栈的结构体设计

//链式栈结点
typedef struct StackNode {
    ElemType data;
    struct StackNode *next;
}StackNode;

typedef struct StackNode *LinkStackPtr;

//链式栈
typedef struct {
    LinkStackPtr top;
    int count;
}LinkStack;

2.初始化一个空栈

Status InitStack(LinkStack *S) {
    
    S->count = 0;
    S->top = NULL;
    
    return OK;
}

3.清空栈

Status ClearLinkStack(LinkStack *S) {
    
    LinkStackPtr p = S->top;
    LinkStackPtr temp;

    while (p) {
        temp = p;
        p = p->next;
        
        free(temp);
    }
    S->count = 0;
    
    return OK;
}

4.栈的长度

栈的长度为：S.count

5.获取栈顶

S.top->data

6.入栈

Status PushLinkStack(LinkStack *S, ElemType e) {
    
    LinkStackPtr ptr = (LinkStackPtr)malloc(sizeof(StackNode));
    ptr->data = e;
    ptr->next = NULL;
    
    ptr->next = S->top->next;
    S->top->next = ptr;
    
    S->count++;
    
    return OK;
}

7.出栈

Status PopLinkStack(LinkStack *S, ElemType *e) {
    //空栈不能出栈
    if (S->count == 0) {
        return ERROR;
    }
    
    *e = S->top->data;
    
    LinkStackPtr p = S->top;
    S->top = p->next;
    
    free(p);
    
    S->count--;
    
    return OK;
}

8.遍历

void TraverseLinkStack(LinkStack S) {
    
    LinkStackPtr p = S.top;
   
    while (p) {
        printf("%d ",p->data);
        p = p->next;
    }
    printf("\n");
}