• 👑专栏内容：数据结构
• ⛪个人主页：子夜的星的主页
• 💕座右铭：日拱一卒，功不唐捐

一、前言

栈和队列是两种常见且重要的线性数据结构，它们在解决各种实际问题和算法实现中发挥着关键作用。本文将详细介绍栈和队列的概念、特点以及各自的应用场景。我们将从生活中的例子出发，形象地解释栈和队列的工作原理，也会使用不同的数据结构实现栈和队列，以及它们的优缺点。

二、栈的概念

1、定义

栈是一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。

栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。

我们可以简单的把栈形象地看成一筒羽毛球，当往筒里放球时，球从筒底排到筒口，当从筒里拿球的时候，球从筒口往下依次被拿出来，直到筒底的最后一个球被拿出来。

2、操作

通常对栈执行以下两种操作：
向栈中添加元素，此过程被称为"进栈"（入栈或压栈）；
从栈中提取出指定元素，此过程被称为"出栈"（或弹栈）；

三、栈的实现

1、定义

typedef struct Stack
{
		int *data; //（1）
		int size; //（2）
		int top;  //(2)
}Stack;

（1）用来存储数据的数组
（2）用来表示线性表的最大存储容量的值
（3）用来标识栈顶元素的栈顶下标

2、栈的初始化

Stack *initStack(int n)
{
		Stack *s = (Stack *)malloc(sizeof(Stack));  
		s->data = (int *)malloc (sizeof(int)*n); 
		s->size = n; 
		s->top = -1; 
		return s; 
}

为什么栈顶的下表要初始化为-1 呢？

3、栈的销毁

void clearStack(Stack *s)
{
	if(s ==NULL) return ; //（1）
	free(s->data); //（2）
	free(s);   //（3）
	return ;
}

（1）如果栈为空，直接返回
（2）销毁存储的数据
（3）销毁栈

4、栈的判空

int empty (Stack *s)
{
		return s->top == -1;
}

5、查看栈顶元素

int top(Stack *s)
{
		if(empty(s)) return 0;
		return s->data[s->top];
}

6、入栈与出栈

Ⅰ、入栈

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

int push(Stack *s,int val)
{
		if(s->top + 1==s->size )//（1）
            return 0;
		s->top = s->top+1;		//（2）
		s->data[s->top] = val;	//（3）
		return 1;
}

（1）如果栈已满

（2）栈顶指针向上移动

（3）将数据让如栈中

Ⅱ、出栈

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

int pop(Stack *s)
{
		if(empty(s)) return 0; //（1）
		s->top = s->top -1;	   //（2）
		return 1;			   
}

（1）如果栈为空，直接结束

（2）出栈 ：将栈顶 减一 即可

四、队列的概念

1、定义

只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out) 。

想象一下排队买票的场景。每个人都会排在队伍的尾部，而排在队伍最前面的人会最先买到票并离开队伍。这个过程类似于队列的入队和出队操作。最先进入队伍的人会最先离开队伍，而最后进入队伍的人则会最后离开队伍。

2、操作

通常对队列执行以下两种操作：
向队列中添加元素，此过程被称为"入队"；
从队列中提取出指定元素，此过程被称为"出队"；

五、队列的实现

1、顺序表实现

Ⅰ、队列的假溢出

队列是一种数据结构，可以将其看作是一个排队等待的队伍。在队列中，元素的添加（入队）和移除（出队）遵循先进先出（FIFO）的原则，即最早进入队列的元素最先被移除。队列有一个队头和队尾，新元素从队尾添加，而元素从队头移除。

队列溢出指的是当队列已满，也就是说它已经包含了最大允许的元素数量，但我们仍试图向其中添加新元素时发生的现象。此时，由于队列无法容纳更多的元素，队列溢出就发生了。而队列的假溢出是指队列中，队列尾部的空闲空间实际上可以容纳新的元素，但由于队列的逻辑结构限制（队列头和尾是相邻的），导致空间不能被利用，从而产生的一种溢出现象。实际上，这种溢出并非真正意义上的溢出，因为队列仍然具有可用空间。这就是为什么称为“假溢出”。

如下图所示，数组的前两个位置明明就是空的，但是却由于数组的最后一个位置有数据导致新数据无法正常加入。

为了解决假溢出的问题，可以使用循环队列的概念。循环队列是一种特殊类型的队列，其中队尾可以连接到队头，从而实现有效地使用队列空间。在循环队列中，当队尾指针到达数组的末尾时，它将循环回到数组的起始位置，继续使用队列中的空闲空间。这样就避免了假溢出的情况。

