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

在阅读该篇文章之前，可以先了解一下堆栈寄存器和栈帧的运作原理：<【操作系统】堆栈寄存器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;}//栈顶指针指向-1p->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;}//队头和队尾指针指向-1p->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");
}

综上。希望该内容能对你有帮助，感谢！

以上。仅供学习与分享交流，请勿用于商业用途！转载需提前说明。

我是一个十分热爱技术的程序员，希望这篇文章能够对您有帮助，也希望认识更多热爱程序开发的小伙伴。
感谢！