数据结构之栈与队列

佚名 6年前 (2019-04-17) 随笔 1313人围观抢沙发百度已收录

一栈的简介

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

栈是一个数据集合，可以理解为只能在一段进行插入或删除操作的列表
栈的特点：后进先出
栈的概念：栈顶，栈底
栈的操作：

进栈(压栈)：push
出栈：pop
取栈顶：gettop

使用一般的列表结构可实现栈

进栈： li.append
出栈： li.pop
取栈顶: li[-1]

Python代码实现栈：

class stack:

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

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

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

    def get_top(self):
        if len(self.stack) > 0:
            return self.stack[-1]
        else:
            return None

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

sta = stack()
sta.stack = [1, 2]
sta.push(5)
print(sta.pop())
print(sta.pop())
print(sta.pop())
print(sta.is_empty())

二栈的应用示例 —— 括号匹配问题

括号匹配问题：给一个字符串,其中包括小括号，中括号，大括号，求该字符串中的括号是否匹配
例如：

()()[]{} 匹配
([{()}]) 匹配
[]( 不匹配
[(]) 不匹配

def brace_match(s):
    match = {'}': '{', ']': '[', ')': '('}
    stack = Stack()
    for ch in s:
        if ch in {'(', '[', '{'}:
            stack.push(ch)
        else:
            if stack.is_empty():
                return False
            elif stack.get_top() == match[ch]:
                stack.pop()
            else:  # stack.get_top() != match[ch]
                return False

    return '匹配成功'


print(brace_match(["{", "(", ")", "}"]))

三队列的简介

队列是一个数据集合，仅允许在列表的一端进行插入，另一端进行删除，
进行插入的一端称为队尾（rear），插入动作称之为进队或入队
进行删除的一端称之为对头（front），删除动作称为出队
队列的性质：先进先出

双向队列：对列的两端都允许进行进队和出队操作

队列的实现

队列能否简单用列表实现？为什么？

初步设想：列表+两个下标指针
创建一个列表和两个变量，front变量指向队首，rear变量指向队尾。初始时，front和rear都为0。
进队操作：元素写到li[rear]的位置，rear自增1。
出队操作：返回li[front]的元素，front自减1。

队列的实现原理-----环形对列

环形队列：当队尾指针front == Maxsize + 1时，再前进一个位置就自动到0。

实现方式：求余数运算
队首指针前进1：front = (front + 1) % MaxSize
队尾指针前进1：rear = (rear + 1) % MaxSize
队空条件：rear == front

对列的内置模块

from collections import deque
queue = deque()#创建队列
queue.append('first')
queue.append('second')
queue.append('third')
print(queue.popleft())
print(queue.popleft())
print(queue.popleft())#出队,,先进先出
print([i for i in queue])  #查看队列里的元素

queue.appendleft('one')#双向队列队首进队
queue.appendleft('two')#双向队列队首进队
queue.appendleft('five')#双向队列队首进队
print(queue.pop())
print(queue.pop())#双向队列从队尾出队
print([i for i in queue])



#单向队列
from queue import Queue
q = Queue()
q.put('a')
q.put('b')
q.put('c')
print(q.get())  #a