这个特点是链表无法比拟的

发布时间：2025-06-24 19:37:40  作者：北方职教升学中心  阅读量：561

出栈：栈的删除操作叫做出栈，出数据也在栈顶。

以下就是用链表来实现队列的示例图：

那接下来，我们就用代码实现队列。这个就是我们为什么会推荐选择用链表来实现队列。

1.2.1 "栈"实现的选择

之所以选择顺序表，主要有以下的原因：

1. 容易找到栈顶的位置。但是，如果我们使用链表来实现的话，只要我们合理的控制头节点和尾节点，就能够很方便的实现插入和删除操作。

   我们可以知道的一个信息就是：队列只能在一端进行插入操作，在另一端进行删除操作。如果我们使用顺序表来实现，在插入操作环节比较容易实现，但是在删除操作用数组实现就比较繁琐了。接下来，我们再来看看另一个数据结构——“队列”！
   

   2. 队列

   2.1 队列的概念及结构

   队列：只允许在一端进行插入数据的操作，在另一端进行数据删除的操作的特殊线性表。方法就是：将头节点的指针和尾节点的指针用一个结构体给打包起来，只要我们使用头节点和尾节点的指针时，就不要额外再定义其它变量了。而相较于链表来说，就要遍历整个链表，从而遭到链表的为节点，在进行数据的操作，那此时的算法时间复杂度就为O(n)了**。双向链表)中选择，我们会选择哪种数据结构呢？

   我会更倾向于顺序表。

2. • 进行插入操作的一端称为队尾；

