C language stack representation and implementation examples

1. Basic concepts:

The C language A stack is a linear table that is limited to insert and delete operations at the end of a table.
As a common data structure in C language, stack is a special linear table that can only be inserted and deleted at one end. It stores data according to the principle of "first in, last out". The data that comes in first is pushed to the bottom of the stack. The last data is at the top of the stack. Stack has memory function, the stack insert and delete operations, do not need to change the stack bottom pointer.

The stack is a special linear table that allows insert and delete operations at the same end. One end of the stack that allows inserts and deletions is called the top and the other end is called the bottom. The bottom of the stack is fixed, while the top of the stack is floating. A stack with zero elements is called an empty stack. Inserts are generally called pushes, and deletions are called pops. The stack is also called last in first out.

In a computer system, the stack is a dynamic memory area with the above attributes. The program can push data onto the stack or pop it off the top of the stack. In the i386 machine, the top of the stack is located by a register called esp. The operation of pressing the stack makes the address of the top of the stack decrease, while the operation of popping up makes the address of the top of the stack increase.

Stack plays an important role in the running of the program. Most importantly, the stack holds the maintenance information needed for a function call, which is often referred to as a stack frame or an active record. Stack frames generally contain the following information:

(1) return address and parameters of the function
(2) temporary variables: including non-static local variables of functions and other temporary variables automatically generated by the compiler

2. Implementation code:

#define STACK_INIT_SIZE 10 
 #define STACKINCREMENT 2 
 typedef struct SqStack
 {
  SElemType *base; 
  SElemType *top; 
  int stacksize; 
 }SqStack; 
Status InitStack(SqStack *S)
 { 
  (*S).base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
  if(!(*S).base)
   exit(OVERFLOW); 
  (*S).top=(*S).base;
  (*S).stacksize=STACK_INIT_SIZE;
  return OK;
 }
 Status DestroyStack(SqStack *S)
 { 
  free((*S).base);
  (*S).base=NULL;
  (*S).top=NULL;
  (*S).stacksize=0;
  return OK;
 }
 Status ClearStack(SqStack *S)
 { 
  (*S).top=(*S).base;
  return OK;
 }
 Status StackEmpty(SqStack S)
 { 
  if(S.top==S.base)
   return TRUE;
  else
   return FALSE;
 }
 int StackLength(SqStack S)
 { 
  return S.top-S.base;
 }
 Status GetTop(SqStack S,SElemType *e)
 { 
  if(S.top>S.base)
  {
   *e=*(S.top-1);
   return OK;
  }
  else
   return ERROR;
 }
 Status Push(SqStack *S,SElemType e)
 { 
  if((*S).top-(*S).base>=(*S).stacksize) 
  {
   (*S).base=(SElemType *)realloc((*S).base,((*S).stacksize+STACKINCREMENT)*sizeof(SElemType));
   if(!(*S).base)
    exit(OVERFLOW); 
   (*S).top=(*S).base+(*S).stacksize;
   (*S).stacksize+=STACKINCREMENT;
  }
  *((*S).top)++=e;
  return OK;
 }
 Status Pop(SqStack *S,SElemType *e)
 { 
  if((*S).top==(*S).base)
   return ERROR;
  *e=*--(*S).top;
  return OK;
 }
 Status StackTraverse(SqStack S,Status(*visit)(SElemType))
 { 
  
  while(S.top>S.base)
   visit(*S.base++);
  printf("n");
  return OK;
 }
 #include"c1.h"
 typedef int SElemType; 
 #include"c3-1.h"
 #include"bo3-1.c"
 Status visit(SElemType c)
 {
  printf("%d ",c);
  return OK;
 }
 void main()
 {
  int j;
  SqStack s;
  SElemType e;
  if(InitStack(&s)==OK)
   for(j=1;j<=12;j++)
    Push(&s,j);
  printf(" The elements in the stack are in order: ");
  StackTraverse(s,visit);
  Pop(&s,&e);
  printf(" The top element of the stack pops up  e=%dn",e);
  printf(" Whether the stack is empty: %d(1: empty  0: no )n",StackEmpty(s));
  GetTop(s,&e);
  printf(" The stack elements  e=%d  The length of the stack is zero %dn",e,StackLength(s));
  ClearStack(&s);
  printf(" After clearing the stack, the stack is empty or not: %d(1: empty  0: no )n",StackEmpty(s));
  DestroyStack(&s);
  printf(" After the stack is destroyed, s.top=%u s.base=%u s.stacksize=%dn",s.top,s.base, s.stacksize);
 }