C语言顺序栈和循环队列基本运算实现

本项目使用C语言实现了顺序栈和循环队列的基本运算，包括初始化、判满、判空、入栈/入队、出栈/出队、读取栈顶/队头元素等操作。此外，还实现了基于顺序栈的表达式括号匹配检验和基于循环队列的杨辉三角形输出。

1. 数据类型定义

栈中数据元素类型：SElemType，在程序中具体化为char类型
队列中数据元素类型：QElemType，在程序中具体化为int类型

2. 代码结构

stack.h：定义顺序栈的结构体和基本运算函数原型
stack.c：实现顺序栈的基本运算函数
queue.h：定义循环队列的结构体和基本运算函数原型
queue.c：实现循环队列的基本运算函数
main.c：主函数，用于测试顺序栈和循环队列的基本运算

3. 代码实现

stack.h

#ifndef STACK_H
#define STACK_H

#define MAXSIZE 100 // 栈的最大容量

typedef char SElemType; // 栈中数据元素类型

typedef struct
{
    SElemType data[MAXSIZE]; // 存储栈的数组
    int top; // 栈顶指针
} SqStack;

void InitStack(SqStack *S); // 初始化栈
int IsFullStack(SqStack S); // 判断栈是否满
int IsEmptyStack(SqStack S); // 判断栈是否空
void Push(SqStack *S, SElemType e); // 入栈
SElemType Pop(SqStack *S); // 出栈
SElemType GetTop(SqStack S); // 读取栈顶元素
int CheckParentheses(char *expression); // 检验表达式中括号是否匹配

#endif

stack.c

#include "stack.h"

void InitStack(SqStack *S)
{
    S->top = -1;
}

int IsFullStack(SqStack S)
{
    return S.top == MAXSIZE - 1;
}

int IsEmptyStack(SqStack S)
{
    return S.top == -1;
}

void Push(SqStack *S, SElemType e)
{
    if (IsFullStack(*S))
    {
        printf("Stack is full.\n");
        return;
    }
    S->data[++S->top] = e;
}

SElemType Pop(SqStack *S)
{
    if (IsEmptyStack(*S))
    {
        printf("Stack is empty.\n");
        return '\0';
    }
    return S->data[S->top--];
}

SElemType GetTop(SqStack S)
{
    if (IsEmptyStack(S))
    {
        printf("Stack is empty.\n");
        return '\0';
    }
    return S.data[S.top];
}

int CheckParentheses(char *expression)
{
    SqStack S;
    InitStack(&S);

    int i = 0;
    while (expression[i] != '\0')
    {
        if (expression[i] == '(')
        {
            Push(&S, '(');
        }
        else if (expression[i] == ')')
        {
            if (IsEmptyStack(S))
            {
                return 0; // 括号不匹配
            }
            Pop(&S);
        }
        i++;
    }

    return IsEmptyStack(S); // 如果栈为空，则括号匹配
}

queue.h

#ifndef QUEUE_H
#define QUEUE_H

#define MAXSIZE 100 // 队列的最大容量

typedef int QElemType; // 队列中数据元素类型

typedef struct
{
    QElemType data[MAXSIZE]; // 存储队列的数组
    int front; // 队头指针
    int rear; // 队尾指针
} SqQueue;

void InitQueue(SqQueue *Q); // 初始化队列
int IsFullQueue(SqQueue Q); // 判断队列是否满
int IsEmptyQueue(SqQueue Q); // 判断队列是否空
void EnQueue(SqQueue *Q, QElemType e); // 入队
QElemType DeQueue(SqQueue *Q); // 出队
QElemType GetFront(SqQueue Q); // 读取队头元素
QElemType GetRear(SqQueue Q); // 读取队尾元素
void PrintYangHuiTriangle(int N); // 输出杨辉三角形N行数据

#endif

queue.c

#include "queue.h"

void InitQueue(SqQueue *Q)
{
    Q->front = Q->rear = 0;
}

