Data structure sequential stack – C language implementation

Data structure sequential stack – C language implementation

• 1. Code comments
• • 1. Related header files
  • 2. Macro definition content
  • 3. Readability optimization and stack type declaration
  • 4. Related functions
  • • 1)`void InitStack(SqStack *S);`Initialize sequence stack
    • 2)`void DestroyStack(SqStack *S);`Destroy the stack
    • 3)`void ClearStack(SqStack *S);`Clear the stack
    • 4)`Status StackEmpty(SqStack S);`Determine the stack is empty
    • 5)`Status StackFull(SqStack S);`Judge that the stack is full
    • 6)`int StackLength(SqStack S);`Return stack length
    • 7)`SElemType GetStackTop(SqStack S);`Return the top element of the stack
    • 8)`void Push(SqStack *S, SElemType e);`Push the stack
    • 9)`void Pop(SqStack *S, SElemType *e);`pop stack
    • 10)`void StackTraverse(SqStack S, void *visit(SElemType));`Traverse stack elements
• 2. Complete code
• 3. Summary

1. Code comments

1. Related header files

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

malloc.h: malloc() and realloc()

malloc() is used to initialize the stack, and realloc() is used to expand the stack when there is insufficient memory.

stdlib.h
stdio.h:
stdbool.h: bool type variable

2. Macro definition content

//Modify according to the specific situation of use
#define SElemType int
#define SElemType_Flag "int"
#define SFormat "%d\t"
#define SPath ""

SElemType: Type of elements in the stack
SElemType_Flag: used for initialization to inform the type of elements in the stack
SFormat "%d\t": Format used for traversing printing/tracing stack running processes/writing files
SPath: used to traverse the elements in the stack and write to the file

#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10

STACK_INIT_SIZE: Initialization stack size
STACKINCREMENT: The size of the expansion each time the stack memory is insufficient.

#define SDisplayFlag 1

DisplayFlag: used for program running tracking

3. Readability optimization and stack type declaration

typedef bool Status;
typedef struct SqStack
{<!-- -->
    SElemType *base;
    SElemType *top;
    int stacksize;
} SqStack;

4. Related functions

1)void InitStack(SqStack *S);Initialize sequence stack

void InitStack(SqStack *S)
{<!-- -->
    S->base = (SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType));
    if (!S->base)
    {<!-- -->
        printf("Sequential stack initialization failed");
        exit(1);
    }
    S->top = S->base;
    S->stacksize = STACK_INIT_SIZE;
    printf("Sequential stack initialization completed\\
");
    printf("The element in the stack is" SElemType_Flag "type\\
");
}

2)void DestroyStack(SqStack *S);Destroy the stack

void DestroyStack(SqStack *S)
{<!-- -->
    free(S->base);
    S->stacksize = 0;
    S->base = S->top = NULL;
}

3)void ClearStack(SqStack *S);Clear the stack

void ClearStack(SqStack *S)
{<!-- -->
    S->top = S->base;
}

4)Status StackEmpty(SqStack S);Judge stack empty

Status StackEmpty(SqStack S)
{<!-- -->
    if (S.top == S.base)
        return true;
    else
        return false;
}

5)Status StackFull(SqStack S);Judge stack full

Status StackFull(SqStack S)
{<!-- -->
    if (S.top - S.base == S.stacksize)
        return true;
    else
        return false;
}

6)int StackLength(SqStack S);Return stack length

int StackLength(SqStack S)
{<!-- -->
    return S.top - S.base;
}

7)SElemType GetStackTop(SqStack S);Return the top element of the stack

SElemType GetStackTop(SqStack S)
{<!-- -->
    if (StackEmpty(S)) // stack is empty
    {<!-- -->
        printf("Error in retrieving the top element of the stack: the sequence stack is empty");
        exit(1);
    }
    else
    {<!-- -->
if (SDisplayFlag)
printf("Top element of stack:" SFormat, *(S.top - 1));
        return *(S.top - 1);
    }
        
}

8)void Push(SqStack *S, SElemType e);Push

Insert element e as the new top element of the stack

void Push(SqStack *S, SElemType e)
{<!-- -->
    if (StackFull(*S)) // stack is full
    {<!-- -->
        S->base = (SElemType *)realloc(S->base, (S->stacksize + STACKINCREMENT) * sizeof(SElemType));
        if (!S->base)
        {<!-- -->
            printf("Sequential stack increasing capacity error");
            exit(1);
        }
        S->top = S->base + S->stacksize;
        S->stacksize + = STACKINCREMENT;
    }
    *S->top + + = e; //=*(S->top)=e;S->top + + ;
    if (SDisplayFlag)
        printf("Push on stack:" SFormat, e);
}

9)void Pop(SqStack *S, SElemType *e);Popping the stack

Delete the top element of S and return its value using e

void Pop(SqStack *S, SElemType *e)
{<!-- -->
    if (StackEmpty(*S)) // stack is empty
    {<!-- -->
        printf("Stack pop error: The sequence stack is empty");
        exit(1);
    }
    else
        *e = *--S->top; //=--S->top;e = *(S->top);
    if (SDisplayFlag)
        printf("Popping stack:" SFormat, *e);
}

