[Data structure] Sequential stack and chain stack (detailed explanation with diagram)

Article directory

  • 1. What is a stack?
    • 1.1 Purpose of stack
  • 2. Stack structure and basic operations
  • 3. Implementation details of the stack
    • 3.1 Sequential stack
      • 3.1.1 Stack initialization
      • 3.1.2 Pushing elements onto the stack
      • 3.1.3 Pop elements from the stack
      • 3.1.4 Get the top element of the stack
      • 3.1.5 Determine whether the stack is empty
      • 3.1.6 Get the number of elements in the stack
      • 3.1.7 Get the number of elements in the stack
    • 3.2 Chain stack
      • 3.2.1 Initialization stack
      • 3.2.2 Destroy the stack
      • 3.2.3 Create new nodes
      • 3.2.3 Push elements onto the stack
      • 3.2.4 Pop the top element of the stack
      • 3.2.5 Get the value of the top element of the stack
      • 3.2.6 Determine whether the stack is empty
      • 3.2.7 Get stack size
  • Summarize

In computer science, a stack is a basic data structure used to store and manage data. It is characterized by the Last-In-First-Out (LIFO) sequence. In this article, we introduce the concepts, usage, basic operations, and implementation details.

1. What is a stack?

A stack is a linear data structure whose elements are inserted and deleted in a specific order. The insertion operation on the stack is called push, and the deletion operation is called pop. The stack can be viewed as a linear list with restricted access. Insertion and deletion operations can only be performed at one end of the list, called the top, and the other end is called the bottom.

1.1 Purpose of stack

Stacks have a wide range of applications in computer science. Here are some common stack uses:

  1. Function calls: The computer uses the stack to keep track of function calls and returns. When a function is called, its local variables and return address and other information are pushed onto the stack. When the function execution ends, this information is popped off the stack.
  2. Expression evaluation: The stack can be used to parse and evaluate expressions, including converting infix expressions to postfix expressions and calculating the value of postfix expressions.
  3. Memory management: The stack plays an important role in memory management and is used to manage function calls and memory allocation of local variables.
  4. Browser history: The stack can be used to implement the browser’s history function. When the user browses the web, each visited URL is pushed into the stack, and the user can access the previous web pages in sequence through the back button.
  5. Undo operation: The stack can be used to implement undo operations. The state of each operation is pushed into the stack, and the user can gradually restore to the previous state through the undo operation.

2. Stack structure and basic operations

Two structures of stack

1. Sequential storage of stack (array implementation):

  • When implementing a stack through an array, a pointer is usually needed to mark the top position of the stack. The stack insertion operation (push) is to add elements to the array [top + 1] position, and then move the top pointer of the stack top + + . The deletion operation (pop) is to delete the element from the [top] position of the array, and then move the top pointer of the stack top–.

  • The stack implemented by the array is very efficient in accessing elements because they can be accessed directly through subscripts. But its disadvantage is that the capacity is fixed, and insertion and deletion operations may require moving a large number of elements.

  • When using arrays to implement stacks, you need to pay attention to stack overflow issues. That is, when the stack space is full, continuing to push into the stack will lead to stack overflow. 

typedef int STDatatype;
typedef struct Stack
{<!-- -->
STDatatype* a;
int capacity;
int top; //Initially 0, indicating the next position subscript at the top of the stack
}ST;

2. Linked storage structure (linked list implementation):

  • When implementing a stack through a linked list,each node contains a data element and a pointer to the next node. The top pointer on the stack points to the head of the linked list.

  • The stack implemented by the linked list does not need to specify the maximum capacity in advance. The efficiency of inserting and deleting elements is relatively high because there is no need to move elements. However, the efficiency of accessing the element at the specified position is lower than that of the array implementation.

  • The stack implemented by the linked list does not need to specify the maximum capacity in advance, and the efficiency of inserting and deleting elements is relatively high because there is no need to move elements. However, accessing elements at specified positions is less efficient than array implementation.

