数据结构-1-栈、队列和链表

发表于 | 更新于 | 分类于 | 评论数： | 阅读次数：

栈

先进后出；push；pop

两种存储表示方式：顺序栈，链式栈

用数组实现一个顺序栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
# coding:utf-8

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

    def isempty(self):
        if (len(self.stack) == 0):
            return True
        return False

    def push(self, e):
        return self.stack.append(e)

    def pop(self):
        if not self.isempty():
            self.stack.pop()

    def print_info(self):
        print(self.stack)


stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)
stack.print_info()  # [1, 2, 3]
stack.pop()
stack.print_info()  # [1, 2]
stack.push(4)
stack.print_info()  # [1, 2, 4]

用链表实现一个链式栈

使用head表示栈顶

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Node:
    def __init__(self, data):
       self.data = data
       self.next = None
 
class Stack:
    def __init__(self):
        self.head = None
 
    def push(self, data):
        if self.head is None:
            self.head = Node(data)
        else:
            new_node = Node(data)
            new_node.next = self.head
            self.head = new_node
 
    def pop(self):
        if self.head is None:
            return None
        else:
            popped = self.head.data
            self.head = self.head.next
            return popped

编程模拟实现一个浏览器的前进、后退功能

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
# coding:utf-8

class Browser:
    def __init__(self):
        self.stack = []
        self.index = -1

    def isempty(self):
        if (len(self.stack) == 0):
            return True
        return False

    def access(self, e):
        self.stack.append(e)
        self.index += 1
        return e

    def forward(self):
        self.index = min(self.index-1, len(self.stack)-1)
        return self.stack[self.index]

    def back(self):
        if not self.isempty():
            self.index = max(self.index - 1, 0)
            return self.stack[self.index]


bw = Browser()
print(bw.access(1))
print(bw.access(2))
print(bw.access(3))
print(bw.forward())
print(bw.access(4))
print(bw.back())
print(bw.back())

"""
1
2
3
before 2
after 1
2
4
2
1
"""

对应的 LeetCode 练习题

Valid Parentheses（有效的括号）

英文版：https://leetcode.com/problems/valid-parentheses/

中文版：https://leetcode-cn.com/problems/valid-parentheses/

代码见：leetcode-20-有效的括号

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution(object):
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        re_dict = {"(": ")", "{": "}", "[": "]"}
        stack = []
        for t in s:
            if t not in re_dict:
                if len(stack) == 0:
                    return False
                elif stack[-1] != t:
                    return False
                else:
                    stack.pop()
            else:
                stack.append(re_dict[t])
        if (len(stack)):
            return False
        return True

Longest Valid Parentheses（最长有效的括号）

英文版：https://leetcode.com/problems/longest-valid-parentheses/

中文版：https://leetcode-cn.com/problems/longest-valid-parentheses/

参考：https://leetcode.com/problems/longest-valid-parentheses/solution/

改方法使用栈，先在栈底放入-1，然后放各个括号索引

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution(object):
    def longestValidParentheses(self, s):
        """
        :type s: str
        :rtype: int
        """
        stack = [-1]
        ans = 0
        for i in range(len(s)):
            if s[i] == "(":
                stack.append(i)
            else:
                stack.pop()
                if len(stack) == 0:
                    stack.append(i)
                else:
                    ans = max(ans, i - stack[-1])
        return ans

测试用例

1
2
3
4
5
s = Solution()
print(s.longestValidParentheses("(()"))  # 2
print(s.longestValidParentheses(")()())"))  # 4
print(s.longestValidParentheses("(()())"))  # 6
print(s.longestValidParentheses("()(()"))  # 2

Evaluate Reverse Polish Notatio（逆波兰表达式求值）

英文版：https://leetcode.com/problems/evaluate-reverse-polish-notation/

中文版：https://leetcode-cn.com/problems/evaluate-reverse-polish-notation/

题中指明逆波兰式总是有效的，因此无需判定有效，直接使用栈解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        stack = []
        for s in tokens:
            if s == "+":
                b = stack.pop()
                a = stack.pop()
                stack.append(a + b)
            elif s == "-":
                b = stack.pop()
                a = stack.pop()
                stack.append(a - b)
            elif s == "*":
                b = stack.pop()
                a = stack.pop()
                stack.append(a * b)
            elif s == "/":
                b = stack.pop()
                a = stack.pop()
                stack.append(int(a / b))  # 负数除法：6//-132 = -1，而非0。因此采用先除，后取整方法
            else:
                stack.append(int(s))  # 将字符转为int存入栈
            # print(stack)
        return stack[0]

