1. Python技术站首页
  2. other

C语言数据结构进阶之栈和队列的实现

• other

C语言数据结构进阶之栈和队列的实现

什么是栈？

栈是一种数据结构，具有后进先出（LIFO）的特点。这意味着最后插入的数据最先被取出。在栈中，插入和删除数据只发生在一端，称为栈顶（top），另一端称为栈底（bottom）。下面介绍如何使用 C 语言实现栈的基本操作。

栈的基本操作

  • push：将元素压入栈顶。
  • pop：将元素从栈顶弹出。
  • isEmpty：检查栈是否为空。
  • isFull：检查栈是否已满，通常用于数组实现的栈。

栈的实现方式

  1. 数组实现

使用数组可以较简单地实现一个栈。定义一个数组存储栈元素，再定义一个栈顶指针，可以记录栈顶元素的位置。当元素入栈时，将它添加到数组末尾，并将栈顶指针加一；当元素出栈时，将栈顶指针减一，然后返回栈顶元素。

```c
#define MAX_SIZE 100
typedef struct {
int data[MAX_SIZE];
int top;
} Stack;

void push(Stack *s, int x) {
if (s->top >= MAX_SIZE) {
printf("ERROR: Stack is full\n");
return;
}
s->data[++s->top] = x;
}

int pop(Stack *s) {
if (s->top == -1) {
printf("ERROR: Stack is empty\n");
return -1;
}
return s->data[s->top--];
}

int isEmpty(Stack *s) {
return s->top == -1;
}
```

  1. 链表实现

另一种实现栈的方式是使用链表。链表是一种递归的数据结构，其结点包含了当前元素的值和一个指向下一个结点的指针。在实现栈时，可以使用链表作为储存元素的容器。在链表的头部作为栈顶，并总是在链表顶部插入和删除元素。

```c
typedef struct Node {
int data;
struct Node* next;
} Node;

typedef struct {
Node *top;
} Stack;

void push(Stack s, int x) {
Node newNode = (Node *)malloc(sizeof(Node));
newNode->data = x;
newNode->next = s->top;
s->top = newNode;
}

int pop(Stack s) {
if (s->top == NULL) {
printf("ERROR: Stack is empty\n");
return -1;
}
Node popped = s->top;
int data = popped->data;
s->top = popped->next;
free(popped);
return data;
}

int isEmpty(Stack *s) {
return s->top == NULL;
}
```

栈的应用

  • 判断括号匹配
  • 二叉树的非递归遍历

什么是队列？

队列（queue）是一种数据结构，具有先进先出（FIFO）的特点。这意味着先插入的数据也会最先被取出。在队列中，插入操作只发生在队列尾部，称为队尾（rear）；删除操作只发生在队列头部，称为队头（front）。下面介绍如何使用 C 语言实现队列的基本操作。

队列的基本操作

  • enqueue：将元素插入队尾。
  • dequeue：将队头元素删除。
  • isEmpty：检查队列是否为空。
  • isFull：检查队列是否已满。

队列的实现方式

  1. 数组实现

使用数组可以较简单地实现一个队列。定义一个数组存储队列元素，再定义两个指针 front 和 rear，分别指向队列头和队列尾。插入操作时，将元素添加到 rear 指向的位置，并将该指针加一；删除操作时，将 front 指针加一。

```c
#define MAX_SIZE 100
typedef struct {
int data[MAX_SIZE];
int front, rear;
} Queue;

void enqueue(Queue *q, int x) {
int nextRear = (q->rear + 1) % MAX_SIZE;
if (nextRear == q->front) {
printf("ERROR: Queue is full\n");
return;
}
q->data[q->rear] = x;
q->rear = nextRear;
}

int dequeue(Queue *q) {
if (q->front == q->rear) {
printf("ERROR: Queue is empty\n");
return -1;
}
int data = q->data[q->front];
q->front = (q->front + 1) % MAX_SIZE;
return data;
}

int isEmpty(Queue *q) {
return q->front == q->rear;
}
```

  1. 链表实现

