1. Stack definition

A stack is a linear table that only inserts and deletes at the end of the table. The end of the table is called the top of the stack, and the head of the table is called the bottom of the stack. The empty table without elements is called the empty stack, and the stack modification principle is last in first out.

2. Store the implementation stack sequentially

The operation is relatively simple, because the storage space is limited during initialization, so the space is limited.

2.1 structure

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 20 /* Initial allocation of storage space */typedef int Status; typedef int SElemType; / / struct {SElemType data[MAXSIZE]; / / struct {SElemType data[MAXSIZE]; int top; /* for top pointer */}SqStack;Copy the code

2.2 Basic Operations

Status InitStack(SqStack *S){S->top = -1;returnOK; Status ClearStack(SqStack *S){S->top = -1;returnOK; } //3 Check whether the sequence stack is empty; Status StackEmpty(SqStack S){if (S.top == -1){
        return TRUE;
    }else{
        returnFALSE; } //4 return StackLength int StackLength(SqStack S){returnS.top + 1; Status GetTop(SqStack S,SElemType *e){if (S.top == -1){
        return ERROR;
    }else{
        *e = S.data[S.top];
    }
    returnOK; PushData(SqStack *S, SElemType e){if (S->top == MAXSIZE -1) {
        return ERROR;
    }
    S->top ++;
    S->data[S->top] = e;
    returnOK; } //7 remove the top element of the stack and bring back the Status Pop(SqStack *S,SElemType *e){if (S->top == -1) {
        return ERROR;
    }
    *e = S->data[S->top];
    S->top--;
    return OK;
}
int main(int argc, const char * argv[]) {
    SqStack S;
    int e;
    if (InitStack(&S) == OK) {
        for(int j = 1 ; j < 10; j++) { PushData(&S, j); }}printf("The element in the sequential stack is :\n");
    StackTraverse(S);
    Pop(&S, &e);
    printf("Pop-out top element: %d\n",e);
    StackTraverse(S);
    printf("Empty stack :%d\n",StackEmpty(S));
    GetTop(S, &e);
    printf("Top element :%d\n Stack length :%d\n",e,StackLength(S));
    ClearStack(&S);
    printf("Have you cleared stack %d with stack length :%d\n?",StackEmpty(S),StackLength(S));
    return 0;
}
Copy the code

3. Chain structure realization stack

The space size is not fixed, and the scalability is strong

3.1 Structure Definition

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 20 /* Initial allocation of storage space */typedef int Status; typedef int SElemType; /* typepedef struct StackNode {SElemType data; struct StackNode *next; }StackNode,*LinkStackPtr; typedef struct { LinkStackPtr top; int count; }LinkStack;Copy the code

3.2 Common Operations

InitStack(LinkStack *S) {S->top=NULL; S->count=0;returnOK; ClearStack(LinkStack *S){LinkStack PTR p,q; p = S->top;while (p) {
        q = p;
        p = p->next;
        free(q);
    }
    S->count = 0;
    returnOK; } /*3 check whether the stack is empty */ Status StackEmpty(LinkStack S){if (S.count == 0)
        return TRUE;
    else
        returnFALSE; } /*4 return the number of elements of S, that is, the StackLength */ int StackLength(LinkStack S){returnS.count; LinkStack (S,SElemType *e){if (S,SElemType *e){if(S.top == NULL)
        return ERROR;
    else
        *e = S.top->data;
    returnOK; } /*6 insert the element e into the stack S */ Status Push(LinkStack *S, SElemType e){ LinkStackPtr temp = (LinkStackPtr)malloc(sizeof(StackNode)); temp->data = e; temp->next = S->top; S->top = temp; S->count++;returnOK; } /*7 If the stack is not empty, remove the top element of S and return its value with e. ERROR*/ Status Pop(LinkStack *S,SElemType *e){LinkStackPtr p;if (StackEmpty(*S)) {
        return ERROR;
    }
    *e = S->top->data;
    p = S->top;
    S->top= S->top->next;
    free(p);
    S->count--;
    return OK;
}
int main(int argc, const char * argv[]) {
    int j;
    LinkStack s;
    int e;
    if(InitStack(&s)==OK)
        for(j=1; j<=10; j++) Push(&s,j);printf("The elements in the stack are:");
    StackTraverse(s);
    Pop(&s,&e);
    printf("Popup top element e=%d\n",e);
    StackTraverse(s);
    printf("Stack empty no: %d(1: empty 0: no)\n",StackEmpty(s));
    GetTop(s,&e);
    printf("Top element e=%d stack length %d\n",e,StackLength(s));
    ClearStack(&s);
    printf("Empty stack no: %d(1: empty 0: no)\n",StackEmpty(s));
    return 0;
}
Copy the code