【数据结构】—— 栈与队列

前言

  在单片机数据处理的时候，如果在中断里添加太多函数，可能会影响整个程序的运行。这时利用数据结构栈或者队列，先将缓存放进去，等主程序空闲时再处理，可以变相提高代码稳定性。栈与队列是一种特殊操作的线性表，本文主要介绍栈与队列的原理以及单片机C语言实现。

一、栈

1.1 堆栈原理

1. 栈的类型定义
     栈Stack又名堆栈，是限定只能在表的一端（表尾）进行插入或删除操作的线性表。允许进行插入或删除的这一端称为栈顶（Top）；另一端则称栈底（Bottom），不能进行插入或删除。当栈中没有包含数据元素时，称为空栈。栈非空时，处于栈顶位置的元素称为栈顶元素。向一个栈插入新的元素称为入栈或选栈（Push）、此时，插入的元素成为新的栈顶元素；从栈中删除一个元素时，只能删除当前的栈顶元素，称为出栈或退栈（Pop）。
     由于栈的插入和删除只能在栈顶进行，最先入栈的元素必定最后出栈，最后入栈的元素最先出栈，因此栈又叫做后进先出（Last In First Out，LIFO)线性表。

2. 顺序栈的表示
     与顺序表类似，顺序栈就是用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素。同时，为了指示当前的栈顶元素位置，需另设一个指针变量top，称为栈顶指针，通常 top指向栈中下一个入栈位置，当栈顶指针指向第一个存储单元时表示空栈。入栈时，首先将新元素的值存入当前的栈顶位置，然后使栈顶指针top+1；出栈时则相反，先使栈顶指针 top一1，然后取出当前位置的元素的值。顺序栈的结构及基本操作如图所示：
   
     顺序栈的实现方式可以采用预设的固定长度的一维数组来实现，也可以通过预定义两个常量INIT_SIZE 和INCREMENT分别表示顺序栈的初始长度和增量，以动态分配的顺序存储结构进行描述。

1.2 栈的实现

1. 定义结构体

#define	ERROR	0
#define OK 		1
#define INIT_SIZE	10	//存储空间初始分配量
#define INCREMENT	5	//分配增量//定义栈结构体
typedef struct
{char*	base;  int*	top; int 	stacksize;		//当前已分配的存储空间
}Stack;

2. 顺序栈初始化

int InitStack(Stack* S)
{S->base = (char*)malloc(INIT_SIZE * sizeof(char));if(!S->base)	return ERROR;	//申请失败返回0S->top = S->base; 				//设置初始值S->stacksize = INIT_SIZE;return OK;
}

3. 判断栈是否为空

bool EmptyStack(Stack* S)
{return S->top == S->base;
}

4. 入栈

int Push(Stack* S, char x)
{// 检查空间够不够，不够就增容if (ps->top - S->base >= S->stacksize){S->base = (char*)realloc(S->base,(S->stacksize + INCREMENT) * sizeof(char));if(!S->base)	return ERROR;			//申请失败返回0S->top = S->base + S->stacksize;		//重新设置栈顶指针S->stacksize += INCREMENT;}*S->top++ = x;		//新元素入栈，栈顶指针加1return OK;
}

5. 出栈

int Pop(Stack* S,char* x)
{if(S->top == S->base) return ERROR;		//栈空则返回失败--S->top;								//修改栈顶指针减1*x = *S->top;							//出栈元素给Xreturn OK;
}

二、队列

2.1 队列的概念

  队列Queue是限定只能在表的两端分别进行插入或删除操作的线性表。在队列结构中，数据元素只能从一端（表尾）插入，从另一端（表头）删除。允许插入的一端称为队尾（Rear)，允许删除的一端称为队头（Front)。当队列中没有包含数据元素时，称为空队。向一个队列插入新的元素称为人队(Enqueue)，此时，插入的元素成为新的队尾元素；从队列中删除一个元素时，只能删除当前的队头元素，称为出队（Dequeue)。基于列的这种“先进先出”的结构特点，因而也称为先进先出（First In First Out，FIFO)线性表。

2.2 队列结构

  队列的表示与实现也可以采用顺序存储结构和链式存储结构描述

2.2.1 顺序队列

  采用顺序存储结构表示队列时，可以用C语言中的一维数组进行描述。由于对于队列的操作只在队头和队尾进行，因此，需要设置两个指针 front和rear分别指示队头和队尾的位置，并可约定队尾指针rear指向当前队尾元素后的下一个位置，队头指针front指向当前的队头元素。顺序队列的表示形式如下，

#define MAXSIZE 100			//队列的最大容量
typedef struct SqQueue
{int data[MAXSIZE];		//队列的存储空间int rear,front;			//对头队尾指针
}SqQueue；

