栈 – 先进后出
栈应用场景
– 一切满足后进先出的场景, 都可以通过栈来维护
– 浏览器的页面的前进后退缓存
– word, Excel – 撤销操作
– 单道停车场问题
今日学习内容:
队列 – 先进先出 – first in first out – FIFO – 缓冲区
– 特点:具有先进先出的特性
typedef queue{
int* arr;//首地址
int cap;//容量
int size;//队列中有效数据的个数
int front;//出队的位置, 队首
int rear; //入队的位置, 队尾
}queue_t;
- 将数据保存到队列的内存中, —入队
- 将数据从队列中内存中获取, —出队
问题?
入队和出对的位置是不是同一个位置
- 假如：将数据1,2放入队列中
1 -> 下标0
2 -> 下标1
1.从队列中获取一个数据 - 获取的是哪个数据 - 获取的是1, 从下标为0的位置上获取
先进先出的原则
2.把3放入队列中 - 放到哪个位置上 -
是否将新的数据3放到下标为0的位置上 - 不对
放到下标为2的位置上
入队 - 位置 - 2
出队 - 位置 - 0-> 初始化
arr – malloc(sizeof(int)*cap)
cap – cap
size – 没有有效数据 – 0
—————–
front – 出队的位置
rear – 入队的位置
初始化 – 不知道front等于多少 – ?
将第一个数据放到下标为0的位置上
获取数据 – 从哪个位置获取数据 – 0
参照 – 栈的初始化和释放
栈 – top 和 cap的关系 – 判断栈是否为满, 是否为空
if(size == cap)
满
else
非满
if(size == 0)
空
else
非空
代码
queue.h
#ifndef _QUEUE_H
#define _QUEUE_H
//包含公共的头文件
#include <stdio.h>
#include <stdlib.h>
//声明描述队列的数据结构
typedef struct queue{
int* arr;//首地址
int cap;//容量
int size;//有效数据个数
int front;//队首,出队
int rear;//队尾,入队
}queue_t;
//声明操作函数
extern void queue_init(queue_t* queue, int cap);//初始化
extern void queue_deinit(queue_t* queue);//释放内存
extern int queue_full(queue_t* queue);//判断满, 满,返回1;非满, 0;
extern int queue_empty(queue_t* queue);//判断空 空,返回1;非空, 0;
extern void queue_push(queue_t* queue, int data);//入队
extern int queue_pop(queue_t* queue);//出队
extern int queue_size(queue_t* queue);//队列中有效数据个数
#endif
queue.c
#include "queue.h"
void queue_init(queue_t* queue, int cap){
queue->arr = malloc(sizeof(int)*cap);
queue->cap = cap;
queue->size = 0;
queue->front = 0;
queue->rear = 0;
}
void queue_deinit(queue_t* queue){
free(queue->arr);
queue->cap = 0;
queue->size = 0;
queue->front = 0;
queue->rear = 0;
}
int queue_full(queue_t* queue){
return queue->size == queue->cap;
}
int queue_empty(queue_t* queue){
return queue->size == 0;
}
void queue_push(queue_t* queue, int data){
if(queue->rear == queue->cap)
queue->rear = 0;//构造循环队列
queue->arr[queue->rear++] = data;
queue->size++;
}
int queue_pop(queue_t* queue){
if(queue->front == queue->cap)
queue->front = 0;//构造循环队列
queue->size--;//更新计数
return queue->arr[queue->front++];
}
//定义返回有效数据个数的函数
int queue_size(queue_t* queue){
return queue->size;
}main.c
#include "queue.h"
int main(void){
queue_t queue;
queue_init(&queue, 4);
//入队
for(int i = 10; i <= 40; i += 10){
if(!queue_full(&queue))
queue_push(&queue, i);//入队:10(0) 20(1) 30(2) 40(3)
}
printf("队列有效数据个数为:%d\n", queue_size(&queue));
//出队两个数据 - 10(0), 20(1)
for(int i = 0; i < 2; i++){
if(!queue_empty(&queue))
printf("%d ", queue_pop(&queue));
}
printf("\n");
printf("队列有效数据个数为:%d\n", queue_size(&queue));
//入队 50 60
//50(0) 60(1) 30(2) 40(3)
for(int i = 50; i <= 60; i += 10){
if(!queue_full(&queue))
queue_push(&queue, i);
}
//出队
while(!queue_empty(&queue))
printf("%d ", queue_pop(&queue));//30 40 50 60 - 出队顺序
printf("\n");
queue_deinit(&queue);
return 0;
}
出队 出栈 – 将数据获取走
数据还在队列, 栈中 – 认为 – 无效化
while(!queue_full(&queue)){
queue_push(&queue, 100);
}
主要考虑
1、出队 – front改变
2、入队 – rear改变
