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日

相关文章

  • React框架 dva 和 mobx 的使用感受

    React框架 dva 和 mobx 的使用感受 React 是目前前端开发中最流行的框架之一，而 dva 和 mobx 则是在 React 生态系统中非常受欢迎的状态管理工具。在实际项目中，我们尝试使用了 dva 和 mobx 两种框架，并在使用过程中有一些收获和感受。 dva 框架的使用感受 dva 是一个基于 React 和 Redux 的 web 应…

    其他 2023年3月28日
    00

  • iOS 微信分享功能简单实现

    iOS 微信分享功能简单实现攻略 概述 在 iOS 应用程序中，我们经常需要与微信进行交互，其中一项常见的功能就是分享内容到微信朋友圈或者微信好友。本文将介绍如何利用微信开放平台提供的 SDK，简单实现 iOS 应用向微信分享的功能。 准备 在使用微信 SDK 之前，我们需要进行如下准备工作： 在微信开放平台注册并创建应用。 将微信 SDK 集成到我们的项目…

    other 2023年6月26日
    00

  • zookeeper入门(二)

    ZooKeeper入门(二)：完整攻略 在上一篇文章中，我们介绍了ZooKeeper的基本概念和安装配置。本文将继续介绍ZooKeeper的方法，包括ZooKeeper的数据模型、ZooKeeper的API和ZooKeeper的常用命令。同时，本文还提供了两个Python示例来演示如何使用ZooKeeper。 步骤1：了解ZooKeeper的数据模型 Zoo…

    other 2023年5月9日
    00

  • JavaScript 中级笔记 第三章

    JavaScript 中级笔记 第三章攻略 1. 闭包（Closures） 闭包是 JavaScript 中一个重要的概念，它允许函数访问其词法作用域之外的变量。闭包在许多情况下都非常有用，例如在创建私有变量和实现模块化时。 示例 1：创建私有变量 function counter() { let count = 0; return function() {…

    other 2023年8月20日
    00

  • vue-cli3 配置开发与测试环境详解

    下面我将为您详细讲解 “vue-cli3 配置开发与测试环境详解” 的完整攻略。 一、什么是 Vue CLI3 Vue CLI3 是 Vue.js 官方提供的脚手架工具，它提供了一整套预定义的项目脚手架，能够帮助开发者快速搭建 Vue.js 项目的基础框架。 二、Vue CLI3 的使用 Vue CLI3 通过命令行交互的方式，提供了一系列的命令用于创建、启…

    other 2023年6月27日
    00

  • 解决elementui中NavMenu导航菜单高亮问题(解决多种情况)

    解决elementui中NavMenu导航菜单高亮问题(解决多种情况) 在使用Element UI的NavMenu导航菜单组件时，有时候会遇到高亮问题，即当前所在的页面对应的菜单项没有正确高亮显示。这个问题可能出现在多种情况下，例如路由嵌套、动态路由等。下面是解决这个问题的完整攻略。 步骤一：设置路由的meta属性 首先，在路由配置中为每个路由项设置一个me…

    other 2023年7月28日
    00

  • 64位 win10系统安装绿色版mysql-5.7.16-winx64的教程

    下面是详细的攻略： 1. 下载MySQL-5.7.16-winx64绿色版安装包 首先，在MySQL官网中找到MySQL-5.7.16-winx64绿色版的下载链接，下载到本地。 2. 安装MySQL-5.7.16-winx64 接着，找到下载后的压缩包，解压到本地某一文件夹，比如 D:\mysql-5.7.16-winx64。 进入解压后的文件夹，双击运行…

    other 2023年6月27日
    00

  • CSS标签居中

    下面是“CSS标签居中的完整攻略”，包括基本原理、实现方法和两个示例说明。 基本原理 在 CSS 中，要使标签居中，需要使用以下两个属性： display: flex; 用于将容器设置为弹性盒子。 justify-content: center; 用于将子元素水平居中。 实现方法 实现标签居中可以按照以下步骤进行操作： 创建一个容器元素。 <div c…

    other 2023年5月5日
    00
合作推广
合作推广
分享本页
返回顶部