Chinaunix首页 | 论坛 | 博客

嵌入式的那些事儿……firestm32.blog.chinaunix.net

首页　| 　博文目录　| 　关于我

Mrt-l

  • 博客访问： 388859
  • 博文数量： 55
  • 博客积分： 1907
  • 博客等级： 上尉
  • 技术积分： 869
  • 用 户 组： 普通用户
  • 注册时间： 2010-11-04 19:30
文章分类

全部博文（55）

文章存档

2011年（32）

2010年（23）

我的朋友
最近访客
推荐博文
相关博文
堆栈操作

分类： C/C++

2011-10-14 17:39:22

1、利用静态数组实现堆栈
  1. /*
  2.  * 利用静态数组实现堆栈
  3.  */

  5. #include <stdlib.h>
  6. #include <stdio.h>
  7. #include <assert.h>

  9. #define STACK_TYPE int
  10. #define STACK_SIZE 100

  12. static STACK_TYPE stack[STACK_SIZE];
  13. static int top_element = -1;

  15. int is_empty(void)
  16. {
  17.     return top_element == -1;
  18. }

  20. int is_full(void)
  21. {
  22.     return top_element == STACK_SIZE - 1;
  23. }

  25. void push(STACK_TYPE value)
  26. {
  27.     assert(!is_full());
  28.     stack[ top_element] = value;
  29. }

  31. STACK_TYPE pop(void)
  32. {
  33.     assert(!is_empty());
  34.     return stack[top_element--];
  35. }

  37. int main()
  38. {
  39.     int i;
  40.     push(0);
  41.     push(1);
  42.     push(2);
  43.     push(3);
  44.     push(4);

  46.     for(i=0; i <= top_element; i )
  47.         printf("M", stack[i]);
  48.     printf("\n");

  50.     printf(" pop=%d\n", pop());

  52.     for(i=0; i <= top_element; i )
  53.         printf("M", stack[i]);
  54.     printf("\n");

  56.   exit(0);
  57. }
2、利用动态数组实现堆栈
  1. /*
  2.  * 利用动态数组实现堆栈
  3.  */

  5. #include <stdlib.h>
  6. #include <stdio.h>
  7. #include <malloc.h>
  8. #include <assert.h>

  10. #define STACK_TYPE int
  11. #define STACK_SIZE 100

  13. static STACK_TYPE *stack;
  14. static size_t stack_size;
  15. static int top_element = -1;

  17. /*
  18.  * malloc 动态分配数组，由 stack 指针指向的内存区是连续的
  19.  * 可以通过 stack[] 这种数组的形式来对分配的内存进行操作。
  20.  */
  21. void creat_stack(size_t size)
  22. {
  23.     assert(stack ==0); //确保堆栈只创建一次
  24.     stack_size = size;
  25.     stack = malloc(stack_size * sizeof(STACK_TYPE));
  26.     assert(stack != NULL); //确保内存分配成功
  27. }

  29. void destroy_stack(void)
  30. {
  31.     assert(stack_size > 0); //确保堆栈已存在
  32.     stack_size = 0;
  33.     free(stack);
  34.     stack = NULL;
  35. }

  37. int is_empty(void)
  38. {
  39.     assert(stack_size > 0); //确保堆栈已存在，测试一个不存在的堆栈是否为空是没有意义的。
  40.     return top_element == -1;
  41. }

  43. int is_full(void)
  44. {
  45.     assert(stack_size > 0); //确保堆栈已存在，测试一个不存在的堆栈是否为满是没有意义的。
  46.     return top_element == stack_size - 1;
  47. }

  49. void push(STACK_TYPE value)
  50. {
  51.     assert(!is_full());
  52.     stack[ top_element] = value;
  53. }

  55. STACK_TYPE pop(void)
  56. {
  57.     assert(!is_empty());
  58.     return stack[top_element--];
  59. }

  61. int main()
  62. {
  63.     int i;
  64.     creat_stack(10);
  65.     
  66.     push(5);
  67.     push(6);
  68.     push(7);
  69.     push(8);
  70.     push(9);

  72.     for(i=0; i <= top_element; i )
  73.         printf("M", stack[i]);
  74.     printf("\n");

  76.     printf(" pop=%d\n", pop());
  77.     printf(" pop=%d\n", pop());

  79.     for(i=0; i <= top_element; i )
  80.         printf("M", stack[i]);
  81.     printf("\n");

  83.     destroy_stack();
  84.   exit(0);
  85. }
3、利用单链表实现堆栈，这个堆栈没有长度限制
  1. /*
  2.  * 利用单链表实现堆栈，这个堆栈没有长度限制。
  3.  */

  5. #include <stdlib.h>
  6. #include <stdio.h>
  7. #include <malloc.h>
  8. #include <assert.h>

  10. #define STACK_TYPE int
  11. #define FALSE     0

  13. typedef struct STACK_NODE{
  14.     STACK_TYPE value;
  15.     struct STACK_NODE *next;
  16. }StackNode;

  18. static struct STACK_NODE *stack = NULL;

  20. int is_empty(void)
  21. {
  22.     return stack == NULL;
  23. }

  25. int is_full(void)
  26. {
  27.     return FALSE;//堆栈没有长度限制，永远都不会满
  28. }

  30. void push(STACK_TYPE value)
  31. {
  32.     struct STACK_NODE *new_node;
  33.     new_node = malloc(sizeof(StackNode));
  34.     assert(new_node != NULL);

  36.     new_node->value = value;
  37.     new_node->next = stack;
  38.     stack = new_node;
  39. }

  41. void pop(void)
  42. {
  43.     struct STACK_NODE *first_node;
  44.     assert(!is_empty());
  45.     first_node = stack;
  46.     stack = first_node->next;
  47.     free(first_node);
  48. }

  50. void destroy_stack(void)
  51. {
  52.     while (stack != NULL)
  53.         pop();
  54. }

  56. STACK_TYPE top()
  57. {
  58.     assert(!is_empty());
  59.     return stack->value;
  60. }

  62. int main(void)
  63. {
  64.     struct STACK_NODE *ptr;    

  66.     push(10);
  67.     push(20);
  68.     push(30);
  69.     push(40);

  71.     for (ptr = stack; ptr != NULL; ptr = ptr->next)
  72.         printf("M", ptr->value);
  73.     printf("\n");

  75.     printf(" pop=%d\n", top());
  76.     pop();

  78.     for (ptr = stack; ptr != NULL; ptr = ptr->next)
  79.         printf("M", ptr->value);
  80.     printf("\n");

  82.     destroy_stack();
  83.   exit(0);
  84. }
 
阅读(2145) | 评论(0) | 转发(2) |
0

上一篇：如何利用客户端在CU发博客

下一篇：嵌入式面试题集锦

给主人留下些什么吧！~~
关于我们 | 关于IT168 | 联系方式 | 广告合作 | 法律声明 | 免费注册

Copyright 2001-2010 ChinaUnix.net All Rights Reserved 北京皓辰网域网络信息技术有限公司. 版权所有

感谢所有关心和支持过ChinaUnix的朋友们

16024965号-6