Implementing Stack in C Language

by

A Stack is one of the data structures that manage data and operates according to the Last In First Out (LIFO) principle. Therefore, data input/output is possible only at one end.

Using Stack

  • Function call and recursive algorithm (to remember return address)
  • Implement undo in the editor
  • Operation of stacking data, etc

Utilization of Stack

  • Check parentheses pair
  • Calculation postfix expression

Major Operations in the Stack

  • Push : An operation that inserts data into a stack, adding an element to the top of the stack.
  • Pop : It is an operation that removes the data at the top of the stack.
  • Peek or Top : It is an operation that queries the data at the top of the stack, and checks the data without deleting it.
  • isEmpty : It is an operation to check whether the stack is empty.

Comparison of stack implementation methods

Methods of implementing the stack include the array and the linked-list. The comparison of each method is as follows.

Array-based stack

  • Since the size is fixed, there may be restrictions on increasing or decreasing the size of the stack. For this reason, if the size is set larger to store a small amount of data, memory usage may increase.
  • It can be implemented relatively simply and quickly.
  • When the stack is full, performance may be degraded if it needs to be rearranged to add new elements.

Linked-List based stack

  • Since the size is dynamically adjusted, the size of the stack may be flexibly adjusted.
  • Prior understanding of the linked-list and related algorithms is required.
  • It is relatively efficient to insert or delete elements.
  • Since nodes are not continuously arranged on the memory, some overhead may occur.

Implementation of Stack

The Standard Template Library(STL) is not supported in the basic C language, so the code must be implemented directly. The C++ language supports many libraries, including stacks, as standard. STL includes not only stack but also various libraries such as queues, containers, and algorithms. For this reason, I often use the C++ language to solve problems. Of course, the execution time is relatively fast.

Array-based stack

A one-dimensional data array that stores data and a top variable indicating the most recently inputted element are required. The first entered element is stored in data[0], and the most recently entered element is stored in data[top]. If the stack is empty, the value of the top variable is -1.

C
#define MAX_SIZE 100

typedef int element; // Type of data

// Define Stack Type
typedef struct {
    element data[MAX_SIZE];
    int top;
} Stack;

// Initialize Stack
void init_stk(Stack* stk) {
    stk->top = -1;
}

// Check Stack is empty
int is_stk_empty(Stack* stk) {
    return stk->top == -1;
}

// Check Stack is full
int is_stk_full(Stack* stk) {
    return stk->top == MAX_SIZE - 1;
}

// Insert data in Stack
void push(Stack* stk, element item) {
    if (is_stk_full(stk)) {
        printf("Stack overflow\n");
        return;
    }
    stk->data[++(stk->top)] = item;
}

// Remove data in Stack
element pop(Stack* stk) {
    // If the stack is empty, you can process it with any value or return an error.
    if (is_stk_empty(stk)) {
        printf("Stack underflow\n");
        return -1;
    }
    return stk->data[(stk->top)--];
}

Linked-List based stack

First, you must define the nodes in the linked-list. Each node stores a variable that stores data and a pointer to the next node.

C
#include <stdio.h>
#include <stdlib.h>

typedef int element; // Type of data

// Define Node Type
typedef struct Node {
    element data;
    struct Node* next;
} Node;

The stack performs an operation of adding and deleting an element to the end of the linked-list. Therefore, the push and pop operations of the stack may be implemented as follows.

C
// Implement Stack
typedef struct Stack {
    Node* top;
} Stack;

// Initialize Stack
void init_stk(Stack* stk) {
    stk->top = NULL;
}

// Insert data in Stack
void push(Stack* stk, element data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = stk->top;
    stk->top = newNode;
}

// Remove data in Stack
element pop(Stack* stk) {
    if (stk->top == NULL) {
        printf("Stack is empty.\n");
        return -1; // Processing exception: Stack is empty
    }
    element data = stk->top->data;
    Node* temp = stk->top;
    stk->top = stk->top->next;
    free(temp);
    return data;
}

The linked-list based stack dynamically allocates memory, so you should not forget to deallocate the memory after use. At the end of the program, all memory used as a free function must be deallocate.

In example, the int data type is stored. If you want to store another data type, you can change the element data type in the above code to another data type. Implementing it yourself without using STL can also help improve your skills. It is recommended to use STL if possible.

Leave a Reply