和栈一样，队列也可以用链表实现。定义一个链表结点，包含当前元素的值和一个指针，指向下一个结点。在队列中，使用一个指针 front 指向队头，并总是在链表尾部插入元素。

```c
typedef struct Node {
int data;
struct Node* next;
} Node;

typedef struct {
Node front, rear;
} Queue;

void enqueue(Queue q, int x) {
Node newNode = (Node *)malloc(sizeof(Node));
newNode->data = x;
newNode->next = NULL;
if (q->rear) {
q->rear->next = newNode;
}
q->rear = newNode;
if (q->front == NULL) {
q->front = newNode;
}
}

int dequeue(Queue q) {
if (q->front == NULL) {
printf("ERROR: Queue is empty\n");
return -1;
}
Node popped = q->front;
int data = popped->data;
q->front = popped->next;
if (q->front == NULL) {
q->rear = NULL;
}
free(popped);
return data;
}

int isEmpty(Queue *q) {
return q->front == NULL;
}
```

队列的应用

  • 广度优先搜索算法（BFS）
  • 模拟处理实体到达和离开事件

示例

使用栈实现计算器

思路：将中缀表达式转换成后缀表达式，再通过栈计算后缀表达式的值。

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

#define MAX_SIZE 100

typedef struct {
  int data[MAX_SIZE];
  int top;
} Stack;

void push(Stack *s, int x) {
  if (s->top >= MAX_SIZE) {
    printf("ERROR: Stack is full\n");
    return;
  }
  s->data[++s->top] = x;
}

int pop(Stack *s) {
  if (s->top == -1) {
    printf("ERROR: Stack is empty\n");
    return -1;
  }
  return s->data[s->top--];
}

int isEmpty(Stack *s) {
  return s->top == -1;
}

int precedence(char op) {
  if (op == '+' || op == '-') {
    return 1;
  }
  if (op == '*' || op == '/') {
    return 2;
  }
  return 0;
}

void infixToPostfix(char *infix, char *postfix) {
  Stack s;
  s.top = -1;
  int i, j;
  char ch, x;
  for (i = 0, j = 0; infix[i] != '\0'; i++) {
    ch = infix[i];
    if (isdigit(ch)) {
      postfix[j++] = ch;
    } else if (ch == '(') {
      push(&s, '(');
    } else if (ch == ')') {
      while ((x = pop(&s)) != '(') {
        postfix[j++] = x;
      }
    } else {
      while (!isEmpty(&s) && precedence(s.data[s.top]) >= precedence(ch)) {
        postfix[j++] = pop(&s);
      }
      push(&s, ch);
    }
  }
  while (!isEmpty(&s)) {
    postfix[j++] = pop(&s);
  }
  postfix[j] = '\0';
}

int evaluatePostfix(char *postfix) {
  Stack s;
  s.top = -1;
  int i, x, y, z;
  char ch;
  for (i = 0; postfix[i] != '\0'; i++) {
    ch = postfix[i];
    if (isdigit(ch)) {
      push(&s, ch - '0');
    } else {
      y = pop(&s);
      x = pop(&s);
      switch(ch) {
        case '+': z = x + y; break;
        case '-': z = x - y; break;
        case '*': z = x * y; break;
        case '/': z = x / y; break;
        default: break;
      }
      push(&s, z);
    }
  }
  return pop(&s);
}

int main() {
  char infix[MAX_SIZE], postfix[MAX_SIZE];
  printf("Enter an infix expression: ");
  fgets(infix, MAX_SIZE, stdin);
  infixToPostfix(infix, postfix);
  printf("Postfix expression: %s\n", postfix);
  printf("Result: %d\n", evaluatePostfix(postfix));
  return 0;
}

使用队列模拟实体到达和离开事件

