【数据结构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 100typedef 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的值来调整队列的最大容量。另外，如果队列已满时尝试入队或者队列为空时尝试出队，代码会输出相应的提示信息。