（1）初始化队列。队尾指针和队头指针均指向下标为0的单元，令front=rear=0。
（2）入队操作。新元素将存放到当前队尾指针所指的单元，并使队尾指针rear增1指示下一次插入的位置，则rear=rear+1。
（3）出队操作。将当前队头指针所指单元的值返回，并将队头指针front增1即可，则 front=front+1。

  入队和出队操作的过程如上图所示。可以看出，队列为空，不能做出队操作，因此判断队列为空的条件是front==rear；经过多次插入和删除操作以后，队列的队尾指针和队头指针将逐步向后移动，最终出现当队尾指针已指向所定义空间中的最后单元时，即rear=MAXSIZE-1时，队列满，无法再入队。虽然此时队头指针所指位置之前可能存在若干单元空闲，却无法进行入队操作的问题。这种现象称为“假溢出”，可以借助两种方法解决顺序队列的“假溢出”问题：

方法一：采用“移动队列”的方法，即每当执行一次出队操作，则依次将队头和队尾指针向数组的起始位置移动，始终保持队头在数组的起始位置。这种方法的代价是产生大量的元素移动，显然不是一种好方法。
方法二：采用循环队列，将一维数组的最后一个单元和第一个单元连接起来构成循环数组，此时称为“循环队列”。当队尾指针已指向数组的最后时，在进行人队操作过程中，可将队尾指针rear 移至数组的起始位置，表示下一次入队操作时的队尾。（居指针移动的方式是rear=(rear+1)%MAXSIZE，队头指针的移动也一样front=(front+1)%MAXSIZE，如图所示：

  循环队列初始化空队时，front=rear=0；当队列经过多次出队入队操作后，会出现队头指针front 和队尾指针rear 再次指向同一单元的情况，此时有可能队列空也有可能队列满。为了区分队满和队空的情况，规定当队空时，front==rear；队满时，队尾指针指向队头指针的前一个位置即为满 (rear+1)%MAXSIZE==front ，实际循环队列队满时，所容纳的元素个数为MAXSIZE-T；通过空留一个存储单元的方式区分循环队列队满和队空的情况。下面第三小节详细说明循环队列的存储表示和基本操作的实现方法。

2.2.2 链队

  采用链式存储结构表示队列，称为链队。显然，利用与线性链表类似的方法可以很容易实现链队结构,并分别设置队尾和队头指针指示链队的位置。在链队结构中增加一个附加的头结点，并使队头指针front指向它。此时，判断空队的标志是，链队的队尾指针rear和队头指针front均指向头结点。带头结点的链队结构示意图如图所示：

2.3 队列的实现

  这边以ringbuffer环形缓冲区为例，环形缓冲区是队列的一个应用，这里采用顺序队来实现

1. ringbuffer.h头文件

#ifndef __RINGBUFFER_H
#define __RINGBUFFER_H#ifdef __cplusplusextern "C" {
#endif #include "stm32f4xx.h"
#include <stdio.h>//队列结构体声明
typedef struct {uint8_t* pBuff;			//保存缓存数据uint8_t* pEnd;  		// pBuff + legnthuint8_t* wp;    		// Write Pointuint8_t* rp;    		// Read Pointuint16_t length;	uint8_t  flagOverflow; // set when buffer overflowed
} RingBuffer;void rbInitialize(RingBuffer* pRingBuff, uint8_t* buff, uint16_t length);
void rbClear(RingBuffer* pRingBuff);
void rbPush(RingBuffer* pRingBuff, uint8_t value);
uint8_t rbPop(RingBuffer* pRingBuff);
uint16_t rbGetCount(const RingBuffer* pRingBuff);
int8_t rbIsEmpty(const RingBuffer* pRingBuff);
int8_t rbIsFull(const RingBuffer* pRingBuff);#ifdef __cplusplus
}
#endif#endif 

2. ringbuffer.c源文件