思路：生成随机的实体到达事件和离开事件，将它们放到两个队列中，每次取两个队列的队头元素，并比较它们的时间戳，如果离开事件的时间戳早于到达事件，说明实体已经离开，弹出节点；否则实体进入处理，从到达队列中弹出节点并加入处理队列。

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

typedef struct {
  int id;
  int timestamp;
} Entity;

typedef struct Node {
  Entity data;
  struct Node* next;
} Node;

typedef struct {
  Node *front, *rear;
} Queue;

void enqueue(Queue *q, Entity x) {
  Node *newNode = (Node *)malloc(sizeof(Node));
  newNode->data = x;
  newNode->next = NULL;
  if (q->rear) {
    q->rear->next = newNode;
  }
  q->rear = newNode;
  if (q->front == NULL) {
    q->front = newNode;
  }
}

Entity dequeue(Queue *q) {
  if (q->front == NULL) {
    printf("ERROR: Queue is empty\n");
    Entity e = {0, 0};
    return e;
  }
  Node *popped = q->front;
  Entity data = popped->data;
  q->front = popped->next;
  if (q->front == NULL) {
    q->rear = NULL;
  }
  free(popped);
  return data;
}

int isEmpty(Queue *q) {
  return q->front == NULL;
}

void printQueue(Queue q) {
  Node *current = q.front;
  while (current != NULL) {
    printf("%d [%d] ", current->data.id, current->data.timestamp);
    current = current->next;
  }
  printf("\n");
}

void simulate() {
  Queue arrival, departure, processing;
  arrival.front = arrival.rear = NULL;
  departure.front = departure.rear = NULL;
  processing.front = processing.rear = NULL;

  int currentTimestamp = 0, id = 0;
  int arrivalCount = 0, departureCount = 0;
  while (arrivalCount < 10) {
    currentTimestamp++;
    if (rand() % 3 != 0) {
      // generate arrival event
      Entity entity = {++id, currentTimestamp};
      printf("Entity %d arrived at time %d\n", entity.id, entity.timestamp);
      enqueue(&arrival, entity);
      arrivalCount++;
    }
    if (departure.front && currentTimestamp >= departure.front->data.timestamp) {
      // departure event occurs before next arrival
      Entity entity = dequeue(&departure);
      printf("Entity %d departed at time %d\n", entity.id, entity.timestamp);
      departureCount++;
    } else if (arrival.front) {
      // process next arrival event
      Entity entity = dequeue(&arrival);
      printf("Entity %d entered processing queue at time %d\n", entity.id, entity.timestamp);
      enqueue(&processing, entity);
    }
    if (processing.front && !departure.front) {
      // start processing if queue not empty and no event scheduled
      Entity entity = dequeue(&processing);
      Entity nextDeparture = {entity.id, currentTimestamp + rand() % 5 + 1};
      printf("Entity %d started processing at time %d\n", entity.id, currentTimestamp);
      printf("Entity %d departure scheduled at time %d\n", entity.id, nextDeparture.timestamp);
      enqueue(&departure, nextDeparture);
    }
    printf("Simulation state:\n");
    printf("Arrival queue: ");
    printQueue(arrival);
    printf("Processing queue: ");
    printQueue(processing);
    printf("Departure queue: ");
    printQueue(departure);
    printf("-------------------------\n");
  }
  printf("Simulation ended\n");
}

int main() {
  srand(time(NULL));
  simulate();
  return 0;
}

以上是“C语言数据结构进阶之栈和队列的实现”的完整攻略。

本站文章如无特殊说明，均为本站原创，如若转载，请注明出处：C语言数据结构进阶之栈和队列的实现 - Python技术站

赞 (0)
0 0 打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2023年6月27日
下一篇 2023年6月27日

