C语言：基本数据结构（堆栈、队列）的数组、链表实现； 一、 实验目的： 1. 学习基本数据结构（堆栈、队列的实现） 2. 要求：分别通过数组、链表的形式对上述两个数据结构进行实现； 3. 注意： • 学习如何实现多文件C程序的编译和运行； • 学习使用头文件实现函数信息（接口）的声明； • 学习掌握全局变量、外部变量的声明和使用； • 学习使用make命令对多文件的工程进行管理（编译，链接），配合Makefile文件； 二、 实验提示： a) 可以对堆栈（队列）存储数组（队列）定义为全局变量； b) 实现堆栈LIFO操作方法，push（），pop（） c) 实现队列的FIFO操作方法,put（），get（） d） 将上述函数保存在不同的文件中； e) 主函数中可以添加相应的测试代码；

以下是一份示例代码，包含了堆栈和队列的数组、链表实现。代码分为头文件和源文件，使用 make 命令进行编译和链接。

stack.h：

#ifndef STACK_H
#define STACK_H

#define MAX_STACK_SIZE 100

void stack_array_push(int element);
int stack_array_pop();
void stack_list_push(int element);
int stack_list_pop();

#endif

stack_array.c：

#include "stack.h"

int stack_array[MAX_STACK_SIZE];
int top = 0;

void stack_array_push(int element) {
    if (top == MAX_STACK_SIZE) {
        printf("Stack overflow!\n");
        return;
    }
    stack_array[top++] = element;
}

int stack_array_pop() {
    if (top == 0) {
        printf("Stack underflow!\n");
        return -1;
    }
    return stack_array[--top];
}

stack_list.c：

#include "stack.h"
#include <stdlib.h>

typedef struct stack_node {
    int element;
    struct stack_node* next;
} StackNode;

StackNode* top = NULL;

void stack_list_push(int element) {
    StackNode* new_node = (StackNode*)malloc(sizeof(StackNode));
    new_node->element = element;
    new_node->next = top;
    top = new_node;
}

int stack_list_pop() {
    if (top == NULL) {
        printf("Stack underflow!\n");
        return -1;
    }
    int element = top->element;
    StackNode* old_top = top;
    top = top->next;
    free(old_top);
    return element;
}

queue.h：

#ifndef QUEUE_H
#define QUEUE_H

#define MAX_QUEUE_SIZE 100

void queue_array_put(int element);
int queue_array_get();
void queue_list_put(int element);
int queue_list_get();

#endif

queue_array.c：

#include "queue.h"

int queue_array[MAX_QUEUE_SIZE];
int front = 0;
int rear = 0;

void queue_array_put(int element) {
    if (rear == MAX_QUEUE_SIZE) {
        printf("Queue overflow!\n");
        return;
    }
    queue_array[rear++] = element;
}

int queue_array_get() {
    if (front == rear) {
        printf("Queue underflow!\n");
        return -1;
    }
    return queue_array[front++];
}

queue_list.c：

#include "queue.h"
#include <stdlib.h>

typedef struct queue_node {
    int element;
    struct queue_node* next;
} QueueNode;

QueueNode* front = NULL;
QueueNode* rear = NULL;

void queue_list_put(int element) {
    QueueNode* new_node = (QueueNode*)malloc(sizeof(QueueNode));
    new_node->element = element;
    new_node->next = NULL;
    if (rear == NULL) {
        front = rear = new_node;
    } else {
        rear->next = new_node;
        rear = new_node;
    }
}

int queue_list_get() {
    if (front == NULL) {
        printf("Queue underflow!\n");
        return -1;
    }
    int element = front->element;
    QueueNode* old_front = front;
    front = front->next;
    if (front == NULL) {
        rear = NULL;
    }
    free(old_front);
    return element;
}

main.c：

#include <stdio.h>
#include "stack.h"
#include "queue.h"

int main() {
    // Stack array implementation
    printf("Stack array implementation:\n");
    stack_array_push(1);
    stack_array_push(2);
    stack_array_push(3);
    printf("%d\n", stack_array_pop());
    printf("%d\n", stack_array_pop());
    printf("%d\n", stack_array_pop());
    printf("%d\n", stack_array_pop()); // should print "Stack underflow!"

    // Stack list implementation
    printf("Stack list implementation:\n");
    stack_list_push(1);
    stack_list_push(2);
    stack_list_push(3);
    printf("%d\n", stack_list_pop());
    printf("%d\n", stack_list_pop());
    printf("%d\n", stack_list_pop());
    printf("%d\n", stack_list_pop()); // should print "Stack underflow!"

    // Queue array implementation
    printf("Queue array implementation:\n");
    queue_array_put(1);
    queue_array_put(2);
    queue_array_put(3);
    printf("%d\n", queue_array_get());
    printf("%d\n", queue_array_get());
    printf("%d\n", queue_array_get());
    printf("%d\n", queue_array_get()); // should print "Queue underflow!"

    // Queue list implementation
    printf("Queue list implementation:\n");
    queue_list_put(1);
    queue_list_put(2);
    queue_list_put(3);
    printf("%d\n", queue_list_get());
    printf("%d\n", queue_list_get());
    printf("%d\n", queue_list_get());
    printf("%d\n", queue_list_get()); // should print "Queue underflow!"

    return 0;
}

Makefile：

CC = gcc
CFLAGS = -Wall -Wextra -Wpedantic -std=c99

all: main

main: main.o stack_array.o stack_list.o queue_array.o queue_list.o
    $(CC) $(CFLAGS) -o $@ $^

main.o: main.c stack.h queue.h
    $(CC) $(CFLAGS) -c $<

stack_array.o: stack_array.c stack.h
    $(CC) $(CFLAGS) -c $<

stack_list.o: stack_list.c stack.h
    $(CC) $(CFLAGS) -c $<

queue_array.o: queue_array.c queue.h
    $(CC) $(CFLAGS) -c $<

queue_list.o: queue_list.c queue.h
    $(CC) $(CFLAGS) -c $<

clean:
    rm -f main *.o