python除法可参考：python – 整数除以负数

更简洁的写法(耗时更长)：

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        stack = []
        symbol = ["+", "-", "*", "/"]
        for s in tokens:
            if s in symbol:
                b = stack.pop()
                a = stack.pop()
                stack.append(str(int(eval(a + s + b))))
            else:
                stack.append(s)  # 栈中存字符
            # print(stack)
        return int(stack[0])  # 最后结果转为int

部分测试用例：

1
2
3
4
s = Solution()
print(s.evalRPN(["2", "1", "+", "3", "*"]))  # 9,((2 + 1) * 3) = 9
print(s.evalRPN(["4", "13", "5", "/", "+"]))  # 6,  (4 + (13 / 5)) = 6
print(s.evalRPN(["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"]))  # 22

队列

用数组实现一个顺序队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# coding:utf-8
class Queue:
    def __init__(self):
        self.items = []

    def isEmpty(self):
        return self.items == []

    def enqueue(self, item):
        self.items.insert(0,item)

    def dequeue(self):
        return self.items.pop()

    def size(self):
        return len(self.items)

用链表实现一个链式队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
# coding:utf-8
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None


class Queue:
    def __init__(self):
        self.front = self.rear = None

    def isEmpty(self):
        return self.front == None

    def EnQueue(self, item):
        temp = Node(item)

        if self.rear == None:
            self.front = self.rear = temp
            return
        self.rear.next = temp
        self.rear = temp

    def DeQueue(self):

        if self.isEmpty():
            return
        temp = self.front
        self.front = temp.next

        if (self.front == None):
            self.rear = None
        return str(temp.data)

实现一个循环队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Queue:
    def __init__(self):
        front = None
        rear = None


def enQueue(q, value):
    temp = Node()
    temp.data = value
    if (q.front == None):
        q.front = temp
    else:
        q.rear.link = temp

    q.rear = temp
    q.rear.link = q.front


def deQueue(q):
    if (q.front == None):
        print("Queue is empty")
        return -1

    value = None
    if (q.front == q.rear):
        value = q.front.data
        q.front = None
        q.rear = None
    else:
        temp = q.front
        value = temp.data
        q.front = q.front.link
        q.rear.link = q.front

    return value

对应的 LeetCode 练习题

Circular Deque（设计一个双端队列）

英文版：https://leetcode.com/problems/design-circular-deque/

中文版：https://leetcode-cn.com/problems/design-circular-deque/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
class MyCircularDeque(object):

    def __init__(self, k):
        """
        Initialize your data structure here. Set the size of the deque to be k.
        :type k: int
        """
        self.k = k
        self.queue = []

    def insertFront(self, value):
        """
        Adds an item at the front of Deque. Return true if the operation is successful.
        :type value: int
        :rtype: bool
        """
        if self.isFull():
            return False
        self.queue.insert(0, value)
        return True

    def insertLast(self, value):
        """
        Adds an item at the rear of Deque. Return true if the operation is successful.
        :type value: int
        :rtype: bool
        """
        if self.isFull():
            return False
        self.queue.append(value)
        return True

    def deleteFront(self):
        """
        Deletes an item from the front of Deque. Return true if the operation is successful.
        :rtype: bool
        """
        if self.isEmpty():
            return False
        self.queue.pop(0)
        return True

    def deleteLast(self):
        """
        Deletes an item from the rear of Deque. Return true if the operation is successful.
        :rtype: bool
        """
        if self.isEmpty():
            return False
        self.queue.pop()
        return True

    def getFront(self):
        """
        Get the front item from the deque.
        :rtype: int
        """
        if len(self.queue) > 0:
            return self.queue[0]  # 注意不是pop(0)
        return -1  # 根据测试用例预期返回-1， 不写return None

    def getRear(self):
        """
        Get the last item from the deque.
        :rtype: int
        """
        if len(self.queue) > 0:
            return self.queue[-1]  # 注意不是pop()
        return -1  # 根据测试用例预期返回-1， 不写return None

    def isEmpty(self):
        """
        Checks whether the circular deque is empty or not.
        :rtype: bool
        """
        if len(self.queue) == 0:
            return True
        return False

    def isFull(self):
        """
        Checks whether the circular deque is full or not.
        :rtype: bool
        """
        if len(self.queue) == self.k:
            return True
        return False

