数据结构：栈

重温八皇后问题

bo-blog 2.1.0附件下载变gz的问题

Nov 18

felix021 @ 2009-11-18 23:56 [IT » 程序设计] 评论(1) , 引用(0) , 阅读(7937) | Via 本站原创

大 | 中 | 小

花点时间总结一下“栈”相关的内容。希望对于初学栈的同学会比较有帮助。

另外，其中涉及的一些内容也是书本上不会涉及到，或者是零零散散写出来的。看看总没坏处。

--------------传说中的分割线-------------

数据结构：栈

内容纲要
1. 什么是栈
2. 栈的实现(C语言)
  a) 数组实现
  b) 单链表实现
  c) 两种实现的对比
3. 栈的应用
  a) 在函数调用中的作用
  b) 在局部变量存储中的应用
    * 栈空间和系统维护的堆空间的对比
  c) 在算法中的应用
4. 附完整代码:

下载文件 (已下载 1100 次)

点击这里下载文件: stack.zip

----
1. 什么是栈。

栈，stack，是一种先进后出(FILO, First In Last Out)的数据结构，就像一个装硬币的圆筒，硬币一枚一枚塞进去，最先塞进去的那个肯定是最后取出来的。

理解以下四个词的含义：
·入栈：将一个元素加入到栈中
·出栈：将最后入栈的元素从栈中弹出
·栈底：空栈(没有元素的栈)可以使用的第一个位置；存放第一个入栈元素的位置。
·栈顶：存放最后一个入栈元素的位置。

----
2. 栈的实现。

从栈的定义来看，一个符合条件的实现应该包含以下几种功能：
·元素入栈
·返回栈顶元素
·栈顶元素出栈
当然，如果能再加上”判断栈是否为空”的功能就更好了。

可以看出，栈是一种有序列的数据结构，所以适合用数组或链表来实现。下面分别讲讲如何实现，并附上具体代码。

a) 数组实现

#define N 100
struct stack {
int data[N];
int n;
};

我们可以用这样一个比较简单的结构体来实现栈。其中的data数组用于保存已经入栈但还未出栈的元素，而n用做栈指针（即data数组的索引），用来记录存储栈顶之上位置（存储下一个入栈元素的位置）的索引。当然，n也可以指向最后一个入栈的元素，如果这么做，下面的代码需要做相应的修改。
基于这个结构体，我们需要实现以下一些函数：

//分配一个stack结构体的空间，初始化栈指针为0，并返回该结构体的指针。如果分配失败，返回NULL。
struct stack * newStack() {
    struct stack * p = (struct stack *) malloc (sizeof (struct stack));
    if (p == NULL) {
        return NULL;
    }
    else {
        p->n = 0;
        return p;
    }
}

//通过栈指针的大小来判断栈是否为空。
int isEmpty(struct stack *p) {
return (p->n <= 0) ? 1 : 0;
}

//通过栈指针的大小来判断栈是否已满
int isFull(struct stack *p) {
return (p->n >= N) ? 1 : 0;
}

//将元素value入栈：如果栈满，失败，返回0；否则入栈成功，返回1。
int push(struct stack *p, int value) {
    if (!isFull(p)) {
        p->data[p->n] = value;
        p->n++;
        return 1;
    }
    else {
        return 0;
    }
}

//从栈p中取出栈顶元素，存入value指向的空间。如果栈为空，失败，返回0；否则返回1。
int top(struct stack *p, int *value) {
    if (isEmpty(p)) {
        return 0;
    }
    else {
        *value = p->data[p->n - 1];
        return 1;
    }
}

//将栈顶元素出栈。如果栈为空，失败，返回0；否则返回1。
int pop(struct stack *p) {
    if (isEmpty(p)) {
        return 0;
    }
    else {
        p->n--;
        return 1;
    }
}

//释放栈p结构体占用的空间。
void deleteStack(struct stack *p) {
free(p);
}

以上一些列函数构成了实现栈所需要的所有功能。也许你曾经看过其他版本的数组实现，看起来好像没这么麻烦。
实际上这么写虽然麻烦些，但是有几个好处：
·使用结构体，将栈需要的数据封装在一起，构成一个整体，使每个结构体变量可以代表一个单独的栈。
·每个操作栈函数的参数包括一个结构体的指针，这样方便创建多个栈同时使用而互不干扰。
·不需要直接访问结构体的元素，完全由各个函数来控制（包括创建和销毁），保证程序的正确性。
·每个函数返回相应的值来判断执行是否出错，保证程序的健壮性。
=>为什么不写一个class？——因为我用的是C而不是C++。返璞归真。
=>返璞归真为啥不用汇编，用机器语言？——找碴的吧你。

用数组来实现，代码非常清晰、简单。但是存在的问题是，数组的初始值是固定的。当然，一个变通的解决办法是写一个可以动态增长的数组（类似STL的vector）来代替这个数组（看不懂的话可以先忽略这一句）。
返回纲要

