栈和队列--C语言实现

栈的概念及结构

进行数据插入和删除操作的一端称为栈顶，另一端称为栈底
**压栈：**栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶
**出栈：**栈的删除操作叫做出栈。出数据也在栈顶

栈的实现

链表实现

#include <stdio.h>

// 定义节点结构体
typedef struct Node {
    int data;
    struct Node* next;
} Node;

// 定义栈结构体
typedef struct Stack {
    Node* top;
    int size;
} Stack;

// 创建新节点
Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (!newNode) {
        printf("内存分配失败\n");
        exit(0);
    }
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// 初始化栈
void initializeStack(Stack* stack) {
    stack->top = NULL;
    stack->size = 0;
}

// 入栈
void push(Stack* stack, int data) {
    Node* newNode = createNode(data);
    newNode->next = stack->top;
    stack->top = newNode;
    stack->size++;
}

// 出栈
int pop(Stack* stack) {
    if (stack->top == NULL) {
        printf("栈为空\n");
        return -1;
    }
    Node* temp = stack->top;
    int data = temp->data;
    stack->top = stack->top->next;
    free(temp);
    stack->size--;
    return data;
}

// 查看栈顶元素
int peek(Stack* stack) {
    if (stack->top == NULL) {
        printf("栈为空\n");
        return -1;
    }
    return stack->top->data;
}

// 检查栈是否为空
int is_empty(Stack* stack) {
    return stack->size == 0;
}

// 获取栈的大小
int size(Stack* stack) {
    return stack->size;
}

int main() {
    Stack stack;
    initializeStack(&stack);

    push(&stack, 1);
    push(&stack, 2);
    push(&stack, 3);

    printf("删除数据: %d\n", pop(&stack)); // 输出 3
    printf("栈顶数据: %d\n", peek(&stack)); // 输出 2
    printf("栈大小: %d\n", size(&stack)); // 输出 2

    return 0;
}

顺序表实现

#include <stdio.h>

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

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

// 初始化栈
void initializeStack(Stack* stack) {
    stack->top = -1;
}

// 检查栈是否为空
bool is_empty(Stack* stack) {
    return stack->top == -1;
}

// 检查栈是否已满
bool is_full(Stack* stack) {
    return stack->top == MAX_SIZE - 1;
}

// 入栈
void push(Stack* stack, int item) {
    if (is_full(stack)) {
        printf("栈已满，无法添加元素\n");
        return;
    }
    stack->items[++stack->top] = item;
}

// 出栈
int pop(Stack* stack) {
    if (is_empty(stack)) {
        printf("栈为空，无法移除元素\n");
        return -1;
    }
    return stack->items[stack->top--];
}

// 查看栈顶元素
int peek(Stack* stack) {
    if (is_empty(stack)) {
        printf("栈为空\n");
        return -1;
    }
    return stack->items[stack->top];
}

// 获取栈的大小
int size(Stack* stack) {
    return stack->top + 1;
}

int main() {
    Stack stack;
    initializeStack(&stack);

    push(&stack, 1);
    push(&stack, 2);
    push(&stack, 3);

    printf("删除数据: %d\n", pop(&stack)); // 输出 3
    printf("栈顶数据: %d\n", peek(&stack)); // 输出 2
    printf("栈空间大小: %d\n", size(&stack)); // 输出 2

    return 0;
}

队列

队列的概念及结构

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出 入队列：进行插入操作的一端称为队尾 出队列：进行删除操作的一端称为队头

队列的实现

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

typedef int QDataType; // 方便修改栈内的数据类型

// 链式结构：表示队列节点
typedef struct QListNode {
    struct QListNode* _pNext;
    QDataType _data;
} QNode;

// 队列的结构
typedef struct Queue {
    QNode* _front; // 队头指针
    QNode* _rear;  // 队尾指针
} Queue;

// 初始化队列
void QueueInit(Queue* q) {
    assert(q);
    q->_front = q->_rear = NULL;
}

// 创建新节点
QNode* CreateNode(QDataType data) {
    QNode* newNode = (QNode*)malloc(sizeof(QNode));
    if (!newNode) {
        printf("内存分配失败\n");
        exit(0);
    }
    newNode->_pNext = NULL;
    newNode->_data = data;
    return newNode;
}

// 队尾入队列
void QueuePush(Queue* q, QDataType data) {
    assert(q);
    QNode* newNode = CreateNode(data);
    if (q->_rear == NULL) {
        q->_front = q->_rear = newNode;
    } else {
        q->_rear->_pNext = newNode;
        q->_rear = newNode;
    }
}

// 队头出队列
void QueuePop(Queue* q) {
    assert(q);
    if (q->_front == NULL) return;

    QNode* temp = q->_front;
    q->_front = q->_front->_pNext;
    if (q->_front == NULL) {
        q->_rear = NULL;
    }
    free(temp);
}

// 获取队列头部元素
QDataType QueueFront(Queue* q) {
    assert(q);
    if (q->_front == NULL) {
        printf("队列是空的\n");
        return -1; // 或者可以返回其他特殊值表示错误
    }
    return q->_front->_data;
}

// 获取队列队尾元素
QDataType QueueBack(Queue* q) {
    assert(q);
    if (q->_rear == NULL) {
        printf("队列是空的\n");
        return -1; // 或者可以返回其他特殊值表示错误
    }
    return q->_rear->_data;
}

// 获取队列中有效元素个数
int QueueSize(Queue* q) {
    assert(q);
    int size = 0;
    QNode* cur = q->_front;
    while (cur) {
        size++;
        cur = cur->_pNext;
    }
    return size;
}

// 检测队列是否为空，如果为空返回非零结果，如果非空返回0
int QueueEmpty(Queue* q) {
    assert(q);
    return q->_front == NULL;
}

// 销毁队列
void QueueDestroy(Queue* q) {
    assert(q);
    QNode* cur = q->_front;
    while (cur) {
        QNode* del = cur;
        cur = cur->_pNext;
        free(del);
    }
    q->_front = q->_rear = NULL;
}

int main() {
    Queue q;
    QueueInit(&q);

    QueuePush(&q, 1);
    QueuePush(&q, 2);
    QueuePush(&q, 3);
        
    printf("队头数据: %d\n", QueueFront(&q)); // 输出 1
    printf("队尾数据: %d\n", QueueBack(&q));   // 输出 3
    printf("队列大小: %d\n", QueueSize(&q));   // 输出 3

    QueuePop(&q);
    printf("删除后的队列头数据: %d\n", QueueFront(&q)); // 输出 2

    QueueDestroy(&q);

    return 0;
}