部分测试用例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
circularDeque = MyCircularDeque(3)  # 设置容量大小为3
print(circularDeque.insertLast(1))  # 返回 true
print(circularDeque.insertLast(2))  # 返回 true
print(circularDeque.insertFront(3))  # 返回 true
print(circularDeque.insertFront(4))  # 已经满了，返回 false
print(circularDeque.getRear())  # 返回 2
print(circularDeque.isFull())  # 返回 true
print(circularDeque.deleteLast())  # 返回 true
print(circularDeque.insertFront(4))  # 返回 true
print(circularDeque.getFront())  # 返回 4

print("=" * 30)
obj = MyCircularDeque(4)  # null
print(obj.insertFront(9))  # true
print(obj.deleteLast())  # true
print(obj.getRear())  # -1

"""
["MyCircularDeque","insertFront","deleteLast","getRear","getFront","getFront","deleteFront","insertFront","insertLast","insertFront","getFront","insertFront"]
[[4],[9],[],[],[],[],[],[6],[5],[9],[],[6]]

[null,true,true,-1,-1,-1,false,true,true,true,9,true]
"""

Sliding Window Maximum（滑动窗口最大值）

英文版：https://leetcode.com/problems/sliding-window-maximum/

中文版：https://leetcode-cn.com/problems/sliding-window-maximum/

链表

实现单链表、循环链表、双向链表，支持增删操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
# coding: utf-8

class Node(object):
    def __init__(self, data):
        self.data = data
        self.next = None


class LinkedList(object):
    def __init__(self):
        self.head = None

    def __len__(self):
        pre = self.head
        length = 0
        while pre:
            length += 1
            pre = pre.nex
        return length

    def is_empty(self):
        return False if len(self) > 0 else True

    def append(self, data):
        node = Node(data)
        if self.head is None:
            self.head = node
        else:
            pre = self.head
            while pre.next:
                pre = pre.next
            pre.next = node

    def insert(self, index, data):
        node = Node(data)
        if abs(index + 1) > len(self):
            return False
        index = index if index >= 0 else len(self) + index + 1
        if index == 0:
            node.next = self.head
            self.head = node
        else:
            pre = self.get(index - 1)
            if pre:
                nex = pre.nex
                pre.nex = node
                node.next = nex
            else:
                return False
        return node

    def delete(self, index):
        f = index if index > 0 else abs(index + 1)
        if len(self) <= f:
            return False
        pre = self.head
        index = index if index >= 0 else len(self) + index
        prep = None
        while index:
            prep = pre
            pre = pre.nex
            index -= 1
        if not prep:
            self.head = pre.nex
        else:
            prep.nex = pre.nex
        return pre.data

实现单链表反转

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# coding: utf-8

class Node(object):
    def __init__(self, data):
        self.data = data
        self.next = None


class LinkedList(object):
    def __init__(self):
        self.head = None
 
    def __reversed__(self):
        def reverse(pre_node, node):
            if pre_node is self.head:
                pre_node.nex = None
            if node:
                next_node = node.nex
                node.nex = pre_node
                return reverse(node, next_node)
            else:
                self.head = pre_node

        return reverse(self.head, self.head.nex)

实现两个有序的链表合并为一个有序链表

1
2
3
4
5
6
7
8
9
10
11
12
13
def Merge(self, pHead1, pHead2):
       if pHead1 == None:
           return pHead2
       elif pHead2 == None:
           return pHead1
       pMergedHead = None
       if pHead1.val < pHead2.val:
           pMergedHead = pHead1
           pMergedHead.next = self.Merge(pHead1.next, pHead2)
       else:
           pMergedHead = pHead2
           pMergedHead.next = self.Merge(pHead1, pHead2.next)
       return pMergedHead

实现求链表的中间结点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# coding: utf-8

class Node:
    def __init__(self,data,next):
        self.data = data
        self.next = next
n1 = Node('n1',None)
n2 = Node('n2',n1)
n3 = Node('n3',n2)
n4 = Node('n4',n3)
n5 = Node('n5',n4)

p1 = n5
p2 = n5
while p2.next is not None and p2.next.next is not None:
    p1 = p1.next
    p2 = p2.next.next
print(p1.data)

对应的 LeetCode 练习题

Linked List Cycle I（环形链表）

英文版：https://leetcode.com/problems/linked-list-cycle/

中文版：https://leetcode-cn.com/problems/linked-list-cycle/

Merge k Sorted Lists（合并 k 个排序链表）

英文版：https://leetcode.com/problems/merge-k-sorted-lists/

中文版：https://leetcode-cn.com/problems/merge-k-sorted-lists/