b) 单链表实现
单链表的基本实现有两种：栈式、队列式。显然我们这里需要栈式链表（废话。。。）。
我们可以用下面这个结构体来作为链表的一个节点：

struct stackNode {
int data;
struct stackNode *next;
};

其中的data保存的是节点的数据（也就是入栈元素的值了），next是下一个节点的指针。
在此基础上完成和数组实现基本一致的一组函数：

//分配一个头节点，初始化，并返回其指针。如果分配失败，返回NULL。
struct stackNode * newStack() {
    struct stackNode *p = (struct stackNode *)malloc(sizeof(struct stackNode));
    if (p == NULL) {
        return NULL;
    }
    p->data = 0;
    p->next = NULL;
    return p;
}

//释放整个链表占用的空间（必须有这样一个循环）
void deleteStack(struct stackNode *llist) {
    struct stackNode *p;
    while (llist != NULL) {
        p = llist;
        llist = llist->next;
        free(p);
    }
}

//判断链表是否为空
int isEmpty(struct stackNode *llist) {
return (llist->next == NULL) ? 1 : 0;
}

//value入栈，返回1/0表示成功失败
int push(struct stackNode *llist, int value) {
    struct stackNode *p = (struct stackNode *)malloc(sizeof(struct stackNode));
    if (p == NULL) {
        return 0;
    }
    p->data = value;
    p->next = llist->next;
    llist->next = p;
    return 1;
}

//取栈顶元素
int top(struct stackNode *llist, int *value) {
    if (isEmpty(llist)) {
        return 0;
    }
    else {
        *value = llist->next->data;
        return 1;
    }
}

//栈顶元素出栈
int pop(struct stackNode *llist) {
    if (isEmpty(llist)) {
        return 0;
    }
    else {
        struct stackNode *p = llist->next;
        llist-next = p->next;
        free(p); //释放头节点next指向的那个节点
        return 1;
    }
}

可以看出，因为链表中需要大量使用指针，所以实现起来比较麻烦，稍不注意就可能导致非法访问或者内存泄漏。
返回纲要

c) 数组和链表实现的对比
· 数组的实现比较简单，链表比较麻烦
· 数组的空间是固定的，链表的可以动态增加
· 数组的速度比较快，链表的比较慢
· 数组的每一个元素不需要附加的空间，链表的每一个元素需要一个指针

----
3. 栈的应用
栈这个数据结构本身非常简单，但是应用却非常广泛。

a) 在函数调用中的作用
考虑4个简单的函数A、B、C、D，A调用B，B调用C，C调用D，在调用的过程中不存在直接或间接的递归。
那么，当执行A函数的时候程序的运行轨迹是：A->B->C->D->C->B->A，非常明显的先进后出顺序。
更深入一点的说，当函数A调用函数B的时候，必须保存下当前A函数运行到哪里了，以便B返回的时候可以继续运行。
我们把这个值记为PC(A)。以此类推，调用到D函数的时候，我们已经按顺序保存了PC(A)、PC(B)、PC(C)。
当D函数执行完毕返回的时候，需要取出PC(C)，从C函数中断的地方继续执行。然后是PC(B)。然后是PC(A)。
又是非常明显的FILO顺序，也就是说，应该使用栈来保存这样的数据。
因此，每个程序都必须包含一个运行时的栈；当然，它是由编译器负责完成了，不用程序员操心。

b) 在局部变量存储空间中的应用
一般来说，每个函数都会有自己的局部变量，这些变量在进入函数的时候分配，在退出函数的时候被释放，和函数的FILO顺序一致。
所以如果把它们放在栈上，就能够比较方便地对其管理，使得分配和释放的效率更高。（释放动作只要简单修改栈指针即可）
同时，由于数据集中性原理，如果把一些经常需要使用到的数据放在一块相对比较小的区域中，
Cache的命中率会相对比较大，所以在栈上存储局部变量，还可以获得更高的存取效率。（这里忽略直接使用寄存器的那种情况）
由于栈空间比较小（PC(win/linux)栈空间大小在MB级别），所以不能在函数中定义需要较大空间的数组、结构体等变量。
特别地，主函数main也是一个函数，同样受到这个限制。
解决的办法有
  · 定义成全局变量，在编译期固定使用的地址空间，程序再载入时就为其分配好。
  · 使用malloc函数分配空间，使用系统维护的"堆"空间。注：此"堆"不同于数据结构中的堆(heap)。详见内存管理类的资料。
* 栈空间和系统维护的"堆"空间的对比
  · 堆空间大，栈空间小
  · 堆效率低，栈效率高。此效率包括分配/回收的效率和存取的效率

c) 在算法中的应用
stack在算法中的应用非常多，这里列出其中几种，具体的不多讲了，具体的看相应的算法资料
· 进制转换
· 深度优先搜索算法(DFS)
· 如何找出多数元素。参考OJ题目：WOJ 1203 @ http://acm.whu.edu.cn/oak/problem/problem.jsp?problem_id=1203

欢迎扫码关注：