堆栈和队列

堆栈

定义

堆栈是一种后进先出(LIFO)的数据结构,在下推堆栈中,只允许两种操作:对象入堆栈,并将对象从堆栈中弹出。元素只能在堆栈顶部添加和删除。push将对象添加到堆栈顶部,pop从顶部删除对象。

堆栈和队列

一个很好理解的例子,有一沓书,你可以只拿走(删除)顶部的书,也可以在顶部添加新书。

应用

  • 堆栈最简单应用是反转一个单词。你将给定的单词逐个字母推入堆栈(压栈),然后从堆栈中弹出字母(弹栈)。
  • 文本编辑器中的”撤销“机制;此操作是通过将所有文本更改保存在堆栈中来完成的。
  • 回溯。想想迷宫中如何找到出口的路呢?
  • 语言处理:
    • 参数和局部变量的空间是使用堆栈在内部创建的
    • 编译器对匹配大括号的语法检查是通过使用堆栈实现的
    • 支持递归

给定一个字符串,{xxx[xxx{xxx}]xx{x[xxx]xxx{xxx}xx}x}

判断其中的 {}[]() 是否成对出现

  • 实现
# test_stack_and_queue.py
import pytest


class Stack:
    """
    创建一个模拟stack堆栈
    """
    def __init__(self):
        self._data = []

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

    def pop(self):
        self._data.pop()

    def top(self):
        return self._data[-1]

    def get_size(self):
        if len(self._data) == 0:
            return True
        else:
            return False

    def get_data(self):
        return self._data


class TestStack:
    """
    创建一个测试类
    """
    def setup(self):
        self.stack = Stack()

    def pattern(self, data):
        brackets_dict = {")": "(", "]": "[", "}": "{"}
        for p in data:
            if p in "{[(":
                self.stack.push(p)
            elif p in ")]}":
                """处理stack中_data无数据情况"""
                try:
                    top = self.stack.top()
                    self.stack.pop()
                    """判断括号是否相对应"""
                    if brackets_dict[p] != top:
                        return False
                except IndexError:
                    return False
        return self.stack.get_size()

    """断言验证"""
    def test_pattern_1(self):
        test_data = '{xxx[xxx{xxx}]xx{x[xxx]xxx{xxx}xx}x}'
        assert self.pattern(test_data)== True

    def test_pattern_2(self):
        assert self.pattern('{@')==False

    def test_pattern_3(self):
        assert self.pattern('{}')==True

    def test_pattern_4(self):
        assert self.pattern("{}{}{}[]()")==True

if __name__ == '__main__':
    pytest.main(['-s'])
"""
test_stack_and_queue.py ....

============================== 4 passed in 0.02s ==============================
"""

队列

队列是一种先进先出(FIFO)的数据结构,一个很好理解的例子是饭堂广场的一排学生。新添加到队列后面的行,而移除(或服务)发生在前面,入队意味着将一个对象插入到队列的后面,出队意味着删除前面的项目。

  • 实现

模拟一个先进先出的数据结构,在队列尾部追加数据,然后在队列头部弹出数据。

class Queue:

    def __init__(self):
        self._data = []

    def put(self, item):
        self._data.append(item)

    def get(self):
        result = self._data[0]
        self._data.remove(result)
        return result
    
if __name__ == '__main__':
    """测试"""
    q = Queue()
    q.put('张三')
    q.put('李四')
    q.put('王五')
    print(q.get())
    print(q.get())
    print(q.get())
"""
张三
李四
王五
"""

参考资料

https://www.andrew.cmu.edu/course/15-121/lectures/Stacks and Queues/Stacks and Queues.html

上一篇:Android系统Recovery工作原理之使用update.zip升级过程---updater-script脚本语法简介以及执行流程(转)


下一篇:CTFHub技能书解题笔记-文件上传-文件头检查