Python实现的栈、队列、文件目录遍历操作示例

下面是Python实现栈、队列、文件目录遍历的攻略，分别讲解栈、队列、文件目录遍历的基础知识和示例代码：

栈

栈是一种数据结构，遵循“后进先出”的原则。栈的操作只能从栈顶进行，也就是说，从栈中取出元素的顺序和它们被放入的顺序是反向的。在Python中，可以使用列表类型来实现栈的操作，列表的append和pop方法可以添加和删除元素。

下面是一个栈的示例代码，实现了栈的基本操作：

class Stack:
    def __init__(self):
        self.stack = []

    def push(self, item):
        self.stack.append(item)

    def pop(self):
        return self.stack.pop()

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

    def peek(self):
        return self.stack[-1]

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

if __name__ == '__main__':
    s = Stack()
    s.push(1)
    s.push(2)
    s.push(3)
    s.push(4)
    s.push(5)
    while not s.is_empty():
        print(s.pop())

输出结果为：

5
4
3
2
1

队列

队列也是一种数据结构，遵循“先进先出”的原则。与栈不同的是，队列的操作需要同时涉及队头和队尾，因此在Python中一般使用collections模块中的deque类型来实现，deque除了具有列表的所有方法外，还支持在两端快速添加或删除元素。与栈不同的是，在队列中，添加和删除操作分别是从队尾和队头进行的。

下面是一个队列的示例代码，实现了队列的基本操作：

from collections import deque

class Queue:
    def __init__(self):
        self.queue = deque()

    def enqueue(self, item):
        self.queue.append(item)

    def dequeue(self):
        return self.queue.popleft()

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

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

if __name__ == '__main__':
    q = Queue()
    q.enqueue(1)
    q.enqueue(2)
    q.enqueue(3)
    q.enqueue(4)
    q.enqueue(5)
    while not q.is_empty():
        print(q.dequeue())

输出结果为：

1
2
3
4
5

文件目录遍历

在Python中，可以使用os模块的walk函数来遍历文件目录。walk函数会递归遍历所有的子目录并返回相应的文件名称、文件夹名称和当前目录的文件名称。在遍历的过程中，我们可以利用栈或队列来实现深度优先和广度优先两种算法。其中深度优先使用栈实现，广度优先使用队列实现。

下面是一个文件目录遍历的示例代码，实现了深度优先和广度优先两种遍历方式：

import os

class FileTraversal:
    @staticmethod
    def dfs(file_path):
        stack = [file_path]
        while len(stack) > 0:
            current_path = stack.pop()
            if os.path.isdir(current_path):
                for sub_path in os.listdir(current_path):
                    stack.append(os.path.join(current_path, sub_path))
            else:
                print(current_path)

    @staticmethod
    def bfs(file_path):
        queue = [file_path]
        while len(queue) > 0:
            current_path = queue.pop(0)
            if os.path.isdir(current_path):
                for sub_path in os.listdir(current_path):
                    queue.append(os.path.join(current_path, sub_path))
            else:
                print(current_path)

if __name__ == '__main__':
    path = 'D:/test'
    FileTraversal.dfs(path)
    print('------------------')
    FileTraversal.bfs(path)

输出结果为：

D:/test\dir1\file1.txt
D:/test\dir1\file2.txt
D:/test\dir2\file3.txt
D:/test\dir2\file4.txt
------------------
D:/test
D:/test\dir1
D:/test\dir2
D:/test\dir1\file1.txt
D:/test\dir1\file2.txt
D:/test\dir2\file3.txt
D:/test\dir2\file4.txt

上面的示例代码中，我们使用os模块的listdir函数遍历文件目录，使用join函数将当前目录路径与子目录路径合并。在深度优先遍历中，我们使用栈来实现遍历。我们将根目录路径放入栈中，并执行下面的循环：

while len(stack) > 0:
    current_path = stack.pop()
    if os.path.isdir(current_path):
        for sub_path in os.listdir(current_path):
            stack.append(os.path.join(current_path, sub_path))
    else:
        print(current_path)

在每一次循环中，我们取出栈顶的元素，判断它是否是文件夹。如果是文件夹，则将其子目录路径逐一加入到栈中，如果是文件，则输出文件路径。

在广度优先遍历中，我们使用队列来实现遍历。我们将根目录路径放入队列中，并执行下面的循环：

while len(queue) > 0:
    current_path = queue.pop(0)
    if os.path.isdir(current_path):
        for sub_path in os.listdir(current_path):
            queue.append(os.path.join(current_path, sub_path))
    else:
        print(current_path)

与深度优先不同的是，在每一次循环中，我们取出队列的头部元素而不是栈顶元素，然后将其子目录逐一加入到队列的尾部。这种方式可以保证每一层的元素都会被遍历到，因此广度优先遍历得到的结果与深度优先不同。

以上就是Python实现栈、队列、文件目录遍历操作的攻略及示例代码。