Python实现堆栈和队列

发表于 | 分类于

  栈作为一种数据结构，是一种只能在一端进行插入和删除操作。它按照先进后出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来）。

@堆栈|center|0

栈的应用场景：

  1. 内存管理中使用的堆栈；
  2. 基于栈实现的二叉树的遍历；

  3. 语言处理中，符号的平衡问题。

    在语言中，往往很多符号是成对出现的，比如<>,{},[],()等，如何判断符号是否漏了，一种实现方式就是：假设在读入一串字符串以后，如果遇到对称符号的左边部分，则将其压入栈中，当遇到对称符号的右边部分，则弹出栈中的一个对象，如果所有的符号都是平衡的，栈中此时应该就是为空，通过判断栈中是否为空，说明字符串是否是符号平衡的。

栈的设计

首先，需要定义一个实例属性top，三个实例方法：获取栈顶元素——peek(); 出栈——pop(); 入栈——push()；

实例属性：self.top 要先找到一个基准

实例方法：

  1. 入栈 push()
    一个指针，一个节点。指针永远指向当前栈顶。
    当入栈时，将当前指针的值付给入栈节点的next，指针指向入栈节点。

  2. 出栈 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
32
33
34
35
36
37
38
39
40
41
42
# 定义节点
class Node(object):
    def __init__(self, val):    # 定位的点的值和一个指向
        self.val = val          # 指向元素的值,原队列第二元素
        self.next = None        # 指向的指针


# 定义栈
class Stack(object):
    def __init__(self):
        self.top = None         # 初始化最开始的位置

    def peek(self):             # 获取栈顶的元素
        if self.top != None:    # 如果栈顶不为空
            return self.top.val  # 返回栈顶元素的值
        else:
            return None

    def push(self, n):          # 添加到栈中
        n = Node(n)             # 实例化节点
        n.next = self.top       # 顶端元素传值给一个指针
        self.top = n
        return n.val

    def pop(self):              # 出栈
        if self.top == None:
            return None
        else:
            tmp = self.top.val
            self.top = self.top.next  # 下移一位
            return tmp


if __name__ == "__main__":
    s = Stack()
    s.push(1)
    s.push(2)
    s.push(3)
    
    print(s.pop())
    print(s.pop())
    print(s.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
32
33
34
35
36
37
38
39
40
# 用列表实现堆栈
class Stack:
    def __init__(self, size):
        self.size = size
        self.list = []

    def push(self, item):
        if self.is_full():
            print('堆栈已满')
        else:
            self.list.append(item)

    def pop(self):
        if self.is_empty():
            print('堆栈已空')

        else:
            return self.list.pop()

    def is_full(self):
        if len(self.list) == self.size:
            return True
        return False

    def is_empty(self):
        if len(self.list) == 0:
            return True
        return False


print()
s = Stack(2)
print(s.is_empty())
s.push(1)
s.push(2)
print(s.list)
print(s.is_full())
print(s.pop())
print(s.pop())
print(s.is_empty())

队列的设计

队列是按照先进先出的原则储存数据，可实现enqueue,dequeue,is_empty,is_full四种方法。

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
class Queue:
    def __init__(self, size):
        self.size = size
        self.list = []

    def enqueue(self, item):
        if self.is_full():
            print('队列已满')
        else:
            self.list.append(item)

    def dequeue(self):
        if self.is_empty():
            print('队列已空')

        else:
            return self.list.pop(0)

    def is_full(self):
        if len(self.list) == self.size:
            return True
        return False

    def is_empty(self):
        if len(self.list) == 0:
            return True
        return False


s = Queue(2)
print(s.is_empty())
s.enqueue(1)
s.enqueue(2)
print(s.is_full())
print(s.dequeue())
print(s.dequeue())
print(s.is_empty())

用栈来实现队列的功能

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
class Stack:
    def __init__(self, size):
        self.size = size
        self.list = []

    def push(self, item):
        if self.is_full():
            print('堆栈已满')
        else:
            self.list.append(item)

    def pop(self):
        if self.is_empty():
            print('堆栈已空')

        else:
            return self.list.pop()

    def is_full(self):
        if len(self.list) == self.size:
            return True
        return False

    def is_empty(self):
        if len(self.list) == 0:
            return True
        return False

    def __len__(self):
        return len(self.list)


class Queue:

    def __init__(self, size):
        self.size = size
        self.in_stack = Stack(size)
        self.out_stack = Stack(size)

    def push(self, item):
        if len(self.in_stack) + len(self.out_stack) < self.size:
            self.in_stack.push(item)
        else:
            print('队列已满')

    def pop(self):

        if len(self.out_stack):
            return self.out_stack.pop()
        for i in range(len(self.in_stack)):
            self.out_stack.push(self.in_stack.pop())
        return self.out_stack.pop()


if __name__ == '__main__':
    q = Queue(3)
    q.push(1)
    q.push(2)
    q.push(3)
    print(q.pop())
    q.push(4)
    print(q.pop())
    print(q.pop())