练习42:栈和队列

原文:Exercise 42: Stacks and Queues

译者:飞龙

到现在为止,你已经知道了大多数用于构建其它数据结构的数据结构。如果你拥有一些ListDArrayHashmapTree,你就能用他们构造出大多数其它的任何结构。你碰到的其它任何结构要么可以用它们实现,要么是它们的变体。如果不是的话,它可能是外来的数据结构,你可能不需要它。

StackQueue是非常简单的数据结构,它们是List的变体。它们是List的弱化或者转换形式,因为你只需要在List的一端放置元素。对于Stack,你只能能够在一段压入和弹出元素。而对于Queue,你只能够在开头压入元素,并在末尾弹出(或者反过来)。

我能够只通过C预处理器和两个头文件来实现这两个数据结构。我的头文件只有21行的长度,并且实现了所有StackQueue的操作,不带有任何神奇的定义。

我将会向你展示单元测试,你需要实现头文件来让它们正常工作。你不能创建stack.cqueue.c实现文件来通过测试,只能使用stack.hqueue.h来使测试运行。

  1. #include "minunit.h"
  2. #include <lcthw/stack.h>
  3. #include <assert.h>
  4. static Stack *stack = NULL;
  5. char *tests[] = {"test1 data", "test2 data", "test3 data"};
  6. #define NUM_TESTS 3
  7. char *test_create()
  8. {
  9. stack = Stack_create();
  10. mu_assert(stack != NULL, "Failed to create stack.");
  11. return NULL;
  12. }
  13. char *test_destroy()
  14. {
  15. mu_assert(stack != NULL, "Failed to make stack #2");
  16. Stack_destroy(stack);
  17. return NULL;
  18. }
  19. char *test_push_pop()
  20. {
  21. int i = 0;
  22. for(i = 0; i < NUM_TESTS; i++) {
  23. Stack_push(stack, tests[i]);
  24. mu_assert(Stack_peek(stack) == tests[i], "Wrong next value.");
  25. }
  26. mu_assert(Stack_count(stack) == NUM_TESTS, "Wrong count on push.");
  27. STACK_FOREACH(stack, cur) {
  28. debug("VAL: %s", (char *)cur->value);
  29. }
  30. for(i = NUM_TESTS - 1; i >= 0; i--) {
  31. char *val = Stack_pop(stack);
  32. mu_assert(val == tests[i], "Wrong value on pop.");
  33. }
  34. mu_assert(Stack_count(stack) == 0, "Wrong count after pop.");
  35. return NULL;
  36. }
  37. char *all_tests() {
  38. mu_suite_start();
  39. mu_run_test(test_create);
  40. mu_run_test(test_push_pop);
  41. mu_run_test(test_destroy);
  42. return NULL;
  43. }
  44. RUN_TESTS(all_tests);

之后是queue_tests.c,几乎以相同的方式来使用Queue

  1. #include "minunit.h"
  2. #include <lcthw/queue.h>
  3. #include <assert.h>
  4. static Queue *queue = NULL;
  5. char *tests[] = {"test1 data", "test2 data", "test3 data"};
  6. #define NUM_TESTS 3
  7. char *test_create()
  8. {
  9. queue = Queue_create();
  10. mu_assert(queue != NULL, "Failed to create queue.");
  11. return NULL;
  12. }
  13. char *test_destroy()
  14. {
  15. mu_assert(queue != NULL, "Failed to make queue #2");
  16. Queue_destroy(queue);
  17. return NULL;
  18. }
  19. char *test_send_recv()
  20. {
  21. int i = 0;
  22. for(i = 0; i < NUM_TESTS; i++) {
  23. Queue_send(queue, tests[i]);
  24. mu_assert(Queue_peek(queue) == tests[0], "Wrong next value.");
  25. }
  26. mu_assert(Queue_count(queue) == NUM_TESTS, "Wrong count on send.");
  27. QUEUE_FOREACH(queue, cur) {
  28. debug("VAL: %s", (char *)cur->value);
  29. }
  30. for(i = 0; i < NUM_TESTS; i++) {
  31. char *val = Queue_recv(queue);
  32. mu_assert(val == tests[i], "Wrong value on recv.");
  33. }
  34. mu_assert(Queue_count(queue) == 0, "Wrong count after recv.");
  35. return NULL;
  36. }
  37. char *all_tests() {
  38. mu_suite_start();
  39. mu_run_test(test_create);
  40. mu_run_test(test_send_recv);
  41. mu_run_test(test_destroy);
  42. return NULL;
  43. }
  44. RUN_TESTS(all_tests);

你应该在不修改测试文件的条件下,使单元测试能够运行,并且它应该能够通过valgrind而没有任何内存错误。下面是当我直接运行stack_tests时它的样子:

  1. $ ./tests/stack_tests
  2. DEBUG tests/stack_tests.c:60: ----- RUNNING: ./tests/stack_tests
  3. ----
  4. RUNNING: ./tests/stack_tests
  5. DEBUG tests/stack_tests.c:53:
  6. ----- test_create
  7. DEBUG tests/stack_tests.c:54:
  8. ----- test_push_pop
  9. DEBUG tests/stack_tests.c:37: VAL: test3 data
  10. DEBUG tests/stack_tests.c:37: VAL: test2 data
  11. DEBUG tests/stack_tests.c:37: VAL: test1 data
  12. DEBUG tests/stack_tests.c:55:
  13. ----- test_destroy
  14. ALL TESTS PASSED
  15. Tests run: 3
  16. $

queue_test的输出基本一样,所以我在这里就不展示了。

如何改进

你可以做到的唯一真正的改进,就是把所用的List换成DArrayQueue数据结构难以用DArray实现,因为它要同时处理两端的节点。

完全在头文件中来实现它们的缺点,是你并不能够轻易地对它做性能调优。你需要使用这种技巧,建立一种以特定的方式使用List的“协议”。做性能调优时,如果你优化了List,这两种数据结构都会有所改进。

附加题

  • 使用DArray代替List实现Stack,并保持单元测试不变。这意味着你需要创建你自己的STACK_FOREACH