• 出队列：进行伤处数据的操作。不过单凭这一点，还不足以让我放弃使用顺序表这个念头！
• 缓存命中率高。
  为什么会这样说呢？你可以想一下**，顺序表的底层是数组，数组如果我要查找到最后一个元素是比较容易的。

  压栈：栈的插入操作叫做压栈(进栈/入栈)，入数据在栈顶。

  2.3.2 队列的头文件

  #pragmaonce#include<stdio.h>#include<stdlib.h>#include<stdbool.h>#include<assert.h>//队列的初始化voidQInit(Queue*p);//销毁队列voidQDestory(Queue*p);//添加数据voidQPush(Queue*p,QDataType x);//删除数据voidQPop(Queue*p);//查看队头元素QDataType QFront(Queue*p);//查看队尾元素QDataType QBack(Queue*p);//队列的大小intQSize(Queue*p);//判断列表是否为空bool QEmpty(Queue*p);

  2.3.3 队列各功能的实现

  #define_CRT_SECURE_NO_WARNINGS#include"queue.h"//队列的初始化voidQInit(Queue*p){assert(p);p->head =p->tail =NULL;p->size =0;}//销毁队列voidQDestory(Queue*p){assert(p);QNode*pcur =p->head->next;while(pcur !=NULL){QNode*next =pcur->next;free(pcur);pcur =next;}pcur =NULL;}//添加数据voidQPush(Queue*p,QDataType x){assert(p);QNode*newnode =(QNode*)malloc(sizeof(QNode));if(newnode ==NULL){perror("malloc fail");return;}newnode->data =x;newnode->next =NULL;//插入数据，只能在队尾插入if(p->head ==NULL){assert(p->tail ==NULL);p->head =p->tail =newnode;}else{p->tail->next =newnode;p->tail =p->tail->next;}p->size++;}//删除数据voidQPop(Queue*p){assert(p &&p->head);//删除数据只能够在队头删除QNode*pcur =p->head;//但只有一个节点的情况if(p->head ==p->tail){free(p->head);p->head =p->tail =NULL;}else{p->head =pcur->next;free(pcur);pcur =NULL;}p->size--;}//查看队头元素QDataType QFront(Queue*p){assert(p &&p->head);returnp->head->data;}//查看队尾元素QDataType QBack(Queue*p){assert(p &&p->tail);returnp->tail->data;}//队列的大小intQSize(Queue*p){assert(p);returnp->size;}//判断列表是否为空bool QEmpty(Queue*p){assert(p);if(QSize(p)==0){returntrue;}returnfalse;}

  好了，到这里，栈和队列的知识就已经全部讲解完毕了。那此时，我们就要想一下，能不能有个更简单的方式，一起控制着头指针和尾指针。

  1.2 栈的实现

  我们根据栈的特点，以及我们所学过的数据结构(顺序表、但其实，栈的实现一般可以用数组或者链表。这个特点是链表无法比拟的。
  我们都知道数组在内存中是连续存储的。

  2.3.1 队列的结构体定义

  typedefintQDataType;typedefstructQNode{QDataType data;structQNode*next;}QNode;typedefstructQueue{QNode*head;QNode*tail;intsize;}Queue;

  这里就是那个难点所在！为什么这里会是要定义两个结构体，你在"栈"实现的时候，才定义一个结构体啊？如果有这个问题的读者，那么恭喜你们跟上了本文的思路了。那根据空间的局部性原理，缓存的命中率就会高，这也就意味着CPU读取数据的速度就会加快，从而给程序的运行提高了速度。

1.3 栈的代码实现

1.3.1 栈的结构体定义（用的是顺序表）

//使用动态顺序表实现栈typedefintSTDataType;typedefstructStack{STDataType*arr;inttop;//可以看作栈顶指针intcapacity;//记录当前栈可用的空间}Stack;

1.3.2 栈的头文件设置

#pragmaonce#include<stdio.h>#include<stdlib.h>#include<assert.h>//栈的接口实现//栈的初始化voidSTInit(Stack*ps);//添加数据 - 栈voidSTPush(Stack*ps,STDataType x);//删除数据 - 栈voidSTPop(Stack*ps);//栈的销毁voidSTDestory(Stack*ps);//查看栈顶元素STDataType STTop(Stack*ps);//判断栈是否未空intSTEmpty(Stack*ps);//查看栈的大小intSTSize(Stack*ps);

1.3.3 栈的各功能的实现

#define_CRT_SECURE_NO_WARNINGS#include"Stack.h"//栈的初始化voidSTInit(Stack*ps){ps->arr =(STDataType*)malloc(sizeof(STDataType)*4);//一开始先给4个大小的空间ps->top =0;ps->capacity =4;}//添加数据 - 栈voidSTPush(Stack*ps,STDataType x){assert(ps);if(ps->top ==ps->capacity){//说明得扩容了STDataType*tmp =(STDataType*)realloc(ps->arr,sizeof(STDataType)*2*ps->capacity);if(tmp ==NULL){perror("realloc fail");exit(1);}ps->arr =tmp;ps->capacity*=2;}ps->arr[ps->top]=x;ps->top++;}//删除数据 - 栈voidSTPop(Stack*ps){assert(ps &&ps->arr);assert(!STEmpty(ps));ps->top--;}//栈的销毁voidSTDestory(Stack*ps){if(ps->arr !=NULL){free(ps->arr);}ps->arr =NULL;ps->capacity =0;ps->top =0;}//查看栈顶元素STDataType STTop(Stack*ps){returnps->arr[ps->top-1];}//判断栈是否未空intSTEmpty(Stack*ps){if(ps->top ==0){return1;}return0;}//查看栈的大小intSTSize(Stack*ps){returnps->top +1;}

好了，到这里，关于栈的知识已经全部讲解完毕了。那可能有的人思维比较活跃，他说那我直接把链表的头部当作栈顶的位置，那我就不需要找链表的尾节点，那时间复杂度就变为O(1)了。

栈中的元素遵循着**后进先出（LIFO：Last In First Out）**的原则。队列具有先进先出的特点FIFO(First In First Out)。

1. 栈

1.1 栈的概念及结构

栈：一种特殊的线性表，其只允许再固定的一端进行插入和删除数据的操作。之后我会出关于这个知识点一系列的编程题详解，希望大家能够持续的关注！

如果觉得本文将的还不错的话，麻烦给偶点个赞吧！！！