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

数据结构3-栈和队列

1 栈-特殊的线性表-先进后出
- 1.1 栈的三个案例
2 队列-与栈相反-先进先出
- 2.1 队列的案例
3 用C实现栈的代码：
4 用C实现队列的代码

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;
}