程序员之数据结构教程一：堆栈

本帖最后由 2gua 于 2010-3-3 21:18 编辑

[摘自：]

1.先不说话，看一段C语言的实现
如果看不懂，就看第二遍，第三遍。。。
view source
print?
01        #include
02        #include
03        #include
04        typedef int data_t;
05        typedef struct _stack_t {
06        data_t data;
07        struct _stack_t *prev,*next;
08        }stack_t;
09        stack_t *stack_top,*stack_bottom;
10        int initial_stack(void)
11        {
12        stack_top==malloc(sizeof(stack_t));
13        if(stack_top == NULL)
14        return -1;
15        stack_bottom = stack_top;
16        stack_top->next=NULL;
17        stack_top->prev=NULL;
18        return 0;
19        }
20        int stack_empty(stack_t *stack_top)
21        {
22        return (stack_top->prev==NULL);
23        }
24        int push(stack_t**p_stack_top,data_t* pdata)
25        {
26        stack_t* new_top;
27        if((new_top=malloc(sizeof(stack_t))) == NULL)
28        return -1;
29        memcpy(&(new_top->data),pdata,sizeof(data_t));
30        (*p_stack_top)->next = new_top;
31        new_top->next = NULL;
32        new_top->prev = *p_stack_top;
33        *p_stack_top = new_top;
34        return 0;
35        }
36        int pop(stack_t**p_stack_top)
37        {
38        if(stack_empty(*p_stack_top))
39        return -1;
40        *p_stack_top = (*p_stack_top)->prev;
41        free((*p_stack_top)->next);
42        (*p_stack_top)->next = NULL;
43        return 0;
44        }
2.简单的来说，堆栈就是一个数据结构（严格说来，堆和栈是两个不同的概念，但一般我们习惯合起来说，实际上叫栈是更科学的） 只允许先进后出通常被称为LIFO先进后出或LIFO后进先出数据结构。你可以把它想象为一个有底的竹筒，把乒乓球放进去，最后放进去的球最先取出，要取出最底下的球，必须先把最顶层的球一个一个依次取出。 Stack通过两个核心方法访问数据——Push(item)，将数据压入堆栈；Pop()则是将数据弹出堆栈，并返回其值。一个Stack可以通过一个垂直的数据元素集合来形象地表示。当元素压入堆栈时，新元素被放到所有其他元素的顶端，弹出时则从堆栈顶端移除该项。
3. PHP提供 array_push() 和 array_pop()函数，可以利用数组实现基本堆栈操作。下面是一个提供全部堆栈常用操作的函数库。【下述代码来自于某本PHP5编程的图书】
view source
print?
01        02        // A library to implement stacks in PHP via arrays
03        // The Initialize function creates a new stack:
04        function &stack_initialize() {
05        // In this case, just return a new array
06        $new = array();
07        return $new;
08        }
09        // The destory function will get rid of a stack
10        function stack_destroy(&$stack) {
11        // Since PHP is nice to us, we can just use unset
12        unset($stack);
13        }
14        // The push operation on a stack adds a new value unto the top of the stack
15        function stack_push(&$stack, $value) {
16        // We are just adding a value to the end of the array, so can use the
17        // [] PHP Shortcut for this. It's faster than usin array_push
18        $stack[] = $value;
19        }
20        // Pop removes the top value from the stack and returns it to you
21        function stack_pop(&$stack) {
22        // Just use array pop:
23        return array_pop($stack);
24        }
25        // Peek returns a copy of the top value from the stack, leaving it in place
26        function stack_peek(&$stack) {
27        // Return a copy of the value on top of the stack (the end of the array)
28        return $stack[count($stack)-1];
29        }
30        // Size returns the number of elements in the stack
31        function stack_size(&$stack) {
32        // Just using count will give the proper number:
33        return count($stack);
34        }
35        // Swap takes the top two values of the stack and switches them
36        function stack_swap(&$stack) {
37        // Calculate the count:
38        $n = count($stack);
39         
40        // Only do anything if count is greater than 1
41        if ($n > 1) {
42        // Now save a copy of the second to last value
43        $second = $stack[$n-2];
44        // Place the last value in second to last place:
45        $stack[$n-2] = $stack[$n-1];
46        // And put the second to last, now in the last place:
47        $stack[$n-1] = $second;
48        }
49        }
50        // Dup takes the top value from the stack, duplicates it,
51        // and adds it back onto the stack
52        function stack_dup(&$stack) {
53        // Actually rather simple, just reinsert the last value:
54        $stack[] = $stack[count($stack)-1];
55        }
56        // Let's use these to create a small stack of data and manipulate it.
57        // Start by adding a few numbers onto it, making it: 73 74 5
58        $mystack =& stack_initialize();
59        stack_push($mystack, 73);
60        stack_push($mystack, 74);
61        stack_push($mystack, 5);
62        // Now duplicate the top, giving us: 73 74 5 5
63        stack_dup($mystack);
64        // Check the size now, it should be 4
65        echo '

Stack size is: ', stack_size($mystack), '

';
66        // Now pop the top, giving us: 5
67        echo '

Popped off the value: ', stack_pop($mystack), '

';
68        // Next swap the top two values, leaving us with: 73 5 74
69        stack_swap($mystack);
70        // Peek at the top element to ensure it is 74
71        echo '

Current top element is: ', stack_peek($mystack), '

';
72        // Now destroy it, we are done.
73        stack_destroy($mystack);
74        ?>
如果想要更完美的实现堆栈，那就用SPL stack，因为PHP的数组虽然可以模拟堆栈，但很容易破坏其结构。


    SPL 的 SplStack 对象则严格以堆栈的形式描述数据，并提供对应的方法。同时，这样的代码应该也能理解它在操作堆栈而非某个数组，从而能让你的同伴更好的理解相应的代码，并且它更快。

4.栈有什么用？
我想最经典的就是用在进制转换，表达式求值，迷宫路径求解了。
迷宫图案，白色代表通道，黑色代表墙。
迷宫入口坐标(1,1),出口坐标(8,8)
  0 1 2 3 4 5 6 7 8 9
  0■■■■■■■■■■
  1■□□■□□□■□■
  2■□□■□□□■□■
  3■□□□□■■□□■
  4■□■■■□□□□■
  5■□□□■□□□□■
  6■□■□□□■□□■
  7■□■■■□■■□■
  8■■□□□□□□□■
  9■■■■■■■■■■
求迷宫中一条从入口到出口的路径。
这个问题留给有强烈求知欲的同学来完成。（据说能做出这个题的人不会超过1%）