#include "ringbuffer.h"//初始化队列结构体
void rbInitialize(RingBuffer* pRingBuff, uint8_t* buff, uint16_t length)
{pRingBuff->pBuff = buff;pRingBuff->pEnd  = buff + length;pRingBuff->wp = buff;pRingBuff->rp = buff;pRingBuff->length = length;pRingBuff->flagOverflow = 0;
}//清除缓存溢出标志位
//正常情况下不会过流，只有在IAP情况下可能会出现虚假过流
void rbClear(RingBuffer* pRingBuff)
{pRingBuff->wp = pRingBuff->pBuff;pRingBuff->rp = pRingBuff->pBuff;pRingBuff->flagOverflow = 0;
}//入队
//首先判断队列有没有满，满就退回一段数据，未满就写数据
void rbPush(RingBuffer* pRingBuff, uint8_t value)
{uint8_t* wp_next = pRingBuff->wp + 1;if( wp_next == pRingBuff->pEnd ) {wp_next -= pRingBuff->length; 	// Rewind pointer when exceeds bound}if( wp_next != pRingBuff->rp ) {*pRingBuff->wp = value;pRingBuff->wp = wp_next;} else {pRingBuff->flagOverflow = 1;}
}//出队，空队返回，否则读取数据
uint8_t rbPop(RingBuffer* pRingBuff)
{if( pRingBuff->rp == pRingBuff->wp ) return 0; // emptyuint8_t ret = *(pRingBuff->rp++);if( pRingBuff->rp == pRingBuff->pEnd ) {pRingBuff->rp -= pRingBuff->length; 		// Rewind pointer when exceeds bound}return ret;
}//返回未读数据长度
uint16_t rbGetCount(const RingBuffer* pRingBuff)
{return (pRingBuff->wp - pRingBuff->rp + pRingBuff->length) % pRingBuff->length;
}//判断队列数据是否为空
//1：空；0：非空
int8_t rbIsEmpty(const RingBuffer* pRingBuff)
{return pRingBuff->wp == pRingBuff->rp; 
}//判断队列空间是否满，没啥意义，可以不用
int8_t rbIsFull(const RingBuffer* pRingBuff)
{return (pRingBuff->rp - pRingBuff->wp + pRingBuff->length - 1) % pRingBuff->length == 0;
}

3. 函数调用
   首先对空间初始化申请队列缓存

#define RX_BUFF_SIZE	4096
static RingBuffer  RX_RingBuff;//初始化
void RcvFrom_Init()
{static uint8_t RX_Buff[RX_BUFF_SIZE];rbInitialize(&RX_RingBuff, RX_Buff, sizeof(RX_Buff));
}//入队
void Push_RcvData(u8 dat)
{rbPush(&RX_RingBuff, dat);
}

  然后在中断压入队列，以串口中断为例

void USART1_IRQHandler(void)
{u8 rcvdata;if (USART_GetFlagStatus(USART1, USART_FLAG_ORE) != RESET){USART_ClearFlag(USART1,USART_FLAG_ORE);USART_ReceiveData(USART1);//The RXNE flag can also be cleared by a read operation to the USART_DR register(USART_ReceiveData()).}if(USART_GetITStatus(USART1,USART_IT_RXNE) != RESET){rcvdata = USART_ReceiveData(USART1);Push_RcvData(rcvdata);}
}

  最后在主函数里对数据处理

u8 cur;void main(void)
{/*初始化*/RcvFrom_Init();while(1){cur = rbPop(&RX_RingBuff);/*具体处理*/}
}

三、堆与栈的区别

  首先，堆与栈是两个不同的概念，但是相同点是，他们都是内存里的一块空间。下面介绍它们最主要的区别

3.1 内存中的堆与栈

1. 栈区stack
     栈由操作系统自动分配释放 ，用于存放函数的参数值、局部变量等。当函数被调用时，其参数会被push到堆栈内存中，待调用函数执行完毕后，被压入堆栈的参数就会被pop出来。另外函数体中定义的临时变量会被存放于堆栈中，堆栈是由操作系统分配的，内存的申请与回收都是由OS决定的。
     栈的内存地址生长方向由高到底，所以后定义的变量地址低于先定义的变量。栈中存储的数据的生命周期随着函数的执行完成而结束。

2. 堆区heap
     用于存放进程运行中被动态分配的内存段，大小并不固定，可动态扩张或缩减，当进程调用malloc等函数分配时，新分配的内存就被动态的添加到堆上，当调用free等函数释放内存时，被释放的内存就会从堆中被剔除(堆被缩减)。堆由开发人员分配和释放， 若开发人员不释放，程序结束时由OS回收，分配方式类似于链表。

int main()
{// C 中用 malloc() 函数申请char* p1 = (char *)malloc(10);// 用 free() 函数释放free(p1);char *p2;			//栈while(1){//}
}

  从上面的示例代码可以看出，由于单片机正常情况下无操作系统，所以在代码里定义的全局变量就相当于堆，如p1，因为它不会自动销毁。而一些暂时性的数据如局部变量就相当于栈，如p2，因为函数被调用结束就会被系统自动释放

3.2 数据结构中的堆与栈

  栈的数据结构在1.1小节有介绍，是一种运算受限的线性表，其限制是指只仅允许在表的一端进行插入和删除操作。而堆是一种常用的树形结构，是一种特殊的完全二叉树，当且仅当满足所有节点的值总是不大于或不小于其父节点的值的完全二叉树被称之为堆。堆的这一特性称之为堆序性。因此，在一个堆中，根节点是最大（或最小）节点。如果根节点最小，称之为小顶堆（或小根堆），如果根节点最大，称之为大顶堆（或大根堆）。堆的左右孩子没有大小的顺序。

结语

  作为一种数据结构，栈在单片机软件开发中并不常用，更多的是使用队列。比如单片机很多实时操作系统RTOS基本有内置的消息队列API，却没有栈API。