A brief analysis of the stack of sequential structure storage

Stack definition: a linear table that is limited to inserts and deletes at the end of a table

Stack features:

1) data that can generally be pushed and pushed at the end of a table

2) last in first out

3) the stack will have the top and bottom of the stack, usually the bottom of the stack is the high address and the top of the stack is the high address, as shown in the following figure

< img border = 0 SRC = "/ / files.jb51.net/file_images/article/201401/201419151956087.jpg" >

Operating systems typically allocate a chunk of memory for stack operations, but this is a bit different from normal operations: for example, to store an array, the address is increased; But in the storage data to the stack, the address is decreasing

Storage structure of the stack:

typedef struct _SQSTACK
{
 SElemType* base;
 SElemType* top;
 int stacksize;
}
SqStack;

Data definition:

//Default storage space size and space growth size
#define STACK_INIT_SIZE 100
#define STACK_INCREMENT 10
//Type definition for storing data
#ifndef INT_TYPE
#define INT_TYPE
#endif // INT_TYPE
#ifdef INT_TYPE
typedef  int  SElemType;
#elif defined FLOAT_TYPE
typedef  float SElemType;
#elif defined STRING_TYPE
typedef  char* SElemType;
#elif defined STRUCT_TYPE
typedef  void* SElemType;
#endif

The operation of the stack involves initializing the stack, destroying the stack, pushing the stack (push), pushing the stack, as well as determining the empty stack, the size of the stack, and emptying the stack, as follows:
Stack initialization:

//Initialize the stack
int InitStack(SqStack *S)
{
 S->base = (SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));
 if (!S->base)
 {
  return -1;
 }
 S->top = S->base;
 S->stacksize = STACK_INIT_SIZE;
 return 0;
}

The stack is just initialized, there is no data in it, then top and base all point to the base address of the allocated space, indicating that the stack is empty
Destruction of the stack:

//Destruction of the stack
int DestroyStack(SqStack *S)
{
 if (S->base)
 {
  free(S->base);
  S->base = NULL;
  S->top = NULL;
  S->stacksize = 0;
 }
 return 0;
}

If the stack exists, the address space is destroyed and the stack size is set to 0
Into the stack:

int Push(SqStack *S, const SElemType data)
{
 assert(S->base != NULL);
 if (S->top - S->base >= STACK_INIT_SIZE)
 {
  S->base = (SElemType*)realloc(S->base, 
   (STACK_INIT_SIZE + STACK_INCREMENT) * sizeof(SElemType));
  if (!S->base)
  {
   return -1;
  }
  S->top = S->base + S->stacksize;
  S->stacksize += STACK_INCREMENT;
 }
 *S->top++ = data;
 return 0;
}

If the stack exists, the address space is destroyed and the stack size is set to 0
Into the stack:
The same code at the page code block index 4

If the size of the stack is greater than the allocated length, reallocate the space and redirect the top of the stack to a new location, then store the data in the location that the top of the stack points to, and the top of the stack +1
The stack:

//Out of the stack
int Pop(SqStack *S, SElemType *data)
{
 assert(S->base != NULL);
 if (S->base == S->top)
 {
  return -1;
 }
 *data = *(--S->top);

 return 0;
}

First place the top of the stack at -1, then get the value of the current position
The following is the auxiliary function, as follows:

//Whether the stack is empty
int IsStackEmpty(const SqStack &S)
{
 return ((S.base == S.top) ? true:false);
}

//I get the length of the stack
int GetStackLength(const SqStack &S)
{
 assert(S.base != NULL);
 return S.stacksize;
}

//Empty stack
int ClearStack(SqStack *S)
{
 assert(S->base != NULL);
 if (S->base != S->top)
 {
  S->top = S->base;
 }
 S->stacksize = 0;
 return 0;
}