【“栈、队列”的应用】408数据结构代码

王道数据结构强化课——【“栈、队列”的应用】代码，持续更新

链式存储栈（单链表实现），并基于上述定义，栈顶在链头，实现“出栈、入栈、判空、判满”四个基本操作

#include <stdio.h>
#include <stdlib.h>// 定义链表节点
struct Node {int data;struct Node* next;
};// 定义栈结构
struct Stack {struct Node* top; // 栈顶指针
};// 初始化栈
void initStack(struct Stack* stack) {stack->top = NULL;
}// 入栈操作
void push(struct Stack* stack, int value) {struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));if (newNode == NULL) {printf("内存分配失败，无法执行入栈操作\n");return;}newNode->data = value;newNode->next = stack->top;stack->top = newNode;
}// 出栈操作
int pop(struct Stack* stack) {if (stack->top == NULL) {printf("栈为空，无法执行出栈操作\n");return -1; // 返回一个错误值}struct Node* temp = stack->top;int poppedValue = temp->data;stack->top = temp->next;free(temp);return poppedValue;
}// 判空操作
int isEmpty(struct Stack* stack) {return (stack->top == NULL);
}// 判满操作（对于链式存储的栈，通常不会满，所以返回0表示不满）
int isFull(struct Stack* stack) {return 0;
}// 释放栈内存
void freeStack(struct Stack* stack) {while (stack->top != NULL) {struct Node* temp = stack->top;stack->top = temp->next;free(temp);}
}int main() {struct Stack stack;initStack(&stack);// 入栈操作push(&stack, 1);push(&stack, 2);push(&stack, 3);// 出栈操作printf("出栈操作: %d\n", pop(&stack));// 判空操作printf("栈是否为空: %s\n", isEmpty(&stack) ? "是" : "否");// 判满操作printf("栈是否满: %s\n", isFull(&stack) ? "是" : "否");// 释放栈内存freeStack(&stack);return 0;
}

链式存储栈（双向链表实现）

#include <stdio.h>
#include <stdlib.h>// 定义链表节点
struct Node {int data;struct Node* next;struct Node* prev;
};// 定义栈结构
struct Stack {struct Node* top; // 栈顶指针，链尾
};// 初始化栈
void initStack(struct Stack* stack) {stack->top = NULL;
}// 入栈操作
void push(struct Stack* stack, int value) {struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));if (newNode == NULL) {printf("内存分配失败，无法执行入栈操作\n");return;}newNode->data = value;newNode->next = NULL;if (stack->top == NULL) {newNode->prev = NULL;stack->top = newNode;} else {newNode->prev = stack->top;stack->top->next = newNode;stack->top = newNode;}
}// 出栈操作
int pop(struct Stack* stack) {if (stack->top == NULL) {printf("栈为空，无法执行出栈操作\n");return -1; // 返回一个错误值}struct Node* temp = stack->top;int poppedValue = temp->data;if (stack->top->prev != NULL) {stack->top = stack->top->prev;stack->top->next = NULL;} else {stack->top = NULL;}free(temp);return poppedValue;
}// 判空操作
int isEmpty(struct Stack* stack) {return (stack->top == NULL);
}// 判满操作（对于链式存储的栈，通常不会满，所以返回0表示不满）
int isFull(struct Stack* stack) {return 0;
}// 释放栈内存
void freeStack(struct Stack* stack) {while (stack->top != NULL) {struct Node* temp = stack->top;stack->top = temp->prev;free(temp);}
}int main() {struct Stack stack;initStack(&stack);// 入栈操作push(&stack, 1);push(&stack, 2);push(&stack, 3);// 出栈操作printf("出栈操作: %d\n", pop(&stack));// 判空操作printf("栈是否为空: %s\n", isEmpty(&stack) ? "是" : "否");// 判满操作printf("栈是否满: %s\n", isFull(&stack) ? "是" : "否");// 释放栈内存freeStack(&stack);return 0;
}

顺序存储的队列（数组实现）

#include <stdio.h>
#include <stdlib.h>#define MAX_QUEUE_SIZE 10 // 队列的最大容量// 定义队列结构
struct Queue {int front, rear; // 前后指针int data[MAX_QUEUE_SIZE];
};// 初始化队列
void initQueue(struct Queue* queue) {queue->front = -1;queue->rear = -1;
}// 判空操作
int isEmpty(struct Queue* queue) {return (queue->front == -1);
}// 判满操作
int isFull(struct Queue* queue) {return ((queue->rear + 1) % MAX_QUEUE_SIZE == queue->front);
}// 入队操作
void enqueue(struct Queue* queue, int value) {if (isFull(queue)) {printf("队列已满，无法执行入队操作\n");return;}if (isEmpty(queue)) {queue->front = 0;}queue->rear = (queue->rear + 1) % MAX_QUEUE_SIZE;queue->data[queue->rear] = value;
}// 出队操作
int dequeue(struct Queue* queue) {if (isEmpty(queue)) {printf("队列为空，无法执行出队操作\n");return -1; // 返回一个错误值}int dequeuedValue = queue->data[queue->front];if (queue->front == queue->rear) {// 队列中只有一个元素，出队后队列为空queue->front = -1;queue->rear = -1;} else {queue->front = (queue->front + 1) % MAX_QUEUE_SIZE;}return dequeuedValue;
}int main() {struct Queue queue;initQueue(&queue);// 入队操作enqueue(&queue, 1);enqueue(&queue, 2);enqueue(&queue, 3);// 出队操作printf("出队操作: %d\n", dequeue(&queue));// 判空操作printf("队列是否为空: %s\n", isEmpty(&queue) ? "是" : "否");// 判满操作printf("队列是否满: %s\n", isFull(&queue) ? "是" : "否");return 0;
}

链式存储队列（单链表实现）

#include <stdio.h>
#include <stdlib.h>// 定义链表节点
struct Node {int data;struct Node* next;
};// 定义队列结构
struct Queue {struct Node* front; // 队列前端struct Node* rear;  // 队列后端
};// 初始化队列
void initQueue(struct Queue* queue) {queue->front = NULL;queue->rear = NULL;
}// 判空操作
int isEmpty(struct Queue* queue) {return (queue->front == NULL);
}// 判满操作（对于链式存储的队列，通常不会满，所以返回0表示不满）
int isFull(struct Queue* queue) {return 0;
}// 入队操作
void enqueue(struct Queue* queue, int value) {struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));if (newNode == NULL) {printf("内存分配失败，无法执行入队操作\n");return;}newNode->data = value;newNode->next = NULL;if (isEmpty(queue)) {queue->front = newNode;} else {queue->rear->next = newNode;}queue->rear = newNode;
}// 出队操作
int dequeue(struct Queue* queue) {if (isEmpty(queue)) {printf("队列为空，无法执行出队操作\n");return -1; // 返回一个错误值}struct Node* temp = queue->front;int dequeuedValue = temp->data;queue->front = temp->next;free(temp);if (queue->front == NULL) {// 如果出队后队列为空，需要更新rear指针queue->rear = NULL;}return dequeuedValue;
}// 释放队列内存
void freeQueue(struct Queue* queue) {while (queue->front != NULL) {struct Node* temp = queue->front;queue->front = temp->next;free(temp);}
}int main() {struct Queue queue;initQueue(&queue);// 入队操作enqueue(&queue, 1);enqueue(&queue, 2);enqueue(&queue, 3);// 出队操作printf("出队操作: %d\n", dequeue(&queue));// 判空操作printf("队列是否为空: %s\n", isEmpty(&queue) ? "是" : "否");// 判满操作printf("队列是否满: %s\n", isFull(&queue) ? "是" : "否");// 释放队列内存freeQueue(&queue);return 0;
}