Ⅱ、队列的定义

为了用顺序表实现队列，我们还要定义一下顺序表。

typedef struct vector {
    int *data; //数据区
    int size;	 //数据大小
} vector;

使用顺序表定义队列

typedef struct Queue {
    vector *data;  //数据存储区域
    int size, head, tail, count; //总大小、队列头指针、队列尾指针、循环
} Queue;

Ⅲ、初始化队列

//初始化有一个大小为n的顺序表
vector *initVector(int n) 
{
    vector *v = (vector *)malloc(sizeof(vector));
    v->size = n;
	//初始化一个顺序表的数据区域
    v->data = (int *)malloc(sizeof(int) * n);
    return v;
}

Queue *initQueue(int n) {
		//申请出一个队列空间
    Queue *q = (Queue *)malloc(sizeof(Queue));
		//初始化数据区域
    q->data = initVector(n);
		//初始化顺序表大小
    q->size = n;
		//初始化头尾指针，循环队列
    q->head = q->tail = q->count = 0;
    return q;
}

Ⅳ、销毁队列

void clearVector(vector *v) {
    if (v == NULL) return ;
    free(v->data);
    free(v);
    return ;
}

void clearQueue(Queue *q) {
    if (q == NULL) return ;
		//清理数据区域
    clearVector(q->data);
		//释放队列本身的空间
    free(q);
    return ;
}

Ⅴ、队列判空

//队列判空
int empty(Queue *q) {
    return q->count == 0;
}

Ⅵ、查看队首元素

//查看顺序表中的某一个值
int vectorSeek(vector *v, int pos) {
    if (pos < 0 || pos >= v->size) return -1;
    return v->data[pos];
}

int front(Queue *q) {
		//直接返回指向的那个元素值
    return vectorSeek(q->data, q->head);
}

Ⅶ、入队出队

入队操作的返回值代表入队成功。

什么时候入队不成功？当队列满了的时候就不成功。

//入队操作
int push(Queue *q, int val) {
    if (q->count == q->size) return 0; //队列满了，入队失败
    insertVector(q->data, q->tail, val);//调用顺序表的插入操作
    q->tail += 1; //完成数据插入，调整tail指针位置
    if (q->tail == q->size) q->tail = 0; //调整位置，形成循环利用，防止假溢出
    q->count += 1; //count + 1
    return 1; //入队成功
}

//出队操作
int pop(Queue *q) {
    if (empty(q)) return 0; //队列为空，直接返回0，出队失败
    q->head += 1; //头指针向后移动一位 
    // 注意这里有个小 bug，由于是循环队列，别忘了判断 head 是否越界
    if (q->head == q->size) q->head = 0;
    q->count -= 1;
    return 1;
}

2、单链表实现

在顺序表实现的队列中，队列的大小是预先固定的，当队列满时，即使实际上有空闲的空间，也无法将新元素插入队列。这种现象被称为“假溢出”。为了解决这个问题，我们通常需要实现一个循环队列，这样可以在队列满时使用空闲空间。

然而，在链表实现的队列中，我们并不需要预先分配固定大小的内存。当需要插入新元素时，我们可以动态地为新节点分配内存，并将其添加到链表中。同样，当删除元素时，我们可以释放相应节点的内存。因此，链表实现的队列不会遇到假溢出现象，因为只要系统内存允许，我们可以继续分配空间来扩展队列。

Ⅰ、队列的定义

//链表的节点结构
typedef struct Node {
    int data;
    Node *next;
} Node;
//实现一个有头链表
typedef struct LinkList {
    Node head, *tail;
} LinkList;

typedef struct Queue {
    LinkList *l; 
	//因为底层结构变成了链表，所以不在乎存储空间大小，不用考虑假溢出
	  int count;  
} Queue;

Ⅱ、初始化队列

//初始化链表
LinkList *initLinkList() {
    LinkList *l = (LinkList *)malloc(sizeof(LinkList));
    l->head.next = NULL; 	// 头节点的下一个节点指针初始化为 NULL
    l->tail = &(l->head);	 // 尾节点指针指向头节点
    return l;
}

Queue *initQueue() {
    Queue *q = (Queue *)malloc(sizeof(Queue));
    q->l = initLinkList(); //初始化队列中的链表
    q->count = 0; 
    return q;
}

Ⅲ、销毁队列

