C语言超详细讲解栈的实现及代码

什么是栈？

栈（Stack）是计算机中的一种数据结构，也是一种线性结构。它只允许在特定一端进行插入和删除操作，即在栈顶进行操作。栈的特点是后进先出（LIFO，Last In First Out），即在栈顶进入元素，在栈顶取出元素。

栈的实现

栈的实现可以用数组（array）或链表（linked list）来实现。其中，一般使用数组来实现栈。

数组实现栈

首先，我们需要定义一个栈结构体：

#define MAXSIZE 100 // 定义栈的最大容量为100

typedef struct {
  int data[MAXSIZE]; // 存放栈中元素的数组
  int top; // 栈顶指针
} Stack;

其中，data用来储存栈中的元素，top表示栈顶指针，即栈中元素个数。我们将栈顶指针top初始化为-1，表示栈为空。

void InitStack(Stack * S) {
  S->top = -1;
}

接下来，我们需要实现入栈（Push）和出栈（Pop）操作。入栈操作就是往栈顶添加元素，出栈操作则是从栈顶删除元素。我们也需要判断栈是否为空或已满。

bool Push(Stack * S, int x) {
  if (S->top == MAXSIZE - 1) // 栈已满，不能继续入栈
    return false;
  S->data[++S->top] = x; // 栈顶指针+1，将元素x压入栈顶
  return true;
}

bool Pop(Stack * S, int * x) {
  if (S->top == -1) // 栈已空，无法继续出栈
    return false;
  *x = S->data[S->top--]; // 将栈顶元素弹出并保存到x中，栈顶指针-1
  return true;
}

最后，我们还需要实现取栈顶元素（GetTop）和判断栈是否为空（IsEmpty）：

bool GetTop(Stack * S, int * x) {
  if (S->top == -1) // 栈已空，无法取栈顶元素
    return false;
  *x = S->data[S->top]; // 将栈顶元素赋值给x
  return true;
}

bool IsEmpty(Stack * S) {
  return (S->top == -1);
}

链表实现栈

链表实现栈相较于数组实现，需要的内存空间不固定，但需要大量消耗内存来存储节点的指针和数据。链表实现栈的基本操作和数组实现栈的基本操作类似，这里不再赘述。

示例说明

示例1：使用栈实现字符串反转

我们可以使用栈来实现字符串反转。具体实现方法是先把字符串中的每个字符依次入栈，再依次出栈输出即可。

void reverse(char * str) {
  Stack S;
  InitStack(&S);
  int i = 0;
  while (str[i]) {
    Push(&S, str[i++]);
  }
  i = 0;
  while (!IsEmpty(&S)) {
    Pop(&S, &str[i++]);
  }
}

示例2：使用栈实现中缀表达式计算

我们可以使用栈来实现中缀表达式计算。将中缀表达式转换成后缀表达式（也称逆波兰式）后，再使用栈进行计算。这里简单介绍一下中缀表达式转后缀表达式的方法。

我们需要一个运算符栈和一个数字栈。从左到右依次扫描中缀表达式的每个元素，如果是数字就入数字栈，如果是运算符就比较优先级，如果该运算符优先级低于或等于栈顶运算符，则将栈顶运算符出栈并加入后缀表达式中，直至该运算符优先级高于栈顶运算符或运算符栈为空，最后将该运算符进栈。

void infix2postfix(char * infix, char * postfix) {
  Stack S;
  InitStack(&S); // 运算符栈
  int i = 0, j = 0;
  while (infix[i]) {
    if (isdigit(infix[i])) {
      postfix[j++] = infix[i++];
    } else {
      char op;
      if (infix[i] == '(') {
        Push(&S, infix[i]);
        i++;
      } else if (infix[i] == ')') {
        while (Pop(&S, &op) && op != '(') {
          postfix[j++] = op;
        }
        i++;
      } else {
        while (!IsEmpty(&S) && prio(S.data[S.top]) >= prio(infix[i])) {
          Pop(&S, &op);
          postfix[j++] = op;
        }
        Push(&S, infix[i++]);
      }
    }
  }
  while (!IsEmpty(&S)) {
    Pop(&S, &postfix[j++]);
  }
  postfix[j] = 0;
}

int prio(char op) { // 运算符优先级
  switch (op) {
    case '+':
    case '-':
      return 1;
    case '*':
    case '/':
      return 2;
    case '(':
    case ')':
      return 0;
  }
  return -1;
}

int postfix_eval(char * postfix) {
  Stack S; // 数字栈
  InitStack(&S);
  int i = 0, op1, op2, result;
  while (postfix[i]) {
    char ch = postfix[i];
    if (isdigit(ch)) {
      Push(&S, ch - '0');
    } else {
      Pop(&S, &op2);
      Pop(&S, &op1);
      switch (ch) {
        case '+':
          result = op1 + op2;
          break;
        case '-':
          result = op1 - op2;
          break;
        case '*':
          result = op1 * op2;
          break;
        case '/':
          result = op1 / op2;
          break;
        default:
          break;
      }
      Push(&S, result);
    }
    i++;
  }
  Pop(&S, &result);
  return result;
}

总结

以上是栈的实现及应用的详细讲解，希望有所帮助。在实际编程中，栈是非常常用的数据结构，掌握栈的实现及应用对于提高代码效率和可读性非常有帮助。