一、棧

棧是一種限定性的線性表，只能在棧頂進(jìn)行插入和刪除操作。先出后進(jìn)的線性表。

二、順序棧

1. 順序棧的結(jié)構(gòu)體設(shè)計

#define MAXSIZE 10//線性表長度的最大值

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

typedef int Status;//狀態(tài)值
typedef int ElemType;//結(jié)點的數(shù)據(jù)類型，視實際情況而定。在此以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");
}

二、鏈?zhǔn)綏?/h4>

1. 鏈?zhǔn)綏５慕Y(jié)構(gòu)體設(shè)計

//鏈?zhǔn)綏＝Y(jié)點
typedef struct StackNode {
    ElemType data;
    struct StackNode *next;
}StackNode;

typedef struct StackNode *LinkStackPtr;

//鏈?zhǔn)綏?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");
}