int IsFullQueue(SqQueue Q)
{
    return (Q.rear + 1) % MAXSIZE == Q.front;
}

int IsEmptyQueue(SqQueue Q)
{
    return Q.front == Q.rear;
}

void EnQueue(SqQueue *Q, QElemType e)
{
    if (IsFullQueue(*Q))
    {
        printf("Queue is full.\n");
        return;
    }
    Q->data[Q->rear] = e;
    Q->rear = (Q->rear + 1) % MAXSIZE;
}

QElemType DeQueue(SqQueue *Q)
{
    if (IsEmptyQueue(*Q))
    {
        printf("Queue is empty.\n");
        return -1;
    }
    QElemType e = Q->data[Q->front];
    Q->front = (Q->front + 1) % MAXSIZE;
    return e;
}

QElemType GetFront(SqQueue Q)
{
    if (IsEmptyQueue(Q))
    {
        printf("Queue is empty.\n");
        return -1;
    }
    return Q.data[Q.front];
}

QElemType GetRear(SqQueue Q)
{
    if (IsEmptyQueue(Q))
    {
        printf("Queue is empty.\n");
        return -1;
    }
    return Q.data[(Q.rear - 1 + MAXSIZE) % MAXSIZE];
}

void PrintYangHuiTriangle(int N)
{
    SqQueue Q;
    InitQueue(&Q);

    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= i; j++)
        {
            if (j == 1 || j == i)
            {
                EnQueue(&Q, 1);
            }
            else
            {
                QElemType a = DeQueue(&Q);
                QElemType b = GetFront(Q);
                EnQueue(&Q, a + b);
            }
            printf("%d ", GetRear(Q));
        }
        printf("\n");
    }
}

main.c

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

int main()
{
    SqStack S;
    InitStack(&S);

    Push(&S, 'a');
    Push(&S, 'b');
    Push(&S, 'c');
    printf("Top element: %c\n", GetTop(S));

    Pop(&S);
    printf("Top element after pop: %c\n", GetTop(S));

    char expression[] = "((()))";
    int result = CheckParentheses(expression);
    if (result)
    {
        printf("Parentheses are matched.\n");
    }
    else
    {
        printf("Parentheses are not matched.\n");
    }

    printf("\n");

    SqQueue Q;
    InitQueue(&Q);

    EnQueue(&Q, 1);
    EnQueue(&Q, 2);
    EnQueue(&Q, 3);
    printf("Front element: %d\n", GetFront(Q));
    printf("Rear element: %d\n", GetRear(Q));

    DeQueue(&Q);
    printf("Front element after dequeue: %d\n", GetFront(Q));

    printf("\n");

    int N = 5;
    printf("Yang Hui Triangle with %d rows:\n", N);
    PrintYangHuiTriangle(N);

    return 0;
}

4. 编译运行

将上述代码保存为五个文件：stack.h，stack.c，queue.h，queue.c和main.c，然后编译运行main.c即可。

5. 运行结果

Top element: c
Top element after pop: b

Parentheses are matched.


Front element: 1
Rear element: 3
Front element after dequeue: 2


Yang Hui Triangle with 5 rows:
1 
1 1 
1 2 1 
1 3 3 1 
1 4 6 4 1

6. 使用说明

顺序栈和循环队列的基本运算函数可以在其他程序中直接调用
可以根据需要修改栈和队列的最大容量MAXSIZE
可以根据需要修改数据元素类型SElemType和QElemType

7. 注意事项

顺序栈和循环队列的实现都使用了数组，所以需要注意数组越界的问题
循环队列的入队和出队操作需要使用取模运算来处理循环边界

8. 总结

本项目使用C语言实现了顺序栈和循环队列的基本运算，并给出了两个应用示例：表达式括号匹配检验和杨辉三角形输出。希望本项目能够帮助读者更好地理解顺序栈和循环队列的基本概念和实现方法。