//销毁链表
void clearLinkList(LinkList *l) {
    Node *p = l->head.next, *q;
    while (p) {
        q = p->next;
        free(p);
        p = q;
    }
    free(l);
    return ;
}

//销毁队列
void clearQueue(Queue *q) {
    if (q == NULL) return ;
    clearLinkList(q->l); //销毁队列中的链表
    free(q); 						 //销毁队列本身
    return ;
}

Ⅳ、队列判空

int empty(Queue *q) {
    return q->count == 0;
}

Ⅴ、查看队首元素

//链表判空
int emptyList(LinkList *l) {
    return l->head.next == NULL;
}
//查看链表首元素
int frontList(LinkList *l) {
    if (emptyList(l)) return 0;
    return l->head.next->data;
}

int front(Queue *q) {
    if (empty(q)) return 0;
    return frontList(q->l); //返回链表存储的第一个数据
}

Ⅵ、 入队出队

入队操作：

• 使用 getNewNode 函数创建一个新节点，将入队元素存储在新节点的 data 成员中。

• 更新链表尾节点指针 tail 的 next 成员，使其指向新节点。

• 更新尾节点指针 tail，使其指向新节点。

• 增加队列元素计数。

  

//创建一个新的链表节点
Node *getNewNode(int val) {
    Node *p = (Node *)malloc(sizeof(Node));
    p->data = val;  
    p->next = NULL; 
    return p;
}
//在链表的最后位置加入一个新链表
int insertTail(LinkList *l, int val) {
    Node *node = getNewNode(val);
    l->tail->next = node;
    l->tail = node;
    return 1;
}
//队列的入队
int push(Queue *q, int val) {
    insertTail(q->l, val); //在链表的末尾增加一个值
    q->count += 1;		 // 更新队列元素个数
    return 1;
}

出队操作：

• 检查链表是否为空。如果为空，说明队列中没有元素可以出队。

• 保存链表头节点的下一个节点指针（即队头元素的节点）。

• 更新链表头节点的 next 成员，使其指向队头元素的下一个节点。

• 如果队头元素是尾节点，更新尾节点指针 tail，使其指向头节点。

• 释放队头元素的节点内存。

• 减少队列元素计数。

  

  //链表判空
  int emptyList(LinkList *l) {
      return l->head.next == NULL;
  }
  //删除链表的头元素
  int eraseHead(LinkList *l) {
      if (emptyList(l)) return 0;   // 如果链表为空，返回 0，表示没有元素可删除
      Node *p = l->head.next;  	  // 保存头部节点（即队头元素所在的节点）
      l->head.next = l->head.next->next; // 更新头节点的下一个节点指针，使其指向队头元素的下一个节点
      if (p == l->tail) l->tail = &(l->head); // 如果删除的是尾节点，更新尾节点指针为指向头节点
      free(p); 	// 释放头部节点（队头元素所在的节点）的内存
      return 1;
  }
  //出队操作
  int pop(Queue *q) {
      eraseHead(q->l); //删除链表中的第一个元素
      q->count -= 1;
      return 1;
  }
  

  

  3、两者区别

  Ⅰ、顺序表实现的队列

  顺序表（基于数组）实现队列时，通常采用循环队列的策略。队列的头部和尾部都会随着入队和出队操作移动，当达到数组边界时会回到数组起始位置。为了避免队列满和队列空的判断条件冲突，通常会预留一个空间不用于存储元素。

• 访问速度快：数组具有较好的随机访问性能，可以通过下标直接访问元素。

• 空间利用率高：顺序表的存储空间是连续的，没有额外的指针开销。

  缺点：

• 产生假溢出：当队列未满但数组已经无法容纳新元素时，需要进行循环队列调整，否则会产生假溢出。

• 大小固定：顺序表的大小在创建时就已经确定，不能动态调整。如果空间过大，会造成空间浪费；如果空间过小，可能导致溢出。

  Ⅱ、单链表实现的队列

  单链表实现队列： 单链表实现队列时，头部节点用于出队，尾部节点用于入队。每次入队时，在尾部添加新节点；每次出队时，删除头部节点并释放其内存。

优点：

• 动态分配空间：单链表实现的队列可以在运行时动态分配和释放内存，避免了假溢出现象。

• 实现简单：单链表实现队列时，只需在头部和尾部进行操作，不需要循环队列策略，实现相对简单。

缺点：

• 空间开销较大：单链表需要额外的指针存储节点之间的关系，导致额外的空间开销。

• 访问速度相对较慢：链表无法像数组那样直接通过下标访问元素，需要遍历链表节点。