10)void StackTraverse(SqStack S, void *visit(SElemType));Traverse stack elements

Call the function visit() on each element of S in sequence from the bottom of the stack to the top of the stack.

void StackTraverse(SqStack S, void visit(SElemType))
{<!-- -->
    if (StackEmpty(S)) // stack is empty
    {<!-- -->
        printf("Stack traversal error: sequential stack is empty");
        exit(1);
    }
    SElemType *temp = S.base;
    printf("There are %d elements in the stack: \\
", StackLength(S));
    while (temp != S.top)
    {<!-- -->
        visit(*temp);
        temp + + ;
    }
    if (SPath == "")
printf("\\
");
else
{<!-- -->
FILE *fp = fopen(SPath, "a");
fprintf(fp,"\\
");
fclose(fp);
}
}
void PrintSElem(SElemType e)
{<!-- -->
    printf(SFormat, e);
}
void FPrintSElem(SElemType e)
{<!-- -->
FILE *fp = fopen(SPath,"a");
fprintf(fp,SFormat,e);
fclose(fp);
}

2. Complete code

/*
Name: SqStack.h
Content: Sequential stack related operations
Created by: dust
Last updated: October 26, 2023 16:04:36
Revise:
#define SElemType
#define SElemType_Flag
#defineFormat
#define Path
*/

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

// Modify according to the specific situation of use
//Data type and printing format in the stack
#ifndef SElemType
#define SElemType int
#endif
#ifndef SElemType_Flag
#define SElemType_Flag "int"
#endif
#ifndef SFormat
#define SFormat "%d\t"
#endif
#ifndef SPath
#define SPath ""
#endif

//Sequence stack size
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10

// Facilitate program running tracking
#define SDisplayFlag 0

#ifndef Status
typedef bool Status;
#endif
typedef struct SqStack
{
    SElemType *base;
    SElemType *top;
    int stacksize;
} SqStack;

void InitStack(SqStack *S)
{<!-- -->
    S->base = (SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType));
    if (!S->base)
    {<!-- -->
        printf("Sequential stack initialization failed");
        exit(1);
    }
    S->top = S->base;
    S->stacksize = STACK_INIT_SIZE;
    printf("Sequential stack initialization completed\\
");
    printf("The element in the stack is" SElemType_Flag "type\\
");
}

void DestroyStack(SqStack *S)
{<!-- -->
    free(S->base);
    S->stacksize = 0;
    S->base = S->top = NULL;
}

void ClearStack(SqStack *S)
{<!-- -->
    S->top = S->base;
}
StatusStackEmpty(SqStackS)
{
    if (S.top == S.base)
        return true;
    else
        return false;
}
StatusStackFull(SqStackS)
{
    if (S.top - S.base == S.stacksize)
        return true;
    else
        return false;
}
int StackLength(SqStack S)
{<!-- -->
    return S.top - S.base;
}
SElemType GetStackTop(SqStack S)
{
    if (StackEmpty(S)) // stack is empty
    {
        printf("Error in retrieving the top element of the stack: the sequence stack is empty");
        exit(1);
    }
    else
    {
        if (SDisplayFlag)
            printf("Top element of stack:" SFormat, *(S.top - 1));
        return *(S.top - 1);
    }
}
void Push(SqStack *S, SElemType e)
{<!-- -->
    if (StackFull(*S)) // stack is full
    {<!-- -->
        S->base = (SElemType *)realloc(S->base, (S->stacksize + STACKINCREMENT) * sizeof(SElemType));
        if (!S->base)
        {<!-- -->
            printf("Sequential stack increasing capacity error");
            exit(1);
        }
        S->top = S->base + S->stacksize;
        S->stacksize + = STACKINCREMENT;
    }
    *S->top + + = e; //=*(S->top)=e;S->top + + ;
    if (SDisplayFlag)
        printf("Push on stack:" SFormat, e);
}
void Pop(SqStack *S, SElemType *e)
{<!-- -->
    if (StackEmpty(*S)) // stack is empty
    {<!-- -->
        printf("Stack pop error: The sequence stack is empty");
        exit(1);
    }
    else
        *e = *--S->top; //=--S->top;e = *(S->top);
    if (SDisplayFlag)
        printf("Popping stack:" SFormat, *e);
}
void StackTraverse(SqStack S, void visit(SElemType))
{
    if (StackEmpty(S)) // stack is empty
    {
        printf("Stack traversal error: sequential stack is empty");
        exit(1);
    }
    SElemType *temp = S.base;
    printf("There are %d elements in the stack: \\
", StackLength(S));
    while (temp != S.top)
    {
        visit(*temp);
        temp + + ;
    }
    if (SPath == "")
        printf("\\
");
    else
    {
        FILE *fp = fopen(SPath, "a");
        fprintf(fp, "\\
");
        fclose(fp);
    }
}
void PrintSElem(SElemType e)
{
    printf(SFormat, e);
}
void FPrintSElem(SElemType e)
{
    FILE *fp = fopen(SPath, "a");
    fprintf(fp, SFormat, e);
    fclose(fp);
}

3. Summary

During the learning process, the sequence stack related operations of hand tapping are convenient for subsequent lazy use. If you find any bugs, please comment and correct them.