練習(xí)42：棧和隊(duì)列
譯者：飛龍
到現(xiàn)在為止死遭，你已經(jīng)知道了大多數(shù)用于構(gòu)建其它數(shù)據(jù)結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)洲守。如果你擁有一些List潘明、DArray誊爹、Hashmap 和 Tree怠晴，你就能用他們構(gòu)造出大多數(shù)其它的任何結(jié)構(gòu)熄诡。你碰到的其它任何結(jié)構(gòu)要么可以用它們實(shí)現(xiàn)，要么是它們的變體鳄虱。如果不是的話弟塞，它可能是外來的數(shù)據(jù)結(jié)構(gòu)，你可能不需要它拙已。
Stack和Queue是非常簡(jiǎn)單的數(shù)據(jù)結(jié)構(gòu)决记，它們是List的變體。它們是List的弱化或者轉(zhuǎn)換形式倍踪，因?yàn)槟阒恍枰?code>List的一端放置元素系宫。對(duì)于Stack，你只能能夠在一段壓入和彈出元素建车。而對(duì)于Queue扩借，你只能夠在開頭壓入元素，并在末尾彈出（或者反過來）缤至。
我能夠只通過C預(yù)處理器和兩個(gè)頭文件來實(shí)現(xiàn)這兩個(gè)數(shù)據(jù)結(jié)構(gòu)潮罪。我的頭文件只有21行的長度，并且實(shí)現(xiàn)了所有Stack和Queue的操作领斥，不帶有任何神奇的定義嫉到。
我將會(huì)向你展示單元測(cè)試，你需要實(shí)現(xiàn)頭文件來讓它們正常工作月洛。你不能創(chuàng)建stack.c 或 queue.c實(shí)現(xiàn)文件來通過測(cè)試何恶，只能使用stack.h 和 queue.h來使測(cè)試運(yùn)行。
#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：
#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);
你應(yīng)該在不修改測(cè)試文件的條件下细层，使單元測(cè)試能夠運(yùn)行，并且它應(yīng)該能夠通過valgrind而沒有任何內(nèi)存錯(cuò)誤唬涧。下面是當(dāng)我直接運(yùn)行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的輸出基本一樣今艺，所以我在這里就不展示了。
如何改進(jìn)
你可以做到的唯一真正的改進(jìn)爵卒，就是把所用的List換成DArray。Queue數(shù)據(jù)結(jié)構(gòu)難以用DArray實(shí)現(xiàn)撵彻，因?yàn)樗瑫r(shí)處理兩端的節(jié)點(diǎn)钓株。
完全在頭文件中來實(shí)現(xiàn)它們的缺點(diǎn)实牡，是你并不能夠輕易地對(duì)它做性能調(diào)優(yōu)。你需要使用這種技巧轴合，建立一種以特定的方式使用List的“協(xié)議”创坞。做性能調(diào)優(yōu)時(shí)，如果你優(yōu)化了List受葛，這兩種數(shù)據(jù)結(jié)構(gòu)都會(huì)有所改進(jìn)题涨。
附加題
- 使用
DArray代替List實(shí)現(xiàn)Stack，并保持單元測(cè)試不變总滩。這意味著你需要?jiǎng)?chuàng)建你自己的STACK_FOREACH纲堵。
