顺序结构：Stack/Queue

栈和队列

栈和队列用List来简单实现就好了。假设用nums数组：

• 栈：尾巴做栈顶

  • 压栈nums.append(val)，出栈val=nums.pop()

• 队列：nums[0]做头nums[-1]做尾

  • 入队nums.append(val)，出队val=nums.pop(0)

如果首尾都需要压入弹出，用双端队列deque队列就行了。

链表实现

其中分别加入了头尾节点，而不是把尾巴留空。这样方便我们实现removeFirst等方法可以来模拟栈或者队列的pop，push等方法。可以用哨兵技巧让head成为一个空节点，减少讨论情况。

主要功能：

• removeFirst()：O(1)删除头节点，并得到头节点的值 实现：直接删除并返回。若List为空，直接返回。

• insertFront(val)：O(1)在头部插入新节点 实现：在哨兵头节点后插入值为val的新节点

class ListNode:
    def __init__(self, val=None, next=None):
        self.val = val
        self.next = next

class LinkedList:
    def __init__(self):
        self.head = ListNode()

    def removeFront(self):
        if not self.head.next: return # empty
        node = self.head.next
        self.head.next = self.head.next.next
        return node.val
        
    def insertFront(self, val):
        node = ListNode(val, next=self.head.next)
        self.head.next = node

有时候如果能以O(1)的时间来得到链表中某节点ListNode的话（比如说在哈希链表中），我们想要删除某一个节点的话需要它左右两边的指针。那么双向链表就是一个更好的结构。

除了单向链表能够在O(1)时间里写查删头尾节点，双向链表的好处是能帮我们在O(1)时间删除任意一个节点，并保持链表原来的顺序。

下面是双向链表的简单实现。同样的，可以用哨兵技巧让head和tail成为空节点，减少讨论情况。

主要功能：

• remove(node)：O(1)时间删除一个节点，并维持原有DLL顺序 实现：假设node存在，则让node的前面连后面，后面连前面

• removeLast()：O(1)时间删除最后一个节点 实现：删除最后一个节点，并返回它的值。若DLL为空，直接返回。

• insertFront(node)：O(1)在头部插入节点 实现：直接插入节点

class ListNode(object):
    def __init__(self, val=None, key=None):
        self.val = val
        self.key = key
        self.prev = self.next = None
        
class DLL(object):
    def __init__(self):
        self.head = ListNode()
        self.tail = ListNode()
        self.head.next = self.tail
        self.tail.prev = self.head
        
    def remove(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev
        
    def removeLast(self):
        if self.head.next == self.tail: # empty
            return None
        last = self.tail.prev
        self.remove(last)
        return last
        
    def insertFront(self, node):
        node.next = self.head.next
        node.prev = self.head
        self.head.next = node
        node.next.prev = node

例题：字符串解码 [LC394]

输入：s = "3[a]2[bc]"
输出："aaabcbc"

输入：s = "3[a2[c]]"
输出："accaccacc"

递归解法

def decodeString(self, s, i=0):
    res, multi = "", 0
    while i < len(s):
        if s[i].isalpha(): res += s[i]
        elif s[i].isdigit(): multi = 10*multi + int(s[i])
        elif s[i]=="]": return res, i
        elif s[i]=="[":
            tmp, i = self.decodeString(s, i+1)
            res, multi = res+multi*tmp, 0
        i += 1
    return res

栈解法

变形