[Data structure is not linked to the subject] The most complete data structure information – stack and queue

Hits: 0

[ [Data structure] is not linked to the subject] The most complete data structure information – linear table

Article directory

foreword

Long time no see, this issue is the second issue of the data structure series – [stack and queue] .

stack

1. Definition of stack

[A stack is a linear] list restricted to insert or delete operations only at the end of the list. Therefore, for the stack, the tail end of the table has its special meaning, which is called the top of the stack, and correspondingly, the head end of the table is called the bottom of the stack. The characteristics of the stack are last in, first out, that is, the last element pushed onto the stack will be the first to be popped.

  • A stack is a linear list that restricts insertion and deletion operations to one end of the list
  • One end of the insertion and deletion is called the top of the stack (Top), and the other end is the bottom of the stack (Bottom). When there are no elements in the table, it is called an empty stack.

The stack is also known as the last in first out (Last In First Out) linear table, referred to as the LIFO structure

2. The sequential structure of the stack

# define   STACK_INIT_SIZE 100;      //Initial allocation
  # define   STACKINCREMENT 10;        //Allocation increment
   typedef  struct { 
    ElemType *base;          //Stack bottom pointer base 
   ElemType *top;           //Stack top pointer top 
    int   stacksize;      //Allocated storage space, in elements
  } SqStack;
  SqStack S;             //Define stack S

Explanation:
1) base is called the stack bottom pointer, which always points to the bottom of the stack; when base = NULL, it indicates that the stack structure does not exist.
2) top is called the top pointer of the stack, when the stack is empty: top=base; when the stack is not empty: point to the next position of the top element of the stack; insert a top element of the stack, the pointer top is incremented by 1; delete a top element of the stack, the pointer top Subtract 1.
3) stacksize : The memory capacity that the current stack can use, (in sizeof(ElemType) units).

3. Basic operations implemented on the [sequential stack]

  • initialization

Status InitStack( SqStack &S )
{
    S.base =new SElemType[MAXSIZE];
    if( !S.base )   return OVERFLOW;
    S.top = S.base;
    S.stackSize = MAXSIZE;
    return OK;
}

  • Check if the sequence stack is empty

bool StackEmpty( SqStack S )
{
    if(S.top == S.base) return true;
   else return false;
}

  • Find the length of the sequence stack

int StackLength( SqStack S )
{
    return S.top – S.base;
}

  • clear the sequence stack

Status ClearStack( SqStack S )
{
    if( S.base ) S.top = S.base;
    return OK;
}

  • Destroy the sequence stack

Status DestroyStack( SqStack &S )
{
    if( S.base )
    {
        delete S.base ;
        S.stacksize = 0;
        S.base = S.top = NULL;
    }
  return OK;
}

  • Sequential stack push

Status Push( SqStack &S, SElemType e)  
{
        return ERROR;   
    *S.top++=e;
    return OK;
}
/*
(1) Determine whether the stack is full, if it is full, an error occurs
(2) Element e is pushed to the top of the stack
(3) Add 1 to the top pointer of the stack


*/

  • Sequential stack pop

Status Pop( SqStack &S, SElemType &e)  
{
        return ERROR;   
    e= *--S.top;
    return OK;
}
/*(1) Determine whether the stack is empty, if it is empty, an error occurs
(2) Get the top element e of the stack
(3) The top pointer of the stack is decremented by 1
*/

  • Get the top element of the order stack

Status GetTop( SqStack S, SElemType &e)  
{
    e = *( S.top – 1 );
    return OK;
}
/* Determine if the stack is empty, if it is empty, return an error
Otherwise, get the top element of the stack through the stack top pointer
*/

  1. stack chain structure

typedef  struct StackNode {
      SElemType  data;
      struct StackNode *next;
 } StackNode,  *LinkStack;
LinkStack S;

4. Basic operations implemented on the chain stack

  • Initialization of the chain stack

void InitStack(LinkStack &S )
{
    S=NULL;
}

  • Check if the chain stack is empty

Status StackEmpty(LinkStack S)
{   
    if (S==NULL) return TRUE;
    else return FALSE;
}

  • Chain stack push

Status Push(LinkStack &S , SElemType e)
{
    p= new StackNode;       //Generate a new node p 
    if (!p) exit (OVERFLOW);
        p->data=e; 
    p->next=S; S=p; 
    return OK; 
}

  • Chain stack pop

Status Pop (LinkStack &S,SElemType &e)
{if (S==NULL) return ERROR;
 e = S-> data;  p = S;   S =  S-> next;
 delete p;   return OK;  }

  • Get the top element of the chain stack

SElemType GetTop(LinkStack S)
   {
       if (S==NULL) 
            exit(1);
       else 
            return S–>data;
    }

You may also like...

Leave a Reply

Your email address will not be published.