本系列博客习题来自《算法(第四版)》，算是本人的读书笔记，如果有人在读这本书的，欢迎大家多多交流。为了方便讨论，本人新建了一个微信群(算法交流)，想要加入的，请添加我的微信号：zhujinhui207407 谢谢。另外，本人的个人博客 http://www.kyson.cn 也在不停的更新中，欢迎一起讨论

算法(第4版)

知识点

• 链接栈或者（栈的链接实现）
• 链接队列或者（队列的链接实现）

1.3.47 可连接的队列、栈或 steque。为队列、栈或 steque（见练习 1.3.32）添加一个能够（破坏性地）链接两个同类对象的额外操作 catenation。

1.3.47 Catenable queues, stacks, or steques. Add an extra operation catenation that (de- structively) concatenates two queues, stacks, or steques (see Exercise 1.3.32). Hint : Use a circular linked list, maintaining a pointer to the last item.

分析

本人所有简书的算法文章详细分析已经移入小专栏：算法四习题详解，欢迎大家订阅

答案

链接栈的链接方法：

public void catenation(LinkedStack<Item> original) {
    Node newCopy;

    if (!original.isEmpty()) {

        Node current = original.topNode;
        while (current.next != null) {
            current = current.next;
        }
        current.next = topNode;
        topNode = original.topNode;
        N += original.size();
    }
}

链接队列的链接方法：

public void catenation(LinkedQueue<Item> q) {
    if (isEmpty()) {
        head = q.head;
        tail = q.tail;
        N = q.size();
    }
    else if (!q.isEmpty()) {
        tail.next = q.head;
        tail = q.tail;
        N += q.size();
    }
}

扩展阅读

链接栈（Link Stack）———— 栈的链接实现
链接队列（Link Queue）——队列的链接实现

广告

我的首款个人开发的APP壁纸宝贝上线了，欢迎大家下载。