栈、队列和数组可执行代码
- 栈--顺序表
#include <iostream>
// 定义栈中元素的最大个数
#define MAX_SIZE 10
typedef struct {
char data[MAX_SIZE];
int top;
} SqStack;
// 初始化栈
void Stack_Init(SqStack &S) {
S.top = -1; // 初始化栈顶指针为-1，表示栈为空
}
// 判断栈是否为空
bool Stack_Empty(SqStack S) {
return S.top == -1;
}
// 判断栈是否已满
bool Stack_Full(SqStack S) {
return S.top == MAX_SIZE - 1;
}
// 新元素入栈
bool Stack_Push(SqStack &S, char x) {
if (Stack_Full(S)) {
std::cout << "栈已满，无法入栈" << std::endl;
return false;
} else {
S.data[++S.top] = x; // 将元素入栈，并更新栈顶指针
return true;
}
}
// 栈顶元素出栈，x为出栈的栈顶元素
bool Stack_Pop(SqStack &S, char &x) {
if (Stack_Empty(S)) {
std::cout << "栈为空，无法出栈" << std::endl;
return false;
} else {
x = S.data[S.top--]; // 将栈顶元素出栈，并更新栈顶指针
return true;
}
}
int main() {
SqStack stack;
Stack_Init(stack);
// 测试入栈操作
for (char c = 'A'; c <= 'J'; ++c) {
if (!Stack_Push(stack, c)) {
std::cout << "入栈失败，栈已满" << std::endl;
break;
}
}
// 测试出栈操作
char x;
while (Stack_Pop(stack, x)) {
std::cout << "出栈元素: " << x << std::endl;
}
return 0;
}
- 栈-链表-带头结点
#include <stdio.h>
#include<stdlib.h>
typedef struct LNode {
int data;
struct LNode * next;
} LNode, *LinkStack;
// 初始化栈
bool Stack_Init (LinkStack &pStack) {
pStack = (LNode *) malloc(sizeof(LNode));
if (pStack == NULL) return false;
pStack->next = NULL;
// 头结点存储栈长度
pStack->data = 0;
return true;
}
// 判断栈是否为空
bool Stack_Empty (LinkStack pStack) {
// 或 pStack->data == 0;
return pStack->next == NULL;
}
// 获取栈有效数据节点个数
int Stack_Length (LinkStack pStack)
{
return pStack->data;
}
// 创建栈
LinkStack Stack_Create(LinkStack &pStack) {
LNode *pTemp; int x;
scanf("%d", &x);
while (x != 999) {
pTemp = (LNode *)malloc(sizeof(LNode));
pTemp->data = x;
pTemp->next = pStack->next;
pStack->next = pTemp;
pStack->data += 1;
scanf("%d", &x);
}
return pStack;
}
// 新元素入栈
bool Stack_Push(LinkStack &pStack, int e) {
LNode *pTemp = (LNode *)malloc(sizeof(LNode));
pTemp->data = e;
pTemp->next = pStack->next;
pStack->next = pTemp;
pStack->data += 1;
return true;
}
// 出栈
bool Stack_Pop (LinkStack &pStack, int &e) {
if (pStack->next == NULL) return false;
LNode *p = pStack->next; // 待删除结点
pStack->next = p->next;
e = p->data;
free(p);
pStack->data -= 1;
return true;
}
// 返回第一个
LNode* Stack_Get_Top (LinkStack pStack) {
return pStack->next;
}
// 打印栈所有值
void Stack_Show (LinkStack pStack) {
LNode *node = pStack->next;
printf("栈值：");
while (node != NULL) {
printf("%d、", node->data);
node = node->next;
}
printf("\n");
}
int main () {
int i = -1;
LinkStack pStack;
Stack_Init(pStack);
printf("栈判空：%s\n", Stack_Empty(pStack) ? "空" : "非空");
Stack_Create(pStack);
Stack_Show(pStack);
printf("栈长度：%d\n\n", Stack_Length(pStack));
printf("入栈：0\n");
Stack_Push(pStack, 0);
Stack_Show(pStack);
printf("栈长度：%d\n\n", Stack_Length(pStack));
printf("入栈：99\n");
Stack_Push(pStack, 99);
Stack_Show(pStack);
printf("栈长度：%d\n\n", Stack_Length(pStack));
Stack_Pop(pStack, i);
printf("出栈：%d\n", i);
Stack_Show(pStack);
printf("栈长度：%d\n\n", Stack_Length(pStack));
Stack_Pop(pStack, i);
printf("出栈：%d\n", i);
Stack_Show(pStack);
printf("栈长度：%d\n\n", Stack_Length(pStack));
LNode *top = Stack_Get_Top(pStack);
printf("获取栈顶元素：%d\n\n", top == NULL ? -1 : top->data);
printf("栈判空：%s\n", Stack_Empty(pStack) ? "空" : "非空");
return 0;
}
- 栈-链表-不带头结点
#include <stdio.h>
#include <stdlib.h>
typedef struct LNode {
int data;
struct LNode *next;
} LNode, *LinkStack;
// 初始化栈
bool Stack_Init(LinkStack &pStack) {
pStack = NULL;
return true;
}
// 判断栈是否为空
bool Stack_Empty(LinkStack pStack) {
return pStack == NULL;
}
// 获取栈有效数据节点个数
int Stack_Length(LinkStack pStack) {
int length = 0;
LNode *current = pStack;
while (current != NULL) {
length++;
current = current->next;
}
return length;
}
// 创建栈
LinkStack Stack_Create(LinkStack &pStack) {
LNode *pTemp;
int x;
scanf("%d", &x);
while (x != 999) {
pTemp = (LNode *)malloc(sizeof(LNode));
pTemp->data = x;
pTemp->next = pStack;
pStack = pTemp;
scanf("%d", &x);
}
return pStack;
}
// 新元素入栈
bool Stack_Push(LinkStack &pStack, int e) {
LNode *pTemp = (LNode *)malloc(sizeof(LNode));
pTemp->data = e;
pTemp->next = pStack;
pStack = pTemp;
return true;
}
// 出栈
bool Stack_Pop(LinkStack &pStack, int &e) {
if (pStack == NULL) return false;
LNode *p = pStack;
e = p->data;
pStack = pStack->next;
free(p);
return true;
}
// 返回第一个
LNode *Stack_Get_Top(LinkStack pStack) {
return pStack;
}
// 打印栈所有值
void Stack_Show(LinkStack pStack) {
LNode *node = pStack;
printf("栈值：");
while (node != NULL) {
printf("%d、", node->data);
node = node->next;
}
printf("\n");
}
int main() {
int i = -1;
LinkStack pStack;
Stack_Init(pStack);
printf("栈判空：%s\n", Stack_Empty(pStack) ? "空" : "非空");
Stack_Push(pStack, 1);
Stack_Push(pStack, 2);
Stack_Push(pStack, 3);
Stack_Push(pStack, 4);
Stack_Show(pStack);
Stack_Pop(pStack, i);
printf("出栈：%d\n", i);
Stack_Show(pStack);
Stack_Pop(pStack, i);
printf("出栈：%d\n", i);
Stack_Show(pStack);
Stack_Pop(pStack, i);
printf("出栈：%d\n", i);
Stack_Show(pStack);
printf("栈长度：%d\n\n", Stack_Length(pStack));
printf("栈判空：%s\n", Stack_Empty(pStack) ? "空" : "非空");
return 0;
}
- 队列-顺序表
#include <stdio.h>
#define MAX_SIZE 100
typedef int ElemType; // 假设队列中存储的元素类型是整数
typedef struct {
ElemType data[MAX_SIZE]; // 存储队列元素的数组
int front, rear; // 队列的队头和队尾指针
} SqQueue;
// 初始化队列
void Queue_Init(SqQueue &Q) {
Q.front = Q.rear = 0;
}
// 判断队列是否为空
int Queue_IsEmpty(SqQueue &Q) {
return Q.front == Q.rear;
}
// 判断队列是否已满
int Queue_IsFull(SqQueue &Q) {
return Q.rear == MAX_SIZE - 1;
}
// 入队操作
int Queue_En(SqQueue &Q, ElemType x) {
if (Q.rear == MAX_SIZE - 1) {
printf("队列已满，无法入队\n");
return 0; // 入队失败
}
Q.data[Q.rear] = x;
Q.rear++; // 队尾指针增加
return 1; // 入队成功
}
// 出队操作
int Queue_De(SqQueue &Q, ElemType &x) {
if (Q.front == Q.rear) {
printf("队列为空，无法出队\n");
return 0; // 出队失败
}
x = Q.data[Q.front];
Q.front++; // 队头指针增加
return 1; // 出队成功
}
// 输出队列中的元素
void Queue_Print(SqQueue &Q) {
int i;
for (i = Q.front; i < Q.rear; i++) {
printf("%d ", Q.data[i]);
}
printf("\n");
}
int main() {
SqQueue Q;
Queue_Init(Q);
Queue_En(Q, 1);
Queue_En(Q, 2);
Queue_En(Q, 3);
printf("队列元素: ");
Queue_Print(Q);
ElemType x;
Queue_De(Q, x);
printf("出队元素：%d\n", x);
printf("队列元素: ");
Queue_Print(Q);
return 0;
}
- 队列-链表-带头结点
#include <stdio.h>
#include<stdlib.h>
typedef struct LNode {
int data;
struct LNode * next;
} LNode;
typedef struct {
LNode * front, *rear; // 队头、队尾
int len; // 当前队列的成员数
} LinkQueue;
// 初始化队列（带头结点）
bool Queue_Init (LinkQueue &Q) {
Q.front = Q.rear = (LNode *)malloc(sizeof(LNode));
Q.front->next = NULL;
Q.len = 0;
return true;
}
// 判断队列是否为空
bool Queue_Empty (LinkQueue Q) {
return Q.front == Q.rear;
}
// 获取队列有效数据节点个数
int Queue_Length (LinkQueue Q) {
return Q.len;
}
// 创建队列
LinkQueue Queue_Create(LinkQueue &Q) {
LNode *pTemp; int x;
scanf("%d", &x);
while (x != 999) {
pTemp = (LNode *)malloc(sizeof(LNode));
pTemp->data = x;
pTemp->next = NULL;
Q.rear->next = pTemp;
Q.rear = pTemp;
Q.len += 1;
scanf("%d", &x);
}
return Q;
}
// 新元素入队
bool Queue_En(LinkQueue &Q, int e) {
LNode *pTemp = (LNode *)malloc(sizeof(LNode));
pTemp->data = e;
pTemp->next = NULL;
Q.rear->next = pTemp;
Q.rear = pTemp;
Q.len += 1;
return true;
}
// 出队
bool Queue_De (LinkQueue &Q, int &e) {
if (Q.front == Q.rear) return false;
LNode *p = Q.front->next; // 待删除结点
Q.front->next = p->next;
e = p->data;
if (Q.rear == p) // 删除的为最后一个结点
Q.rear = Q.front;
free(p);
Q.len -= 1;
return true;
}
// 打印队列所有值
void Queue_Show (LinkQueue Q) {
LNode *node = Q.front->next;
printf("队列值：");
while (node != NULL) {
printf("%d、", node->data);
node = node->next;
}
printf("\n");
}
int main () {
int i = -1;
LinkQueue Q;
Queue_Init(Q);
printf("队列判空：%s\n", Queue_Empty(Q) ? "空" : "非空");
Queue_Create(Q);
Queue_Show(Q);
printf("队列长度：%d\n\n", Queue_Length(Q));
printf("入队列：0\n");
Queue_En(Q, 0);
Queue_Show(Q);
printf("队列长度：%d\n\n", Queue_Length(Q));
printf("入队列：99\n");
Queue_En(Q, 99);
Queue_Show(Q);
printf("队列长度：%d\n\n", Queue_Length(Q));
Queue_De(Q, i);
printf("出队列值：%d\n", i);
Queue_Show(Q);
printf("队列长度：%d\n\n", Queue_Length(Q));
Queue_De(Q, i);
printf("出队列值：%d\n", i);
Queue_Show(Q);
printf("队列长度：%d\n\n", Queue_Length(Q));
printf("队列判空：%s\n", Queue_Empty(Q) ? "空" : "非空");
return 0;
}
- 队列-链表-不带头结点
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
typedef struct LNode {
int data;
struct LNode* next;
} LNode;
typedef struct {
LNode* front; // 队头
LNode* rear; // 队尾
int len; // 当前队列的成员数
} LinkQueue;
// 初始化队列（不带头结点）
bool Queue_Init(LinkQueue* Q) {
Q->front = Q->rear = NULL;
Q->len = 0;
return true;
}
// 判断队列是否为空
bool Queue_Empty(LinkQueue* Q) {
return Q->front == NULL;
}
// 获取队列有效数据节点个数
int Queue_Length(LinkQueue* Q) {
return Q->len;
}
// 创建队列
void Queue_Create(LinkQueue* Q) {
int x;
scanf("%d", &x);
while (x != 999) {
LNode* pTemp = (LNode*)malloc(sizeof(LNode));
pTemp->data = x;
pTemp->next = NULL;
if (Q->rear == NULL) {
Q->front = Q->rear = pTemp;
} else {
Q->rear->next = pTemp;
Q->rear = pTemp;
}
Q->len += 1;
scanf("%d", &x);
}
}
// 新元素入队
bool Queue_En(LinkQueue* Q, int e) {
LNode* pTemp = (LNode*)malloc(sizeof(LNode));
pTemp->data = e;
pTemp->next = NULL;
if (Q->front == NULL) {
Q->front = pTemp;
Q->rear = pTemp;
} else {
Q->rear->next = pTemp;
Q->rear = pTemp;
}
Q->len += 1;
return true;
}
// 出队
bool Queue_De(LinkQueue* Q, int* e) {
if (Q->front == NULL) return false;
LNode* p = Q->front;
Q->front = p->next;
*e = p->data;
Q->len -= 1;
if (Q->front == NULL) {
Q->rear = NULL;
}
free(p);
return true;
}
// 打印队列所有值
void Queue_Show(LinkQueue* Q) {
LNode* node = Q->front;
printf("队列值：");
while (node != NULL) {
printf("%d、", node->data);
node = node->next;
}
printf("\n");
}
int main() {
int i = -1;
LinkQueue Q;
Queue_Init(&Q);
printf("队列判空：%s\n", Queue_Empty(&Q) ? "空" : "非空");
Queue_En(&Q, 10);
Queue_En(&Q, 20);
Queue_En(&Q, 30);
Queue_En(&Q, 40);
Queue_En(&Q, 50);
Queue_Show(&Q);
printf("队列长度：%d\n\n", Queue_Length(&Q));
Queue_De(&Q, &i);
printf("出队列值：%d\n", i);
Queue_Show(&Q);
printf("队列长度：%d\n\n", Queue_Length(&Q));
Queue_De(&Q, &i);
printf("出队列值：%d\n", i);
Queue_Show(&Q);
printf("队列长度：%d\n\n", Queue_Length(&Q));
printf("队列判空：%s\n", Queue_Empty(&Q) ? "空" : "非空");
return 0;
}
- 队列-顺序表-循环队列
#include <stdio.h>
#include <stdlib.h>
#define ElemType int
#define MAX_SIZE 10
typedef struct {
ElemType data[MAX_SIZE]; // 存储队列元素的数组
int front, rear; // 队列的前端和后端指针
} SqQueue;
// 初始化队列
void Queue_Init(SqQueue &Q) {
Q.rear = 0; // 初始化队尾指针
Q.front = 0; // 初始化队头指针
}
// 检查队列是否为空
bool Queue_IsEmpty(SqQueue Q) {
if (Q.rear == Q.front)
return true; // 队列为空
else
return false; // 队列不为空
}
// 入队操作，将元素 x 添加到队列尾部
bool Queue_En(SqQueue &Q, ElemType x) {
// 检查队列是否已满，如果队尾指针的下一个位置等于队头指针，表示队列已满
if ((Q.rear + 1) % MAX_SIZE == Q.front) {
return false; // 队列已满，无法入队，返回 false
}
Q.data[Q.rear] = x; // 将元素 x 存储在队列尾部
Q.rear = (Q.rear + 1) % MAX_SIZE; // 更新队尾指针，实现循环队列，即如果到达数组末尾，循环回到数组开头
return true; // 入队成功，返回 true
}
// 出队操作，将队列头部元素存储在 x 中，并从队列中删除
bool Queue_De(SqQueue &Q, ElemType &x) {
// 检查队列是否为空，如果队尾指针等于队头指针，表示队列为空
if (Q.rear == Q.front)
return false; // 队列为空，无法出队，返回 false
x = Q.data[Q.front]; // 将队头元素存储在 x 中
Q.front = (Q.front + 1) % MAX_SIZE; // 更新队头指针，实现循环队列，即如果到达数组末尾，循环回到数组开头
return true; // 出队成功，返回 true
}
int main() {
SqQueue myQueue;
Queue_Init(myQueue); // 初始化队列
// 入队操作
for (int i = 1; i <= 5; ++i) {
Queue_En(myQueue, i * 10);
}
// 出队操作
while (!Queue_IsEmpty(myQueue)) {
ElemType frontElem;
Queue_De(myQueue, frontElem);
printf("出队元素：%d\n", frontElem);
}
return 0;
}
- 栈-括号匹配-顺序表
#include <iostream>
// 定义栈中元素的最大个数
#define MAX_SIZE 10
typedef struct {
char data[MAX_SIZE];
int top;
} SqStack;
// 初始化栈
void Stack_Init(SqStack &S) {
S.top = -1; // 初始化栈顶指针为-1，表示栈为空
}
// 判断栈是否为空
bool Stack_Empty(SqStack S) {
return S.top == -1;
}
// 判断栈是否已满
bool Stack_Full(SqStack S) {
return S.top == MAX_SIZE - 1;
}
// 新元素入栈
bool Stack_Push(SqStack &S, char x) {
if (Stack_Full(S)) {
std::cout << "栈已满，无法入栈" << std::endl;
return false;
} else {
S.data[++S.top] = x; // 将元素入栈，并更新栈顶指针
return true;
}
}
// 栈顶元素出栈，x为出栈的栈顶元素
bool Stack_Pop(SqStack &S, char &x) {
if (Stack_Empty(S)) {
std::cout << "栈为空，无法出栈" << std::endl;
return false;
} else {
x = S.data[S.top--]; // 将栈顶元素出栈，并更新栈顶指针
return true;
}
}
// 括号匹配函数
bool Bracket_Match(char str[], int n) {
SqStack S; // 创建一个栈
Stack_Init(S); // 初始化栈
for (int i = 0; i < n; i++) { // 遍历输入的字符数组
if (str[i] == '(' || str[i] == '[' || str[i] == '{') {
// 如果遇到左括号 (、[、{，则将其入栈
Stack_Push(S, str[i]);
} else {
if (Stack_Empty(S)) {
// 如果遇到右括号但栈为空，说明无法匹配，返回false
return false;
}
char topElem;
Stack_Pop(S, topElem); // 弹出栈顶元素，与当前右括号进行匹配
// 检查栈顶元素与当前右括号是否匹配，不匹配则返回false
if (str[i] == ')' && topElem != '(')
return false;
if (str[i] == ']' && topElem != '[')
return false;
if (str[i] == '}' && topElem != '{')
return false;
}
}
// 所有字符处理完毕后，如果栈为空，表示括号匹配成功
return Stack_Empty(S);
}
int main() {
char str[] = "{[()]}";
int n = strlen(str);
if (Bracket_Match(str, n)) {
std::cout << "括号匹配成功" << std::endl;
} else {
std::cout << "括号匹配失败" << std::endl;
}
return 0;
}
- 栈-表达式计算-顺序表
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_EXPR_SIZE 100
// 函数用于返回操作符的优先级
int precedence(char c) {
if (c == '^')
return 3;
else if (c == '/' || c == '*')
return 2;
else if (c == '+' || c == '-')
return 1;
else
return -1; // 非操作符的情况
}
// 函数用于检查字符是否为操作符
int isOperator(char ch) {
return (
ch == '+'
|| ch == '-'
|| ch == '*'
|| ch == '/'
|| ch == '^'
);
}
// 函数用于反转字符串
void reverseString(char *str) {
int len = strlen(str);
for (int i = 0; i < len / 2; i++) {
char temp = str[i];
str[i] = str[len - i - 1];
str[len - i - 1] = temp;
}
}
// 函数用于替换括号，将'('替换为')'，将')'替换为'('
void replaceParentheses(char *str) {
int len = strlen(str);
for (int i = 0; i < len; i++) {
if (str[i] == '(') {
str[i] = ')';
} else if (str[i] == ')') {
str[i] = '(';
}
}
}
// 函数用于将中缀表达式转换为后缀表达式
bool infixToPostfix(char* infix, char* postfix) {
int i, j;
int len = strlen(infix);
char stack[MAX_EXPR_SIZE];
int top = -1;
for (i = 0, j = 0; i < len; i++) {
if (infix[i] == ' ' || infix[i] == '\t')
continue;
// 如果扫描到的字符是操作数，将其添加到后缀表达式
if (
(infix[i] >= 'a' && infix[i] <= 'z')
|| (infix[i] >= 'A' && infix[i] <= 'Z')
|| (infix[i] >= '0' && infix[i] <= '9')
) {
postfix[j++] = infix[i];
}
// 如果扫描到'('，将其压入栈中
else if (infix[i] == '(') {
stack[++top] = infix[i];
}
// 如果扫描到')'，则弹出栈中的元素并添加到输出字符串，直到找到'('
else if (infix[i] == ')') {
// 当扫描到的字符为')'时，需要将栈中的操作符弹出并添加到后缀表达式中，直到遇到'('
while (top > -1 && stack[top] != '(') {
postfix[j++] = stack[top--];
}
// 如果在上述循环结束后，栈顶仍然不是'('，则括号不匹配，返回false
if (top == -1 || stack[top] != '(') {
return false; // 括号不匹配的情况
} else {
top--; // 如果栈顶是'('，则将'('弹出栈
}
}
// 如果扫描到操作符，将其压入栈中，但需要根据优先级进行处理
else if (isOperator(infix[i])) {
// 当栈不为空且栈顶操作符的优先级大于等于当前扫描到的操作符时，将栈顶操作符弹出并添加到后缀表达式中
while (top > -1 && precedence(stack[top]) >= precedence(infix[i]))
postfix[j++] = stack[top--];
stack[++top] = infix[i];
}
}
// 弹出栈中剩余的元素
while (top > -1) {
if (stack[top] == '(') {
return false; // 括号不匹配的情况
}
postfix[j++] = stack[top--];
}
postfix[j] = '';
return true;
}
// 函数用于将中缀表达式转换为前缀表达式
void infixToPrefix(char *infix, char *prefix) {
int len = strlen(infix);
// 1. 反转中缀表达式
reverseString(infix);
// 2. 替换括号
replaceParentheses(infix);
// 3. 获取后缀表达式（这里实际上调用了中缀转后缀的函数）
infixToPostfix(infix, prefix);
// 4. 反转后缀表达式，得到前缀表达式
reverseString(prefix);
}
// 主函数
int main() {
char infix[MAX_EXPR_SIZE] = "A+B*(C-D)-E/F";
// char infix[MAX_EXPR_SIZE] = "((15/(7-(1+1)))*3)-(2+(1+1))";
printf("中缀表达式: %s\n", infix);
char postfix[MAX_EXPR_SIZE];
char prefix[MAX_EXPR_SIZE];
// 调用中缀转后缀函数
infixToPostfix(infix, postfix);
printf("后缀表达式(左优先): %s\n", postfix);
// 调用中缀转前缀函数
infixToPrefix(infix, prefix);
printf("前缀表达式(右优先): %s\n", prefix);
return 0;
}
- 队列-双端队列
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100 // 双端队列的最大容量
// 双端队列结构体
typedef struct {
int data[MAX_SIZE];
int front; // 队列头指针
int rear; // 队列尾指针
} Deque;
// 初始化双端队列
void Deque_Init(Deque &Q) {
Q.front = 0; // 头指针指向0
Q.rear = 0; // 尾指针指向0
}
// 判断双端队列是否为空
int isEmpty(Deque &Q) {
return (Q.front == Q.rear);
}
// 判断双端队列是否已满
int isFull(Deque &Q) {
return (Q.front == (Q.rear + 1) % MAX_SIZE);
}
// 在队头插入元素
void Deque_InsertFront(Deque &Q, int element) {
if (Q.front == (Q.rear + 1) % MAX_SIZE) {
printf("双端队列已满，无法插入元素\n");
}
// 注意是先移动，在插值。和在队尾插入元素是相反的
Q.front = (Q.front - 1 + MAX_SIZE) % MAX_SIZE; // 循环向前移动头指针
Q.data[Q.front] = element; // 在队头插入元素
}
// 在队尾插入元素
void Deque_InsertRear(Deque &Q, int element) {
if (Q.front == (Q.rear + 1) % MAX_SIZE) {
printf("双端队列已满，无法插入元素\n");
}
Q.data[Q.rear] = element; // 在队尾插入元素
Q.rear = (Q.rear + 1) % MAX_SIZE; // 循环向后移动尾指针
}
// 从队头删除元素
int Deque_DeleteFront(Deque &Q) {
if (Q.front == Q.rear) {
printf("双端队列为空，无法删除元素\n");
return -1; // 返回一个特殊值表示错误
}
int element = Q.data[Q.front];
Q.front = (Q.front + 1) % MAX_SIZE; // 循环向后移动头指针
return element;
}
// 从队尾删除元素
int Deque_DeleteRear(Deque &Q) {
if (Q.front == Q.rear) {
printf("双端队列为空，无法删除元素\n");
return -1; // 返回一个特殊值表示错误
}
Q.rear = (Q.rear - 1 + MAX_SIZE) % MAX_SIZE; // 循环向前移动尾指针
return Q.data[Q.rear];
}
void Deque_print (Deque Q) {
// 输出队列中的值
printf("队列中的值: ");
int i;
for (i = Q.front; i != Q.rear; i = (i + 1) % MAX_SIZE) {
printf("%d ", Q.data[i]);
}
printf("\n");
}
int main() {
Deque Q;
Deque_Init(Q);
// 在队头插入元素
Deque_InsertFront(Q, 1);
Deque_InsertFront(Q, 2);
// 在队尾插入元素
Deque_InsertRear(Q, 3);
Deque_InsertRear(Q, 4);
Deque_print(Q);
// 从队头删除元素
int frontElement = Deque_DeleteFront(Q);
printf("从队头删除元素: %d\n", frontElement);
Deque_print(Q);
// 从队尾删除元素
int rearElement = Deque_DeleteRear(Q);
printf("从队尾删除元素: %d\n", rearElement);
Deque_print(Q);
return 0;
}
- 队列-层次遍历
#include <stdio.h>
#include <stdlib.h>
// 树存储结构
typedef struct BiTNode {
int data;
struct BiTNode *lchild, *rchild; // 左右孩子指针
} BiTNode, * BiTree;
// 循环队列算法，辅助完成二叉树层次遍历
#define MaxSize 50 // 定义队列中元素的最大个数
typedef struct {
BiTree data[MaxSize]; // 存放队列元素
int front, rear; // 队头和队尾指针
} SqQueue;
// 初始化队列（带头结点）
void Queue_Init(SqQueue &Q) {
Q.rear = Q.front = 0;
}
// 判断队列是否为空
bool Queue_Empty(SqQueue Q) {
return Q.front == Q.rear;
}
// 入队
bool Queue_En(SqQueue &Q, BiTree e) {
if ((Q.rear + 1) % MaxSize == Q.front) return false; // 队满则报错
Q.data[Q.rear] = e;
Q.rear = (Q.rear + 1) % MaxSize; // 队尾指针加 1 取模
return true;
}
// 出队
bool Queue_De(SqQueue &Q, BiTree &e) {
if (Queue_Empty(Q)) return false; // 队空则报错
e = Q.data[Q.front];
Q.front = (Q.front + 1) % MaxSize;
return true;
}
// 通过给定数组创建二叉树，0为空结点
// nums 为数组、len 为数组长度、i 为当前数组下标
BiTNode * BiTree_Create (char* nums, int len , int i) {
if (i >= len || nums[i] == 0) return NULL;
BiTNode * node = (BiTNode *)malloc(sizeof(BiTNode));
node->data = nums[i];
node->lchild = BiTree_Create(nums, len, 2 * i + 1);
node->rchild = BiTree_Create(nums, len, 2 * i + 2);
return node;
}
// 先序遍历: 根左右(NLR)
void Order_Pre(BiTree tree) {
if(tree == NULL) return;
printf("%d,", tree->data); // 访问根树内容
Order_Pre(tree->lchild); // 递归遍历左子树
Order_Pre(tree->rchild); // 递归遍历右子树
}
// 中序遍历: 左根右(LNR)
void Order_In(BiTree tree) {
if(tree == NULL) return;
Order_In(tree->lchild); // 递归遍历左子树
printf("%d,", tree->data); // 访问根树内容
Order_In(tree->rchild); // 递归遍历右子树
}
// 后序遍历: 左根右(LRN)
void Order_Post(BiTree tree) {
if(tree == NULL) return;
Order_Post(tree->lchild); // 递归遍历左子树
Order_Post(tree->rchild); // 递归遍历右子树
printf("%d,", tree->data); // 访问根树内容
}
// 层次遍历
void Order_Level (BiTree tree) {
SqQueue Q; // 初始化队列
Queue_Init(Q);
BiTree p;
Queue_En(Q, tree); // 根节点入队
while (!Queue_Empty(Q)) { // 队列不空则继续遍历
Queue_De(Q, p); // 队头结点出队
printf("%d,", p->data); // 访问出队结点内容
if (p->lchild != NULL)
Queue_En(Q, p->lchild); // 左子树不为空，则左子树根入队
if (p->rchild != NULL)
Queue_En(Q, p->rchild); // 右子树不为空，则右子树根入队
}
}
int main() {
char nums[11] = {1, 2, 3, 0, 4, 0, 5, 0, 0, 6, 0};
BiTree tree = BiTree_Create(nums, 11, 0);
printf("先序遍历：");
Order_Pre(tree);
printf("\n");
printf("中序遍历：");
Order_In(tree);
printf("\n");
printf("后序遍历：");
Order_Post(tree);
printf("\n");
// 层次遍历需要借助队列实现
printf("层次遍历: ");
Order_Level(tree);
return 0;
}