顺序栈代码实现

"""
顺序存储的方式实现栈
思路：
    1、栈 ：LIFO 后进先出
    2、设计
       列表尾部作为栈顶（入栈、出栈操作）
       列表头部作为栈底（不进行任何操作）
"""
class Stack:
    def __init__(self):
        """初始化一个空栈"""
        self.elems = []
def is_empty(self):
    """判断栈是否为空栈"""
    return self.elems == []

def push(self, item):
    """入栈: 相当于在链表尾部添加1个元素"""
    self.elems.append(item)

def destack(self):
    """出栈: 相当于在列表尾部弹出1个元素"""
    if self.is_empty():
        raise Exception('destack from empty stack')
    return self.elems.pop()
if __name__ == '__main__':
    s = Stack()
    # 栈(栈底->栈顶): 100 200 300
    s.push(100)
    s.push(200)
    s.push(300)
    # 终端1: 300 200 100 异常
    print(s.destack())
    print(s.destack())
    print(s.destack())
    print(s.destack())

链式栈代码实现

"""
链式存储方式实现栈
思路：
    1、栈：LIFO 后进先出
    2、设计
       链表头部作为栈顶（入栈、出栈操作）
       链表尾部作为栈底（不进行任何操作）
"""
class Node:
    """节点类"""
    def __init__(self, value):
        self.value = value
        self.next = None

class LinkListStack:
    def __init__(self):
        """初始化一个空栈"""
        self.head = None
def is_empty(self):
    """判断是否为空栈"""
    return self.head == None

def push(self, item):
    """入栈操作: 相当于在链表的头部添加一个节点"""
    node = Node(item)
    node.next = self.head
    self.head = node

def pop(self):
    """出栈操作: 相当于删除链表头节点"""
    if self.is_empty():
        raise Exception('pop from empty LinkListStack')
    item = self.head.value
    self.head = self.head.next

    return item
if __name__ == '__main__':
    s = LinkListStack()
    # 栈（栈底->栈顶）：300 200 100
    s.push(100)
    s.push(200)
    s.push(300)
    # 终端1: 300
    print(s.pop())
    # 终端2: False
    print(s.is_empty())

定义

队列是限制在两端进行插入操作和删除操作的线性表，允许进行存入操作的一端称为"队尾"，允许进行删除操作的一端称为"队头"

特点

1) 队列只能在队头和队尾进行数据操作
2) 队列模型具有先进先出规律（FIFO）

顺序队列代码实现

"""
顺序存储方式去实现队列模型
思路：
    1、队列：FIFO 先进先出,队尾负责入队,队头负责出队
    2、设计：
       列表头部作为队头,负责出队
       列表尾部作为队尾,负责入队
"""
class Queue:
    def __init__(self):
        """初始化一个空队列"""
        self.elems = []
def is_empty(self):
    """判断队列是否为空"""
    return self.elems == []

def enqueue(self, item):
    """队尾入队: append(item)"""
    self.elems.append(item)

def dequeue(self):
    """队头出队: pop(0)"""
    if self.is_empty():
        raise Exception('dequeue from empty Queue')
    return self.elems.pop(0)
if __name__ == '__main__':
    q = Queue()
    # 队列: 100 200 300
    q.enqueue(100)
    q.enqueue(200)
    q.enqueue(300)
    # 终端1: 100
    print(q.dequeue())
    # 终端2: False
    print(q.is_empty())

链式队列代码实现

"""
链式存储方式去实现队列
思路：
    1、队列：FIFO 先进先出
    2、设计：
       链表头部作为队头,负责出队操作
       链表尾部作为队尾,负责入队操作
"""
class Node:
    def __init__(self, value):
        self.value = value
        self.next = None

class LinkListQueue:
    def __init__(self):
        """初始化一个空队列"""
        self.head = None
def is_empty(self):
    """判断队列是否为空"""
    return self.head == None

def enqueue(self, item):
    """队尾入队: 相当于在链表尾部添加一个节点"""
    node = Node(item)
    # 空队列情况
    if self.is_empty():
        self.head = node
        return
    # 非空队列
    cur = self.head
    while cur.next:
        cur = cur.next
    # 循环结束后,cur一定是指向了原链表尾节点
    cur.next = node
    node.next = None

def dequeue(self):
    """队头出队: 相当于删除链表头节点"""
    if self.is_empty():
        raise Exception('dequeue from empty LinkListQueue')
    cur = self.head
    # 删除头节点
    self.head = self.head.next

    return cur.value
if __name__ == '__main__':
    q = LinkListQueue()
    # 队列: 100 200 300
    q.enqueue(100)
    q.enqueue(200)
    q.enqueue(300)
    # 终端1: 100
    print(q.dequeue())
    # 终端2: False
    print(q.is_empty())

栈和队列练习一

题目描述+试题解析

【1】题目描述
    用两个栈来实现一个队列，完成队列的 Push 和 Pop 操作。队列中的元素为 int 类型

【2】试题解析
    1、队列特点：先进先出（时刻铭记保证先进先出）
    2、栈 A 用来做入队列，栈 B 用来做出队列，当栈 B 为空时，栈 A 全部出栈到栈 B，栈B 再出栈(即出队列)
    3、精细讲解
      stack_a: 入队列（队尾）
      stack_b: 出队列（队头）
  stack_a队尾: [1,2,3]
  stack_b队头: []
     stack_b.append(stack_a.pop()) # [3,2,1]
     stack_b.pop()  # 1</code></pre></li>
代码实现
"""
用两个栈来实现一个队列，完成队列的 Push 和 Pop 操作。队列中的元素为 int 类型
思路：
    1、明确目标：实现队列（FIFO）
    2、实现载体：2个栈（LIFO）
    3、设计（计划使用顺序栈模型,而不使用链式栈模型）
       栈A(列表A)：入队
       栈B(列表B)：出队
       最终实现先进先出的效果,队列模型嘎然而生
"""
class Solution:
    def __init__(self):
        """初始化2个顺序栈"""
        self.stack_a = []
        self.stack_b = []
def push(self, item):
    """入队操作：相当于在stack_a中添加一个元素"""
    self.stack_a.append(item)

def pop(self):
    """出队操作：相当于在stack_b中弹出一个元素"""
    # 先从栈B中pop(),当B栈为空的时候,再去判断A栈是否为空
    if self.stack_b:
        return self.stack_b.pop()

    # B栈为空时,判断A栈,把A栈中所有的元素再次添加到B栈中
    while self.stack_a:
        self.stack_b.append(self.stack_a.pop())

    # 循环结束后,A栈中所有的元素又全部到的B栈中
    if self.stack_b:
        return self.stack_b.pop()
if __name__ == '__main__':
    s = Solution()
    # 入栈: 100 200 300
    s.push(100)
    s.push(200)
    s.push(300)
    # 终端1: 100
    print(s.pop())
    print(s.pop())
    print(s.pop())

定义
树（Tree）是n（n≥0）个节点的有限集合T，它满足两个条件：有且仅有一个特定的称为根（Root）的节点；其余的节点可以分为m（m≥0）个互不相交的有限集合T1、T2、……、Tm，其中每一个集合又是一棵树，并称为其根的子树（Subtree）