A stack is an important linear data structure that operates on the "Last In, First Out" (LIFO) principle. Stacks have a wide range of applications, including expression evaluation, bracket matching, and recursion implementation. This article delves into the concept of stacks and compares two implementation approaches: sequential stacks and linked stacks.

1. Basic Concepts

1.1 Definition

A stack is a collection where insertion and deletion operations occur only at one end, following the LIFO principle. This means the last element added is the first to be removed.

1.2 Basic Operations

• Push: Add a new element to the top of the stack.

• Pop: Remove and return the top element from the stack.

• Peek: View the top element without removing it.

• isEmpty: Check if the stack contains no elements.

• Size: Get the number of elements in the stack.

1.3 Features

• Operation Limitation: Elements can only be added or removed from the stack top.

• Stack Top: The top of the stack is the current accessible and operable element.

• Empty Stack: Operations like popping are not possible on an empty stack.

2. Stack Implementations

2.1 Sequential Stack

When implemented with an array, the stack's top corresponds to the array's last element. Push and pop operations both have a time complexity of $O(1)$.

2.1.1 Basic Structure

typedef struct Stack {
    DataType* arr;  // Array for stack elements
    int top;        // Index of the stack top
    int capacity;   // Capacity of the stack
} ST;

2.1.2 Functional Implementation

1. Initialize the Stack

// Initialize the stack
void StackInit(ST* p) {
    assert(p);
    p->arr = NULL;       // Start with an empty stack
    p->top = p->capacity = 0;  // Set top and capacity to 0
}

2. Destroy the Stack

// Destroy the stack
void StackDestroy(ST* p) {
    assert(p);
    if (p->arr) {
        free(p->arr);    // Free allocated memory
    }
    p->arr = NULL;       // Set pointer to NULL
    p->top = p->capacity = 0;  // Reset top and capacity
}

3. Push Operation

// Check and resize stack if needed
void checkcapacity(ST* p) {
    assert(p);
    if (p->capacity == p->top) {  // Stack is full
        int NewCap = p->capacity == 0 ? 4 : 2 * p->capacity;  // Expand capacity
        DataType* tmp = (DataType*)realloc(p->arr, NewCap * sizeof(DataType));  
        if (!tmp) {
            perror("realloc fail!");
            exit(1);  // Exit if allocation fails
        }
        p->arr = tmp;
        p->capacity = NewCap;
    }
}

// Push an element onto the stack
void StackPush(ST* p, DataType x) {
    assert(p);
    checkcapacity(p);  // Ensure sufficient capacity
    p->arr[p->top++] = x;  // Add element to the stack top
}

4. Check if Stack is Empty

// Check if stack is empty
bool StackEmpty(ST* p) {
    assert(p);
    return p->top == 0;
}

5. Pop Operation

// Pop the top element
void StackPop(ST* p) {
    assert(p);
    assert(!StackEmpty(p));  // Ensure the stack is not empty
    --p->top;  // Decrease the top index
}

6. Get the Top Element

// Retrieve the top element
DataType StackTop(ST* p) {
    assert(p);
    assert(!StackEmpty(p));  // Ensure the stack is not empty
    return p->arr[p->top - 1];
}

7. Get Stack Size

// Get the size of the stack
int StackSize(ST* p) {
    assert(p);
    return p->top;  // Return the number of elements in the stack
}

2.2 Linked Stack

When implementing a stack using a linked list, the head node of the list serves as the stack's top, while the tail node serves as the bottom.
For push operations, an element is inserted at the head of the list using the "head insertion method." For pop operations, the head node is removed from the list.

2.2.1 Basic Structure

// Define node structure
typedef struct Node {
    DataType data;          // Data field
    struct Node* next;      // Pointer field
} Node;

// Define linked stack structure
typedef struct Stack {
    Node* top;              // Pointer to the top of the stack
    int size;               // Number of valid elements in the stack
} ST;

2.2.2 Functional Implementation

1. Initialize the Stack

// Initialize the stack
void StackInit(ST* p) {
    assert(p);
    p->top = NULL;          // Initialize stack top to NULL
    p->size = 0;            // Initialize stack size to 0
}

2. Destroy the Stack

