当前位置：首页 > article >正文

【数据结构】栈与队列（FIFO）

article 2025/1/6 15:49:56

在阅读该篇文章之前，可以先了解一下堆栈寄存器和栈帧的运作原理：<【操作系统】堆栈寄存器sp详解以及栈帧>。

栈(FILO)

特性: 栈区的存储遵循着先进后出的原则。
例子: 枪的弹夹，最先装进去的子弹最后射出来，最后装入的子弹最先射出来。
操作：

初始化
入栈
出栈
遍历

分类：

顺序栈
通过数组与栈顶指针实现。

链栈
通过链表与栈顶指针实现。

顺序栈

#define N 5
#define datatype int
typedef struct stack{
	datatype arr[N];  //栈的数组
	datatype top;     //栈的栈顶指针
}stack_t;

在这里插入图片描述

1> 初始化stack_init

stack_t *stack_init(void)
{
	//堆
	stack_t *p = (stack_t *)malloc(sizeof(stack_t));
	if(NULL == p)
	{
		perror("malloc");
		return NULL;
	}
    //栈顶指针指向-1
    p->top = -1;
    return p;
}

2> 入栈push

int push(stack_t *p,datatype d)
{
    //判断栈是否已满
	if(p->top == N-1)
    {
        printf("酒店(栈)满了..\n");
        return -1;
    }
    //栈顶指针+1和存入数据
    p->arr[p->++top] = d;
    return 0;
}

3> 出栈pop

int pop(stack_t *p,datatype *d)  //这样就能使外面的变量改变
{
    //先判断栈是否空
    if(p->top == -1)
    {
        printf("酒店人都不在了..\n");
        return -1; 
    }
    //将数据取出来并栈顶指针减1
    *d = p->arr[p->top--];
    return 0;
}

4> 遍历display

void display(stack_t *p)
{
	for(int i=p->top;i>=0;i--)  //先进后出
	{
		printf("| %d |",p->arr[i]);
	}
	printf("\n");
}

链栈

在这里插入图片描述

#define datatype int
typedef struct stack{
	struct stack *next;  //下一个地址
	datatype data;     //链栈的数据域
}stack_t;

1> 入栈push

int push(stack_t **top,datatype d) //二级指针
{
    //1>创建新结点
    stack_t *node = (stack_t *)malloc(sizeof(stack_t));
    if(NULL == p)
	{
		perror("malloc");
		return -1;
	}
    //2>next指针域指向top指向的地址
    node->data = d;
    node->next = (*top); 
    //3>让top指向新入栈的结点的地址
    (*top) = node;
    return 0;
}

2> 遍历display

void display(stack_t *top)
{
	//遍历
	while(top != NULL)
	{
		printf("| %d |\n",top->data);
        top = top->next;
	}
    printf("\n");
}

3> 出栈pop

int pop(stack_t **top,datatype *d)
{
    //1>判断链栈是否空
    if((*top)== NULL)
    {
        printf("链栈为空\n");
        return -1;
    }
    //2>中间变量保存要删除的地址
    stack_t *temp = (*top);
    //3>top往栈底方向移动
    (*top) = (*top)->next;
    //数据传出
    (*d) = temp->data;
    //4>删除与释放
    temp->next = NULL;
    free(temp);
    return 0;
}

队列(FIFO)

“FILO（先进后出）”，这其实是栈的特点，而不是队列的特性。

特性：先进先出
分类：

顺序队列（顺序循环队列）
链式队列

顺序队列

在这里插入图片描述

1> 初始化queue_init

queue_t *queue_init(void)
{
	//堆
	queue_t *p = (queue_t *)malloc(sizeof(queue_t));
	if(NULL == p)
	{
		perror("malloc");
		return NULL;
	}
    //队头和队尾指针指向-1
    p->head = -1;
    p->tail = -1;
    return p;
}

2> 入队push

//入队
int push(queue_t *p,datatype d)
{
    //判断队列是否已满
	if(p->tail == N-1)
    {
        printf("队列满了..\n");
        return -1;
    }
    //队尾指针+1和存入数据
    p->arr[++p->tail] = d;
    return 0;
}

3> 出队pop

//出队
int pop(queue_t *p,datatype *d)  //这样就能使外面的变量改变
{
    //先判断队列是否空
    if(p->head == p->tail)
    {
        printf("队列中没有数据..\n");
        return -1; 
    }
    //将数据取出来并栈顶指针减1
    *d = p->arr[++p->head];
    return 0;
}

4> 遍历display

void display(queue_t *p)
{
	for(int i=p->head+1;i<=p->tail;i++)  //先进先出
	{
		printf("| %d |\n",p->arr[i]);
        
	}
    printf("\n");
}

顺序循环队列

在这里插入图片描述

1> 初始化

queue_t *queue_init(void)
{
	//堆
	queue_t *p = (queue_t *)malloc(sizeof(queue_t));
	if(NULL == p)
	{
		perror("malloc");
		return NULL;
	}
    //队头和队尾指针指向-1  //修改处
    p->head = N-1;
    p->tail = N-1;
    return p;
}

2> 入队

int push(queue_t *p,datatype d)
{
    //判断队列是否已满 //修改处 牺牲一个空间 区分队空
	if((p->tail+1)%N == p->head)
    {
        printf("队列满了..\n");
        return -1;
    }
    //队尾指针+1 ,取余目的是循环使用空间
    p->tail = (p->tail+1)%N;
    //存入数据
    p->arr[p->tail] = d;
    return 0;
}

3> 出队

int pop(queue_t *p,datatype *d)  //这样就能使外面的变量改变
{
    //先判断队列是否空
    if(p->head == p->tail)
    {
        printf("队列中没有数据..\n");
        return -1; 
    }
    //将队头指针+1，并取余
    p->head = (p->head+1)%N;
    //将数据取出
    *d = p->arr[p->head];
    return 0;
}

4> 遍历

void display(queue_t *p)
    int i; //修改处
	for(i=(p->head+1)%N;i!=(p->tail+1)%N;i=(i+1)%N)  //先进先出
	{
		printf("| %d |\n",p->arr[i]);
        
	}
    printf("\n");
}