Implementation of stack (C language)

Catalog

The realization of the stack

Definition of stack

Array implementation

Static stack

Dynamic stack

Chain stack

---

The realization of the stack

First of all, let's think about a question , What is stack? ？

 Stack is a kind of data structure , Stack is very common in our daily coding , Many people's contact with the stack may be limited to   Recursion uses the stack   and  StackOverflowException, A stack is a last in, first out data structure ( Imagine the cell of the biochemical pyramid and the dog hole of the biochemical arena ).

Definition of stack

Stack （stack） Also known as the stack , It is a kind of Limited operation The linear table . A linear table limited to insert and delete operations only at the end of the table . This end is called the top of the stack , relatively , Call the other end the bottom of the stack . Inserting a new element into a stack is also called a push 、 Push or push , It's putting a new element on top of the top of the stack , Make it the new top element ; Removing an element from a stack is also called making a stack or backing a stack , It removes the top element of the stack , Make its adjacent elements the new top of the stack

 

Stacks are widely used , For example, your program execution view call stack 、 There are four addition and subtraction operations in computer 、 The non recursive form of the algorithm 、 Bracket matching and so on . So stack is also a data structure that must be mastered . The simplest we've all experienced , You take a book and fold it up and down , It's a last in, first out process , You can think of it as a stack . So let's talk about Array There are two forms of stack .

Array implementation

Static stack

This method is generally not recommended , Because when space is not enough , It will be a little troublesome to increase capacity , Unpractical .

typedef struct Stack
{ 
    STDataType _a[];  //STDataType  by int Macro definition , Of course, you can also define it as other types , The macro definition is for convenience when changing stack types 
    int _top; //  To the top of the stack 
    int _capacity; //  Capacity 
}Stack;

Dynamic stack

Compared with static stack , When the dynamic stack space is insufficient, you can use it directly realloc Dynamic capacity , However, dynamic expansion will consume a certain degree , We will directly double the capacity , When it is not used up, it will cause a certain degree of space waste .

typedef struct Stack
{ 
    STDataType* _a;// A pointer to an open continuous space 
    int _top; //  To the top of the stack 
    int _capacity; //  Capacity 
}Stack;

The operation to be implemented by the stack

//  Initialization stack 
void StackInit(Stack* ps);
//  Push 
void StackPush(Stack* ps, STDataType data);
//  Out of the stack 
void StackPop(Stack* ps);
//  Get stack top element 
STDataType StackTop(Stack* ps);
//  Get the number of valid elements in the stack 
int StackSize(Stack* ps);
//  Check if the stack is empty , If NULL, return non-zero result , If not empty return 0
bool StackEmpty(Stack* ps);
//  Destroy the stack 
void StackDestroy(Stack* ps);

Initialization of stack

void StackInit(Stack* ps)
{
    ps->_a = NULL; // Pointer to null during initialization , There is no open space at this time 
    // I can put top The assignment is 0, It can also be assigned to -1.
    ps->_top = -1;  // The assignment is 0 It means top Is the subscript of the next position of the stack top element , The assignment is -1 when top Is the subscript of the top element of the stack 
    ps->_capacity = 0; // Stack capacity 
}

Push

void StackPush(Stack* ps, STDataType data)
{
    assert(ps);
    // Consider whether to increase capacity 
    // When top by 0 The judgment condition is 
    //if(ps->top==ps->_capacity)
    if (ps->_top+1 == ps->_capacity)// Enter when the stack is full 
    {
        // Judge whether the capacity of the current stack is 0, by 0 Open up 4 Space , Not for 0 Double the capacity 
        int newcapacity = ps->_capacity == 0 ? 4 : ps->_capacity * 2;
        STDataType* tmp = realloc(ps->_a, sizeof(STDataType) * newcapacity);
        if (tmp == NULL)
        {
            exit(-1);
        }
        ps->_a = tmp;
        ps->_capacity = newcapacity;
    }
    // Expansion completed , Or no expansion , Start inserting 
    ps->_top++;
    ps->_a[ps->_top] = data;
    // When top by 0 Insert operation 
    //ps->_a[ps->_top] = data;
    //ps->_top++;
}

Out of the stack

void StackPop(Stack* ps)
{
    assert(ps);
    // Determine whether it is null 
    assert(!StackEmpty(ps));// Violent judgment 
    //if (top==-1)// Judge gently 
    //{
    //  printf(" The stack is empty ！\n");
    //  exit(-1); // Throw out the exception 
    //}
    ps->_top--;
}

 

Take the top element of the stack

STDataType StackTop(Stack* ps)
{
    assert(ps);
    // Determine whether it is null , Throw an exception when it is empty .
    assert(!StackEmpty(ps));
    //if (!StackEmpty(ps)) {
    //  printf(" The stack is empty. ！\n");
    //  exit(-1);
    //}
    return ps->_a[ps->_top]; // Back to top of stack element 
}

Determine how many valid data are in the stack

// Get the number of effective elements in the stack .
int StackSize(Stack* ps)
{
    assert(ps);
    return ps->_top+1; 
}

Judge whether the stack is empty

bool StackEmpty(Stack* ps)
{
    assert(ps);
    return ps->_top == -1;  //ps->_top by -1 return true, Otherwise return to false.
​
}

Destroy the stack

Destroying the stack is an essential step , If not destroyed, it will cause memory leakage

void StackDestroy(Stack* ps)
{
    assert(ps);
    free(ps->_a);
    ps->_a = NULL;
    ps->_top = -1;
    ps->_capacity = 0;
​
}

Chain stack

Finally, I will introduce the chain stack , Not here. If you are interested, you can do it yourself .

The chain stack is the same as the list , It is also used to link various data blocks through pointers

The design chain stack is best designed as a two-way linked list , Otherwise, when you design to use the tail as the top of the stack, it will be inefficient .

When using the head as the top of the stack , Plug removal , It can be designed as a single linked list .