练习42：栈和队列

原文：Exercise 42: Stacks and Queues

译者：飞龙

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

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

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

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

# include "minunit.h"# include # include static Stack *stack = NULL;char *tests[] = {"test1 data", "test2 data", "test3 data"};# define NUM_TESTS 3char *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 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 # include static Queue *queue = NULL;char *tests[] = {"test1 data", "test2 data", "test3 data"};# define NUM_TESTS 3char *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 value);    }    for(i = 0; i valgrind而没有任何内存错误。下面是当我直接运行stack_tests时它的样子：

$ ./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，这两种数据结构都会有所改进。## 附加题1. 使用DArray代替List实现Stack，并保持单元测试不变。这意味着你需要创建你自己的STACK_FOREACH。#c、lxthw#

版权声明

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处。如若内容有涉嫌抄袭侵权/违法违规/事实不符，请点击 举报 进行投诉反馈！