typedef int STDataType;
typedef struct StackNode
{<!-- -->
struct StackNode* next; // pointer to the next node
STDataType data; // Data stored in the node
} STNode;

typedef struct Stack
{<!-- -->
STNode* top; // stack top pointer
} ST;

The stack supports the following basic operations:

  1. Push: Insert an element onto the top of the stack.
  2. Pop: Remove an element from the top of the stack and return the deleted element.
  3. Top element of the stack (top): Returns the element at the top of the stack, but does not modify the stack.
  4. Empty test (isEmpty): Check whether the stack is empty, return true if it is empty, otherwise return false.
  5. Full judgment (isFull): Check whether the stack is full, if it is full, return true, otherwise return false.

3. Stack implementation details

3.1 Sequential stack

3.1.1 Stack initialization

Used to initialize the stack, empty the array members of the stack, the top index of the stack is 0, and the stack capacity is 0. Then dynamically apply for a memory space of size 4 as the stack array. If the application fails, an error message will be output and the program will exit.

void StackInit(ST* ps)
{<!-- -->
assert(ps); // Assert: ps is not NULL

//Initialize stack data members
ps->a = NULL; // The array member of the stack is empty
ps->top = 0; // The top index of the stack is 0
ps->capacity = 0; // The capacity of the stack is 0

//Reallocate space, capacity is 4
ps->a = (STDatatype*)malloc(sizeof(STDatatype)*4);
if (ps->a == NULL) // If allocation fails, give an error message and exit the program
{<!-- -->
perror("malloc fail");
exit(-1);
}

//Update stack data members
ps->top = 0; // The top index of the stack is 0
ps->capacity = 4; // The stack capacity is 4
}

3.1.2 Pushing elements onto the stack

Push element x onto the stack. If the stack is full (that is, the number of elements in the stack is equal to the capacity of the stack), a memory space twice the original size is reallocated and the original data is copied in. Then put the new element on the top of the stack (add one to the top index of the stack) and update the top index of the stack.

void StackPush(ST* ps, STDatatype x)
{<!-- -->
assert(ps); // Assert: ps is not NULL

// If the stack is full, a larger array space needs to be reallocated
if (ps->top == ps->capacity)
{<!-- -->
//Reallocate space and copy the original data into it
STDatatype* tmp = (STDatatype*)realloc(ps->a, ps->capacity * 2 * sizeof(STDatatype));
if (tmp == NULL) // If allocation fails, give an error message and exit the program
{<!-- -->
perror("realloc fail");
exit(-1);
}

// After the space is successfully reallocated, update the stack data members
ps->a = tmp;
ps->capacity *= 2;
}

// Put the new element on the top of the stack and update the index on the top of the stack
ps->a[ps->top] = x;
ps->top + + ;
}

3.1.3 Pop elements from the stack

Pop the top element from the stack. If the stack is empty (the number of elements in the stack is 0), no operation is performed. Otherwise, decrement the top index of the stack by one, and pop the top element from the stack.

void StackPop(ST* ps)
{<!-- -->
assert(ps); // Assert: ps is not NULL
assert(!StackEmpty(ps)); // Assert: the stack is not empty

ps->top--; // Decrementing the top index by one is equivalent to popping the top element off the stack
}

3.1.4 Get the top element of the stack

Get the value of the top element of the stack. If the stack is empty (the number of elements in the stack is 0), no operation is performed. Otherwise, return the value of the top element of the stack (that is, the array element corresponding to the top index minus one)

STDatatype StackTop(ST* ps)
{<!-- -->
assert(ps); // Assert: ps is not NULL
assert(!StackEmpty(ps)); // Assert: the stack is not empty

return ps->a[ps->top - 1]; // Return the top element of the stack
}

3.1.5 Determine whether the stack is empty

bool StackEmpty(ST* ps)
{<!-- -->
assert(ps); // Assert: ps is not NULL

// If the top index of the stack is 0, it means the stack is empty, otherwise it is not empty
return ps->top == 0;
}

3.1.6 Get the number of elements in the stack

