練習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`。