利用双端队列数据结构实现字符串反转的函数

双端队列（Double Ended Queue）是一种具有队列和栈性质的抽象数据类型。双端队列可以从两端进行插入和删除操作。利用双端队列数据结构可以实现字符串的反转。

下面是使用双端队列实现字符串反转的函数：

class Deque:
    def __init__(self):
        self.items = []

    def is_empty(self):
        return len(self.items) == 0

    def add_rear(self, item):
        self.items.append(item)

    def add_front(self, item):
        self.items.insert(0, item)

    def remove_rear(self):
        return self.items.pop()

    def remove_front(self):
        return self.items.pop(0)

    def size(self):
        return len(self.items)

def reverse_string(input_str):
    deque = Deque()
    for char in input_str:
        deque.add_rear(char)
    
    reversed_str = ""
    while not deque.is_empty():
        reversed_str += deque.remove_rear()
    
    return reversed_str

上述代码中，首先定义了一个双端队列类 Deque ，其中包含了常用的队列操作函数。然后，定义了一个 reverse_string 函数，该函数接受一个字符串作为输入，利用双端队列将字符串进行反转，并返回反转后的字符串。具体实现步骤如下：

1. 创建一个双端队列 deque。

2. 对输入的字符串进行遍历，将每一个字符依次添加到双端队列的尾部，实现字符的逆序排列。

3. 定义一个空字符串 reversed_str，用来保存反转后的字符串。

4. 当队列不为空时，从队列的尾部依次取出字符，并将其拼接到 reversed_str 末尾。

5. 返回反转后的字符串 reversed_str。

下面是使用例子：

input_str = "Hello, world!"
reversed_str = reverse_string(input_str)
print(reversed_str)

输出结果为：!dlrow ,olleH

以上就是利用双端队列数据结构实现字符串反转的函数及使用例子。双端队列的特性使得在操作队列时具有两端都可以进行插入和删除的灵活性，从而方便地实现字符串反转这一功能。