嵌入式系统及其在无线通信中的应用开发最新章节_王勇著

1.3.5 栈、堆与队列

栈和队列在嵌入式软件中使用频率非常高，可以将其看成线性表。通过对线性表的插入和删除进行限制操作就可得到栈的实现定义，即先进后出的数据结构。

栈也称为堆栈，栈的插入和删除在表的同一端完成，也就是说栈只能在一端（栈顶）操作数据，也称为压栈（push）和弹栈（pop），后文详述。堆是一个数组对象，可以一个完全二叉树的方式存在，所以它具有顺序随意性。队列是能在两端对数据项进行操作，它的特点是先进先出（First Input First Output,FIFO）。

1.程序内存区

程序占用的内存分为以下4个部分。

（1）栈区（stack），存放函数参数和局部变量，编译器负责分配释放。

（2）堆区（heap），由程序员分配和释放，如malloc对应着free函数，若程序员不释放，程序结束时可能由操作系统（Operation System,OS）回收。注意它与数据结构中的堆是不同的。

（3）全局区（静态区static），用来存放全局变量和静态变量，结束后由OS释放。

（4）常量区和代码区，存放常量数据和函数码，结束后由OS释放。

具体代码如下所示。

/*ret在全局初始化区，如没有初始化则存放在未初始化区*/
int ret = 2;
main ()
{
    int val;             /*栈*/
    static int s=0;        /*静态变量初始化区*/
    char*pt=＂test＂;      /*pt在栈中，test在常量区*/
    ps = (char*)malloc (32); /*这个32 byte的区域在堆中*/
}

2.栈操作

前文所述，栈的访问规则为push和pop两种操作。push是向栈顶添加元素，pop用来删除当前栈顶的元素，栈顶指针可上下移动。

typedef struct node
{
    int data;
    struct node *next;
}node;
node *Init (node *top)
{
    top=NULL;
    return (top);
}
node *push (node *top,int x)
{
    node *p;
    p= (node*)malloc (sizeof (node));
    p->data=x;
    p->next=top;
    top=p;
    return (top);
}
node *pop (node *top)
{
    node *tep;
    tep=top;
    top=top->next;
    free (tep);
    return (top);
}

进栈后，栈顶指针自动增1；出栈后，栈顶指针自动减1，整个过程一直指向最顶端。因为需要判定栈空或栈满的异常，软件开发中要对栈顶指针进行运算处理，在栈空时不能出栈（无效），栈满则不能再向栈中存储数据。若所有元素的类型相同，栈存储也可用数组来实现。

3.队列操作

和栈类似，队列也是一组元素的集，其操作规则有入队和出队两种，采用先进先出的方式。入队（enqueue）是在队尾添加元素，此时队尾就是这个新增元素了，出队（dequeue）是从队头取出一个元素，此时队头就是它的下一个元素。从中可看出队列的插入和删除操作分别在线性表的两端进行。

为提高存储空间利用效率，使用环形队列（Circular Queue）。它是将队列元素按环形圈的方法处理，队列的头指针（head）和尾指针（tail）之间包括有效数据。指针可增大，head到tail时队列为空状态，tail到head时队列为满状态，源代码如下。

#define MAX_SIZE  100
/*初始定义队列中的节点和操作接口*/
typedef struct queue
{
    int elem[MAX_SIZE];
    int front;
    int rear;
}queue;
void Init (queue * qu)
{
    qu->front=0;
    qu->rear=0;
}
void enqueue (queue *cp,int x)
{
    if ((cp->rear+1)%MAX_SIZE = =cp->front)
      return;
    else
    {
      cp->rear= (cp->rear+1)% MAX_SIZE;
      cp->elem[cp->rear]=x;
    }
}
int dequeue (queue *cp)
{
    if (cp->front= =cp->rear)
      return −1;
    else
    {
      cp->front= (cp->front+1)%MAX_SIZE;
      return (cp->elem[cp->front]);
    }
}

4.堆和栈的区别

在实际开发中，使用堆或栈是有区别的，主要表现在以下方面。

（1）申请方式不同

栈由系统自动分配。堆则需要程序员申请，指明空间大小，在C++语言中用new，而在C语言中可用malloc函数，如p1 = (char *)malloc (10)。堆分配的速度较慢，较易产生内存碎片，所以需要及时清理。

（2）大小的限制不同

栈是一块连续的内存区。栈顶和栈的最大容量是预先确定的。只要栈的剩余空间大于要申请的空间，就可为程序变量提供内存；否则报告异常，提示栈溢出。栈的溢出问题非常棘手，特别是在消息通信或者参数传递时极易出现类似的问题。

堆则不同，它是不连续的内存区。系统维护一个空闲内存链表，收到分配申请时要从中找出大于申请空间的节点，所以其大小受限于系统中有效的虚拟内存，即主机位。堆获得的空间比较灵活，也比较大，但要注意回收。

（3）存储内容不同

存储内容的区别主要表现在指令地址和存储数据。在函数调用时，依次进栈的有指令地址、函数参数（参数入栈顺序是从右向左）和局部变量等。栈顶指针指向主函数的下一条指令，表明程序从该点运行被调用函数，所以函数调用时栈会增长。静态变量不入栈。出栈顺序与入栈顺序相反，出栈结束后栈会缩小。

相对来说，堆是一种较长期的存储区域，其具体内容由程序确定，大小在堆的头部用一个字节存放。同样，堆不会自动释放内存，需要明确释放内存，防止内存泄露。