相关文章

  • Android自定义控件样式实例详解

    Android自定义控件样式实例详解 概述 本文主要讲解如何在Android应用中使用自定义控件样式，并提供示例说明。通过阅读本文，你将学到： 什么是Android自定义控件样式 如何在Android项目中创建自定义控件 如何使用XML样式文件 如何使用代码设置控件样式 示例说明 什么是Android自定义控件样式 Android自定义控件样式即是指在And…

    other 2023年6月25日
    00

  • 详解jvm双亲委派机制

    详解JVM双亲委派机制 前言 Java虚拟机（JVM）是一种能够执行Java字节码的虚拟机，它是Java平台的核心部分之一。在Java平台中，类的加载、验证、解析、初始化等操作都是由JVM来完成的。而JVM在执行这些操作时，会采用一种称为“双亲委派机制”的策略来保证Java程序的安全性和稳定性。下面，我们将详细讲解这种机制的实现原理和作用。 双亲委派机制的定…

    other 2023年6月27日
    00

  • Pycharm导入Python包,模块的图文教程

    以下是PyCharm导入Python包和模块的图文教程的完整攻略： 打开PyCharm并创建一个新的Python项目。 在项目的根目录下创建一个新的Python文件。 在Python文件中，使用import关键字导入需要的包或模块。例如： python import numpy as np import pandas as pd PyCharm会自动检测导入…

    other 2023年10月14日
    00

  • phpcms V9二级目录下分页路径不正确问题的彻底解决方法

    下面我将为你详细讲解“phpcms V9二级目录下分页路径不正确问题的彻底解决方法”的完整攻略。 问题描述 当我们把phpcms V9放置在站点的非根目录下时，就会出现分页路径不正确的问题。原因是phcms V9默认使用的是根目录路径，而没有考虑站点放置的目录。例如，我们的站点放置在www.example.com/cms目录下，当我们访问分页时，路径会变成w…

    other 2023年6月27日
    00

  • MySQL更新存放JSON的字段、\“ 转义成 “的问题描述

    MySQL中可以使用UPDATE语句更新存放JSON的字段。JSON是一种轻量级的数据交换格式，常常用于表示复杂的数据结构。当我们需要更新JSON字段中的值时，可以使用MySQL提供的一些内置函数来实现。 在更新JSON字段时，有时候需要使用到双引号。而MySQL中默认的转义字符是反斜杠（\），所以需要使用双反斜杠（\）来转义双引号。 下面是一个具体的示例，…

    other 2023年6月25日
    00

  • JavaScript使用递归和循环实现阶乘的实例代码

    让我来详细讲解一下JavaScript使用递归和循环实现阶乘的实例代码的攻略。 阶乘的定义 首先，我们需要知道什么是阶乘。阶乘是指一个自然数 n 的阶乘，写作 n!，它表示从1到n这n个自然数的乘积，即：n! = 1 × 2 × 3 × … × n。 递归实现阶乘 递归是一种函数调用自身的方式。我们可以使用递归来实现阶乘的计算。首先，我们需要写一个可以计…

    other 2023年6月27日
    00

  • Android实现页面跳转

    Android实现页面跳转攻略 在Android开发中，页面跳转是非常常见的需求。下面是一份详细的攻略，介绍了如何在Android应用中实现页面跳转。 1. 使用Intent进行页面跳转 Intent是Android中用于在组件之间传递数据和执行操作的对象。通过使用Intent，我们可以实现页面之间的跳转。 步骤： 在源页面的按钮点击事件或其他触发事件中，创…

    other 2023年8月20日
    00

  • python 内置错误类型 Built-in Exceptions

    Python 内置错误类型 Built-in Exceptions 在 Python 中，错误类型被定义为异常。每个异常都是一个类，这些类都是内置到 Python 中的。在程序执行过程中，当 Python 遇到错误时会自动抛出相应的异常。 以下是 Python 内置的一些常见异常及其描述： 1. Exception（所有异常的基类） 在 Python 中，所…

    其他 2023年3月28日
    00
合作推广
合作推广
分享本页
返回顶部