练习42：栈和队列 · 笨办法学C

# 练习42：栈和队列 > 原文：[Exercise 42: Stacks and Queues](http://c.learncodethehardway.org/book/ex42.html) > 译者：[飞龙](https://github.com/wizardforcel) 到现在为止，你已经知道了大多数用于构建其它数据结构的数据结构。如果你拥有一些`List`、`DArray`、`Hashmap` 和 `Tree`，你就能用他们构造出大多数其它的任何结构。你碰到的其它任何结构要么可以用它们实现，要么是它们的变体。如果不是的话，它可能是外来的数据结构，你可能不需要它。 `Stack`和`Queue`是非常简单的数据结构，它们是`List`的变体。它们是`List`的弱化或者转换形式，因为你只需要在`List`的一端放置元素。对于`Stack`，你只能能够在一段压入和弹出元素。而对于`Queue`，你只能够在开头压入元素，并在末尾弹出（或者反过来）。我能够只通过C预处理器和两个头文件来实现这两个数据结构。我的头文件只有21行的长度，并且实现了所有`Stack`和`Queue`的操作，不带有任何神奇的定义。我将会向你展示单元测试，你需要实现头文件来让它们正常工作。你不能创建`stack.c` 或 `queue.c`实现文件来通过测试，只能使用`stack.h` 和 `queue.h`来使测试运行。 ```c #include "minunit.h" #include <lcthw/stack.h> #include <assert.h> static Stack *stack = NULL; char *tests[] = {"test1 data", "test2 data", "test3 data"}; #define NUM_TESTS 3 char *test_create() { stack = Stack_create(); mu_assert(stack != NULL, "Failed to create stack."); return NULL; } char *test_destroy() { mu_assert(stack != NULL, "Failed to make stack #2"); Stack_destroy(stack); return NULL; } char *test_push_pop() { int i = 0; for(i = 0; i < NUM_TESTS; i++) { Stack_push(stack, tests[i]); mu_assert(Stack_peek(stack) == tests[i], "Wrong next value."); } mu_assert(Stack_count(stack) == NUM_TESTS, "Wrong count on push."); STACK_FOREACH(stack, cur) { debug("VAL: %s", (char *)cur->value); } for(i = NUM_TESTS - 1; i >= 0; i--) { char *val = Stack_pop(stack); mu_assert(val == tests[i], "Wrong value on pop."); } mu_assert(Stack_count(stack) == 0, "Wrong count after pop."); return NULL; } char *all_tests() { mu_suite_start(); mu_run_test(test_create); mu_run_test(test_push_pop); mu_run_test(test_destroy); return NULL; } RUN_TESTS(all_tests); ``` 之后是`queue_tests.c`，几乎以相同的方式来使用`Queue`： ```c #include "minunit.h" #include <lcthw/queue.h> #include <assert.h> static Queue *queue = NULL; char *tests[] = {"test1 data", "test2 data", "test3 data"}; #define NUM_TESTS 3 char *test_create() { queue = Queue_create(); mu_assert(queue != NULL, "Failed to create queue."); return NULL; } char *test_destroy() { mu_assert(queue != NULL, "Failed to make queue #2"); Queue_destroy(queue); return NULL; } char *test_send_recv() { int i = 0; for(i = 0; i < NUM_TESTS; i++) { Queue_send(queue, tests[i]); mu_assert(Queue_peek(queue) == tests[0], "Wrong next value."); } mu_assert(Queue_count(queue) == NUM_TESTS, "Wrong count on send."); QUEUE_FOREACH(queue, cur) { debug("VAL: %s", (char *)cur->value); } for(i = 0; i < NUM_TESTS; i++) { char *val = Queue_recv(queue); mu_assert(val == tests[i], "Wrong value on recv."); } mu_assert(Queue_count(queue) == 0, "Wrong count after recv."); return NULL; } char *all_tests() { mu_suite_start(); mu_run_test(test_create); mu_run_test(test_send_recv); mu_run_test(test_destroy); return NULL; } RUN_TESTS(all_tests); ``` 你应该在不修改测试文件的条件下，使单元测试能够运行，并且它应该能够通过`valgrind`而没有任何内存错误。下面是当我直接运行`stack_tests`时它的样子： ```sh $ ./tests/stack_tests DEBUG tests/stack_tests.c:60: ----- RUNNING: ./tests/stack_tests ---- RUNNING: ./tests/stack_tests DEBUG tests/stack_tests.c:53: ----- test_create DEBUG tests/stack_tests.c:54: ----- test_push_pop DEBUG tests/stack_tests.c:37: VAL: test3 data DEBUG tests/stack_tests.c:37: VAL: test2 data DEBUG tests/stack_tests.c:37: VAL: test1 data DEBUG tests/stack_tests.c:55: ----- test_destroy ALL TESTS PASSED Tests run: 3 $ ``` `queue_test`的输出基本一样，所以我在这里就不展示了。 ## 如何改进你可以做到的唯一真正的改进，就是把所用的`List`换成`DArray`。`Queue`数据结构难以用`DArray`实现，因为它要同时处理两端的节点。完全在头文件中来实现它们的缺点，是你并不能够轻易地对它做性能调优。你需要使用这种技巧，建立一种以特定的方式使用`List`的“协议”。做性能调优时，如果你优化了`List`，这两种数据结构都会有所改进。 ## 附加题 + 使用`DArray`代替`List`实现`Stack`，并保持单元测试不变。这意味着你需要创建你自己的`STACK_FOREACH`。