// Destroy the stack
void StackDestroy(ST* p) {
    assert(p);
    Node* pcur = p->top;    // Start from the top of the stack
    Node* temp;

    while (pcur != NULL) {
        temp = pcur;        // Save the current node
        pcur = pcur->next;  // Move to the next node
        free(temp);         // Free the current node's memory
    }

    p->top = NULL;          // Set stack top to NULL
    p->size = 0;            // Reset stack size to 0
}

3. Push Operation

// Create a new node
Node* CreateNode(DataType x) {
    Node* newnode = (Node*)malloc(sizeof(Node));
    if (newnode == NULL) {
        perror("malloc fail");
        exit(1);
    }
    newnode->data = x;
    newnode->next = NULL;
    return newnode;
}

// Push an element onto the stack
void StackPush(ST* p, DataType x) {
    assert(p);
    Node* newnode = CreateNode(x);
    newnode->next = p->top; // Link new node to the current top
    p->top = newnode;       // Update stack top
    ++p->size;
}

4. Check if Stack is Empty

// Check if the stack is empty
bool StackEmpty(ST* p) {
    assert(p);
    return p->top == NULL;  // Stack is empty if top is NULL
}

5. Pop Operation

// Pop an element from the stack
void StackPop(ST* p) {
    assert(p);
    assert(!StackEmpty(p)); // Ensure stack is not empty

    Node* temp = p->top;    // Save the current top node
    p->top = p->top->next;  // Move stack top to the next node
    free(temp);             // Free the memory of the old top
    temp = NULL;
    --p->size;
}

6. Get Top Element

// Get the top element of the stack
DataType StackTop(ST* p) {
    assert(p);
    assert(!StackEmpty(p)); // Ensure stack is not empty
    return p->top->data;    // Return the data of the top node
}

7. Get Stack Size

// Get the size of the stack
int StackSize(ST* p) {
    assert(p);
    return p->size;         // Return the size of the stack
}

2.3 Comparison: Sequential Stack vs. Linked Stack

3.Complete Code Implementation

3.1 Sequential Stack

File: Stack.h
This file includes the function declarations and necessary header file imports.

#pragma once
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>

typedef int DataType;

typedef struct Stack {
    DataType* arr;     // Array implementation
    int top;           // Index of the top element
    int capacity;      // Stack capacity
} ST;

// Function declarations
void StackInit(ST* p);            // Initialize stack
void StackDestroy(ST* p);         // Destroy stack
void StackPush(ST* p, DataType x);// Push element
void StackPop(ST* p);             // Pop element
DataType StackTop(ST* p);         // Get top element
int StackSize(ST* p);             // Get stack size

File: Stack.c
This file contains the definitions of the functions declared in Stack.h.

#define _CRT_SECURE_NO_WARNINGS
#include "Stack.h"

// Initialize stack
void StackInit(ST* p) {
    assert(p);
    p->arr = NULL; 
    p->top = p->capacity = 0; 
}

// Destroy stack
void StackDestroy(ST* p) {
    assert(p);
    if (p->arr) {
        free(p->arr); 
    }
    p->arr = NULL; 
    p->top = p->capacity = 0; 
}

// Check and expand stack capacity
void checkcapacity(ST* p) {
    assert(p);
    if (p->capacity == p->top) {
        int NewCap = p->capacity == 0 ? 4 : 2 * p->capacity; 
        DataType* tmp = (DataType*)realloc(p->arr, NewCap * sizeof(DataType));
        if (tmp == NULL) {
            perror("realloc fail!");
            exit(1);
        }
        p->arr = tmp; 
        p->capacity = NewCap; 
    }
}

// Push operation
void StackPush(ST* p, DataType x) {
    assert(p);
    checkcapacity(p); 
    p->arr[p->top++] = x; 
}

// Check if stack is empty
bool StackEmpty(ST* p) {
    assert(p);
    return p->top == 0; 
}

// Pop operation
void StackPop(ST* p) {
    assert(p);
    assert(!StackEmpty(p)); 
    --p->top; 
}

// Get the top element
DataType StackTop(ST* p) {
    assert(p);
    assert(!StackEmpty(p)); 
    return p->arr[p->top - 1]; 
}

// Get stack size
int StackSize(ST* p) {
    assert(p);
    return p->top; 
}

File: main.c
This file is used to test the stack implementation.

#define _CRT_SECURE_NO_WARNINGS
#include "Stack.h"