int StackSize(ST* ps)
{<!-- -->
assert(ps); // Assert: ps is not NULL
return ps->top; // Return the number of elements in the stack, that is, the top index of the stack
}

3.1.7 Get the number of elements in the stack

//Destroy the stack
void StackDestroy(ST* ps)
{<!-- -->
assert(ps); // Assert: ps is not NULL
free(ps->a); // Release the dynamically allocated stack array
ps->a = NULL; // The stack array member is empty
ps->top = ps->capacity = 0; // The top index of the stack and the capacity of the stack are both 0
}

3.2 Chain Stack

The stack is a last-in-first-out (LIFO) data structure. We can think of it as a container. Insertion and deletion operations can be performed on the top of the stack, and only the elements on the top of the stack can be accessed.

typedef int STDataType;

typedef struct StackNode
{<!-- -->
    struct StackNode* next; // pointer to the next node
    STDataType data; // Data stored in the node
} STNode;

typedef struct Stack
{<!-- -->
    STNode* top; // stack top pointer
} ST;

3.2.1 Initialization stack

void StackInit(ST* ps)
{<!-- -->
    ps->top = NULL; // Initialize the top pointer of the stack to NULL
}

3.2.2 Destroy stack

void StackDestroy(ST* ps)
{<!-- -->
    STNode* cur = ps->top;
    while (cur != NULL)
    {<!-- -->
        STNode* next = cur->next;
        free(cur);
        cur = next;
    }
    ps->top = NULL; // After destroying the stack, set the top pointer to empty
}

3.2.3 Create new nodes

STNode* BuyStackNode(STDataType x)
{<!-- -->
    STNode* pnode = (STNode*)malloc(sizeof(STNode));
    if (pnode == NULL)
    {<!-- -->
        perror("malloc fail");
        exit(-1);
    }
    pnode->data = x; // Initialize node data
    pnode->next = NULL; // Initialize the next pointer of the node to NULL

    return pnode;
}

3.2.3 Push elements onto the stack

First, create a new node to store the element to be pushed; secondly, connect the new node to the back of the current top of the stack; finally, update the top of the stack pointer to the new node pointer, making the new node the new top element of the stack. The entire process requires attention to memory management and various boundary conditions.

void StackPush(ST* ps, STDataType x)
{<!-- -->
    STNode* newnode = BuyStackNode(x); // Create a new node
    newnode->next = ps->top; // Point the next pointer of the new node to the top node of the current stack
    ps->top = newnode; // Update the top pointer of the stack to the new node
}

3.2.4 Pop the top element from the stack

Move the top pointer of the stack forward one bit and update the top pointer of the stack. Before performing a pop operation, you should check whether the link stack is empty to prevent errors or exceptions.

void StackPop(ST* ps)
{<!-- -->
    if (ps->top == NULL)
    {<!-- -->
        return;
    }
    STNode* next = ps->top->next; // Get the next node pointer of the top node of the current stack
    free(ps->top); // Release the current top node of the stack
    ps->top = next; // Update the top pointer of the stack to the next node
}

3.2.5 Get the value of the top element of the stack

STDataType StackTop(ST* ps)
{<!-- -->
    if (ps->top == NULL)
    {<!-- -->
        return -1;
    }
    return ps->top->data; // Return the data value of the top node of the stack
}

3.2.6 Determine whether the stack is empty

bool StackEmpty(ST* ps)
{<!-- -->
    return ps->top == NULL; // Determine whether the stack is empty based on whether the top pointer of the stack is NULL
}

3.2.7 Get the stack size

int StackSize(ST* ps)
{<!-- -->
    int count = 0;
    STNode* pcur = ps->top;
    while (pcur != NULL)
    {<!-- -->
         + + count;
        pcur = pcur->next;
    }
    return count; // Traverse the stack, counting the number of nodes is the size of the stack
}

Summary

The stack is a very important data structure in computer science. It is simple and efficient. We gained an in-depth understanding of the concept, purpose, basic operations, and implementation details of the stack. By mastering the principles and applications of the stack, we can better understand and use it, thereby taking advantage of its advantages when solving practical problems.