Data Structures 06 - Stack

Code

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

#define STACK_MAX_SIZE 10 // Define the maximum capacity of the stack

// Define a character stack structure
typedef struct CharStack {
    int top; // Stack top pointer, initialized to -1 indicating an empty stack
    int data[STACK_MAX_SIZE]; // Stack storage array, fixed maximum length
} *CharStackPtr;

// Output the elements in the stack
void outputStack(CharStackPtr paraStack) {
    for (int i = 0; i <= paraStack->top; i ++) {
        printf("%c ", paraStack->data[i]);
    }
    printf("\r\n");
}

// Initialize an empty character stack
CharStackPtr charStackInit() {
    CharStackPtr resultPtr = (CharStackPtr)malloc(sizeof(struct CharStack));
    resultPtr->top = -1; // Initialize stack top pointer to -1
    return resultPtr;
}

// Push an element onto the stack
void push(CharStackPtr paraStackPtr, int paraValue) {
    if (paraStackPtr->top >= STACK_MAX_SIZE - 1) { // Check if stack space is full
        printf("Cannot push element: stack full.\r\n");
        return;
    }
    paraStackPtr->top++; // Update stack top pointer
    paraStackPtr->data[paraStackPtr->top] = paraValue; // Push element onto the stack
}

// Pop an element from the stack
char pop(CharStackPtr paraStackPtr) {
    if (paraStackPtr->top < 0) { // Check if stack is empty
        printf("Cannot pop element: stack empty.\r\n");
        return '\0'; // If stack is empty, return null character
    }
    paraStackPtr->top--; // Update stack top pointer
    return paraStackPtr->data[paraStackPtr->top + 1]; // Return the popped element
}

// Test push and pop functions
void pushPopTest() {
    printf("---- pushPopTest begins. ----\r\n");

    CharStackPtr tempStack = charStackInit(); // Initialize stack
    printf("After initialization, the stack is: ");
    outputStack(tempStack);

    // Push elements
    for (char ch = 'a'; ch < 'm'; ch ++) {
        printf("Pushing %c.\r\n", ch);
        push(tempStack, ch);
        outputStack(tempStack);
    }

    // Pop elements
    char ch;
    for (int i = 0; i < 3; i ++) {
        ch = pop(tempStack);
        printf("Pop %c.\r\n", ch);
        outputStack(tempStack);
    }

    printf("---- pushPopTest ends. ----\r\n");
}

// Program entry point
int main() {
    pushPopTest(); // Run test function
}

Code Summary:

1. Defines a fixed-size stack (STACK_MAX_SIZE is 10) for storing characters.

2. The CharStack structure contains a stack top pointer top and a data array data. The stack top pointer is initialized to -1, indicating an empty stack.

3. The charStackInit function initializes an empty stack and returns a pointer to the stack.

4. The push function pushes a new element onto the stack. It first checks if the stack is full; if not, it pushes the new element onto the top of the stack.

5. The pop function pops an element from the stack. It first checks if the stack is empty; if not, it pops the top element and returns it.

6. The outputStack function outputs all elements in the stack.

7. The pushPopTest function is a test function for testing push and pop operations. It initializes a stack, then pushes a series of characters, then pops several characters, outputting the current state of the stack after each operation.

8. The main function is the program entry point, calling the pushPopTest function to execute the test.

Running Result