【数据结构3-栈和队列】

1 栈-特殊的线性表-先进后出

1.1 栈的三个案例

2 队列-与栈相反-先进先出

2.1 队列的案例

3 用C实现栈的代码：

#define MAX_SIZE 100
typedef struct
{
    int data[MAX_SIZE];//栈的深度
    int top;//栈顶记录
} Stack;
//初始化
void init(Stack *stack)
{
    stack->top = -1;
}
int isEmpty(Stack *stack)
{
    return stack->top == -1;
}
int isFull(Stack *stack)
{
    return stack->top == MAX_SIZE - 1;
}
//入栈
void push(Stack *stack, int value)
{
    if (isFull(stack))
    {
        printf("Stack is full. Cannot push element.\n");
        return;
    }
    stack->data[++stack->top] = value;
}
//出栈
int pop(Stack *stack)
{
    if (isEmpty(stack))
    {
        printf("Stack is empty. Cannot pop element.\n");
        return -1;
    }
    return stack->data[stack->top--];
}

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

    push(&stack, 10);
    push(&stack, 20);
    push(&stack, 30);

    printf("Popped element: %d\n", pop(&stack));
    printf("Popped element: %d\n", pop(&stack));
    printf("Popped element: %d\n", pop(&stack));
    return 0;
}

4 用C实现队列的代码

#include <stdio.h>

#define MAX_SIZE 100

typedef struct {
    int data[MAX_SIZE];
    int front;
    int rear;
} Queue;
void initQueue(Queue *queue) {
    queue->front = 0;
    queue->rear = 0;
}
int isFull(Queue *queue) {
    return (queue->rear + 1) % MAX_SIZE == queue->front;
}
int isEmpty(Queue *queue) {
    return queue->front == queue->rear;
}
void enqueue(Queue *queue, int value) {
    if (isFull(queue)) {
        printf("Queue is full.\n");
        return;
    }
    queue->data[queue->rear] = value;
    queue->rear = (queue->rear + 1) % MAX_SIZE;
}
int dequeue(Queue *queue) {
    if (isEmpty(queue)) {
        printf("Queue is empty.\n");
        return -1;
    }
    int value = queue->data[queue->front];
    queue->front = (queue->front + 1) % MAX_SIZE;
    return value;
}
int main() {
    Queue queue;
    initQueue(&queue);
    enqueue(&queue, 1);
    enqueue(&queue, 2);
    enqueue(&queue, 3);
    
    printf("%d\n", dequeue(&queue));
    printf("%d\n", dequeue(&queue));
    printf("%d\n", dequeue(&queue));
    return 0;
}

• 我们使用了一个结构体来表示队列，其中包含一个数组用于存储数据，以及两个指针front和rear分别指向队列的头部和尾部。
• initQueue函数用于初始化队列
• isFull函数用于判断队列是否已满
• isEmpty函数用于判断队列是否为空
• enqueue函数用于入队操作
• dequeue函数用于出队操作
• 可以根据需要修改MAX_SIZE的值来调整队列的最大容量。另外，如果队列已满时尝试入队或者队列为空时尝试出队，代码会输出相应的提示信息。