C语言栈的表示与实现实例详解

栈的概念

栈是一种特殊的线性表，它具备后进先出（Last-In-First-Out，LIFO）的特性。栈实现的基本操作有入栈（push）和出栈（pop）两种。

栈的表示

栈可以通过数组或链表两种数据结构进行表示。

数组表示

数组表示的栈是一段连续的内存空间，可以使用数组下标代表每个栈元素的位置。数组的顶部指针用于标识当前栈顶元素所在的位置。

下面是C语言中数组表示栈的实现过程，其中使用了结构体Stack对栈进行封装。

typedef struct {
  int *array;     // 栈使用的数组
  int size;       // 栈的总容量
  int top;        // 栈顶的位置
} Stack;

// 初始化一个容量为size的栈
void initStack(Stack *s, int size) {
  s->array = (int *) malloc(size * sizeof(int));
  s->size = size;
  s->top = -1;
}

// 入栈操作
void push(Stack *s, int data) {
  if (s->top == s->size - 1) {
    printf("Stack is full\n");
    return;
  }
  s->array[++s->top] = data;
}

// 出栈操作
int pop(Stack *s) {
  if (s->top == -1) {
    printf("Stack is empty\n");
    return -1;
  }
  return s->array[s->top--];
}

链表表示

链表表示的栈利用了链表的指针域来建立每个栈元素之间的联系。链表的头指针指向栈顶元素。

下面是C语言中链表表示栈的实现过程，其中使用了结构体StackNode对栈元素进行封装。

typedef struct StackNode {
  int data;               // 栈元素的值
  struct StackNode *next; // 下一个栈元素的地址
} StackNode;

typedef struct {
  StackNode *top;         // 栈顶元素
} Stack;

// 初始化一个空栈
void initStack(Stack *s) {
  s->top = NULL;
}

// 入栈操作
void push(Stack *s, int data) {
  StackNode *newNode = (StackNode *) malloc(sizeof(StackNode));
  newNode->data = data;
  newNode->next = s->top;
  s->top = newNode;
}

// 出栈操作
int pop(Stack *s) {
  if (s->top == NULL) {
    printf("Stack is empty\n");
    return -1;
  }
  int result = s->top->data;
  StackNode *topNode = s->top;
  s->top = s->top->next;
  free(topNode);
  return result;
}

栈的实现实例

示例1：匹配括号

栈可以用于匹配括号的问题，常见的应用场景是在编写代码时，需要检查代码中的括号是否匹配。例如，检查下列代码中的括号是否匹配。

void func() {
  int a = 1;
  if (a > 0) {
    printf("a is positive.\n");
  } else {
    printf("a is negative.\n");
  }
}

可以发现，该代码中的括号是匹配的。具体解决方法是：使用一个栈来保存每个左括号出现的位置，当遇到右括号时，从栈中弹出一个左括号的位置，判断左右括号的位置是否匹配。如果栈为空或栈顶元素不是与当前右括号匹配的左括号，则出现括号不匹配的错误。

下面是使用数组表示栈的实现过程。

bool checkParenthesis(char *str) {
  Stack s;
  initStack(&s, strlen(str));

  for (int i = 0; i < strlen(str); i++) {
    if (str[i] == '(') {
      push(&s, i);
    } else if (str[i] == ')') {
      if (s.top == -1) {
        printf("Error: unmatched ')' at position %d\n", i);
        return false;
      }
      int leftIndex = pop(&s);
      printf("Matched '()' at positions %d and %d\n", leftIndex, i);
    }
  }

  if (s.top != -1) {
    printf("Error: unmatched '(' at position %d\n", s.array[s.top]);
    return false;
  }

  return true;
}

示例2：中缀表达式转后缀表达式

栈还可以用于中缀表达式转后缀表达式的问题，例如将“2+3*(4+5)-6”这个中缀表达式转换为后缀表达式。具体解决方法是：从左向右遍历中缀表达式，使用一个栈来保存运算符，如果遇到数字，则直接输出到后缀表达式中。如果遇到运算符，则将其压入栈中。需要注意的是，运算符有优先级，需要根据优先级来确定何时将运算符输出到后缀表达式中。当遇到左括号时，将其压入栈中。当遇到右括号时，将栈中的运算符弹出直到遇到左括号为止，并且左右括号都不在后缀表达式中输出。

下面是使用数组表示栈的实现过程。

bool isOperator(char c) {
  return c == '+' || c == '-' || c == '*' || c == '/';
}

int getOperatorPriority(char c) {
  switch (c) {
    case '+':
    case '-':
      return 1;
    case '*':
    case '/':
      return 2;
    default:
      return 0;
  }
}

void infixToPostfix(char *infix, char *postfix) {
  Stack s;
  initStack(&s, strlen(infix));
  int j = 0;
  for (int i = 0; i < strlen(infix); i++) {
    if (isdigit(infix[i])) {
      postfix[j++] = infix[i];
    } else if (isOperator(infix[i])) {
      while (s.top != -1 && getOperatorPriority(infix[i]) <= getOperatorPriority(s.array[s.top])) {
        postfix[j++] = pop(&s);
      }
      push(&s, infix[i]);
    } else if (infix[i] == '(') {
      push(&s, infix[i]);
    } else if (infix[i] == ')') {
      while (s.top != -1 && s.array[s.top] != '(') {
        postfix[j++] = pop(&s);
      }
      if (s.top == -1) {
        printf("Error: unmatched '(' at position %d\n", i);
        return;
      }
      pop(&s);
    } else {
      printf("Error: invalid character '%c' at position %d\n", infix[i], i);
      return;
    }
  }
  while (s.top != -1) {
    if (s.array[s.top] == '(') {
      printf("Error: unmatched '(' at position %d\n", s.top);
      return;
    }
    postfix[j++] = pop(&s);
  }
  postfix[j] = '\0';
}

结语

栈是一种非常常用的数据结构，可以用于很多实际问题的解决。本文介绍了栈的基本概念、表示方法和实现实例，希望能对读者有所帮助。