# 顺序结构：Stack/Queue

## 栈和队列

![](https://3265673997-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MY_rO03Mc0ssTMstQFR%2F-MYqN0zGLs8cdbh8bn5E%2F-MYqtYyw2gdOxvaOnjj1%2FScreen%20Shot%202021-04-21%20at%205.06.23%20PM.png?alt=media\&token=a8c6b7d6-60ab-4ddd-91a7-27734193e594)

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

* **栈**：尾巴做栈顶
  * 压栈`nums.append(val)`，出栈`val=nums.pop()`
* **队列**：`nums[0]`做头`nums[-1]`做尾
  * 入队`nums.append(val)`，出队`val=nums.pop(0)`

如果首尾都需要压入弹出，用双端队列[deque](https://docs.python.org/3/library/collections.html#collections.deque)队列就行了。

## 链表实现

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

主要功能：

* `removeFirst()`：O(1)删除头节点，并得到头节点的值\
  实现：直接删除并返回。若List为空，直接返回。
* `insertFront(val)`：O(1)在头部插入新节点\
  实现：在哨兵头节点后插入值为val的新节点

```python
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)在头部插入节点\
  实现：直接插入节点

```python
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\]](https://leetcode-cn.com/problems/decode-string/)

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

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

{% tabs %}
{% tab title="递归解法" %}

```python
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
```

{% endtab %}

{% tab title="栈解法" %}

```python
def decodeString(s):
    if not s: return ""
    res, num = "", 0
    stack = []
    for c in s:
        if c.isalpha(): res += c
        elif c.isdigit(): num = 10*num+int(c)
        elif c=="]":
            pre_res, cur_num = stack.pop()
            res = pre_res + cur_num*res
        elif c=="[":
            stack.append((res, num))
            res, num = "", 0
    return res
```

{% endtab %}

{% tab title="变形" %}

```python
def printrepeat(s, i=0):
    res = ""
    while i < len(s):
        c = s[i]
        if c=="(":
            nxt, i = printrepeat(s, i+1)
            res += nxt
        elif c==")":
            repeat = int(s[i+2])
            i += 4
            return res*repeat, i
        else:
            res += c
            i += 1
    return res

s = "((a){2}b){3}"
printrepeat(s) # aabaabaab
```

{% endtab %}
{% endtabs %}