void test01() {
    ST st;
    StackInit(&st);
    StackPush(&st, 1);
    StackPush(&st, 3);
    StackPush(&st, 5);
    StackPush(&st, 7);

    while (!StackEmpty(&st)) {
        DataType data = StackTop(&st);
        printf("%d ", data);
        StackPop(&st);
    }
    StackDestroy(&st);
}

int main() {
    test01();
    return 0;
}

3.2 Linked Stack

File: Stack.h

This part contains function declarations and necessary header file imports.

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>

typedef int DataType;

// Define the structure of a node
typedef struct Node {
    DataType data;         // Data field
    struct Node* next;     // Pointer field
} Node;

// Define the structure of the linked stack
typedef struct Stack {
    Node* top;             // Pointer to the top of the stack
    int size;              // Number of elements in the stack
} ST;

// Function declarations
void StackInit(ST* p);             // Initialize the stack
void StackDestroy(ST* p);          // Destroy the stack
void StackPush(ST* p, DataType x); // Push an element onto the stack
void StackPop(ST* p);              // Pop an element off the stack
DataType StackTop(ST* p);          // Get the top element of the stack
int StackSize(ST* p);              // Get the number of elements in the stack

File: Stack.c

This part includes the definitions of the declared functions.

#pragma once
#include "Stack.h"

// Initialize the stack
void StackInit(ST* p) {
    assert(p);
    p->top = NULL;  // Set the top of the stack to NULL
    p->size = 0;    // Initialize the size of the stack to 0
}

// Create a new node
Node* CreateNode(DataType x) {
    Node* newnode = (Node*)malloc(sizeof(Node));
    if (newnode == NULL) {
        perror("malloc fail");
        exit(1);
    }
    newnode->data = x;
    newnode->next = NULL;
    return newnode;
}

// Push operation
void StackPush(ST* p, DataType x) {
    assert(p);
    Node* newnode = CreateNode(x);
    newnode->next = p->top; // Point the new node's next to the current top
    p->top = newnode;       // Update the top to the new node
    ++p->size;
}

// Check if the stack is empty
bool StackEmpty(ST* p) {
    assert(p);
    return p->top == NULL;  // The stack is empty if the top is NULL
}

// Pop operation
void StackPop(ST* p) {
    assert(p);
    assert(!StackEmpty(p)); // Ensure the stack is not empty

    Node* temp = p->top;    // Temporarily store the current top
    p->top = p->top->next;  // Move the top to the next node
    free(temp);             // Free the memory of the removed node
    temp = NULL;
    --p->size;
}

// Get the top element of the stack
DataType StackTop(ST* p) {
    assert(p);
    assert(!StackEmpty(p)); // Ensure the stack is not empty
    return p->top->data;    // Return the data of the top node
}

// Get the size of the stack
int StackSize(ST* p) {
    assert(p);
    return p->size;         // Return the number of elements in the stack
}

// Destroy the stack
void StackDestroy(ST* p) {
    assert(p);
    Node* pcur = p->top;    // Start from the top of the stack
    Node* temp;

    while (pcur != NULL) {
        temp = pcur;        // Temporarily store the current node
        pcur = pcur->next;  // Move to the next node
        free(temp);         // Free the memory of the current node
    }

    p->top = NULL;          // Set the top to NULL
    p->size = 0;            // Reset the size to 0
}

File: main.c

This file tests the implementation of the linked stack.

#define _CRT_SECURE_NO_WARNINGS
#include "Stack.h"

void test01() {
    ST st;
    StackInit(&st);
    StackPush(&st, 1);
    StackPush(&st, 2);
    StackPush(&st, 3);

    while (!StackEmpty(&st)) {
        DataType data = StackTop(&st); // Get the top element
        printf("%d ", data);
        StackPop(&st);                // Pop the top element
    }
    StackDestroy(&st);                // Destroy the stack
}

int main() {
    test01();
    return 0;
}

Summary

The stack is an essential fundamental data structure suitable for various computational scenarios. By implementing both sequential and linked stacks, we gain a deeper understanding of stack operations and their applications. The choice of implementation depends on specific needs—sequential stacks are more memory-efficient, while linked stacks offer greater flexibility. We hope this blog helps you better understand the concepts and implementation of stacks!