数据结构-栈&队列_编写shell程序,编写一个sstack函数堆栈显示数据列,编写一个squeue函数,队列显示数

栈

后进者先出，先进者后出，这就是典型的“栈”结构。

栈的操作

• Stack() 创建一个新的空栈
• push(item) 添加一个新的元素item到栈顶
• pop() 弹出栈顶元素
• peek() 返回栈顶元素
• is_empty() 判断栈是否为空
• size() 返回栈的元素个数

class stack(object):
    def __init__(self):
        self.item = []
    
    def is_empty(self):
        '''判断栈是否为空'''
        return self.item == []

    def push(self, item):
        '''入栈'''
        self.item.append(item)

    def travel(self):
        '''遍历栈元素并打印'''
        print(self.item)
    
    def pop(self):
        '''出栈'''
        return self.item.pop()

    def peek(self):
        '''返回栈顶元素'''
        if self.is_empty():
            return None
        else:
            return self.item[-1]
    
    def size(self):
        '''打印栈元素的个数'''
        print(len(self.item))


s = stack()
print(s.is_empty())
s.push(0)
s.push(2)
s.push(5)
s.push(1)
s.pop()
s.travel()
print(s.peek())
s.size()

# True
# [0, 2, 5]
# 5
# 3
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

栈的应用

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Jk7StrTo-1574007113175)(02500A0353B34FEDAF6680D5AC40C2B8)]

浏览器的前进、后退功能，我想你肯定很熟悉吧？

当你依次访问完一串页面 a-b-c 之后，点击浏览器的后退按钮，就可以查看之前浏览过的页面 b 和 a。当你后退到页面 a，点击前进按钮，就可以重新查看页面 b 和 c。但是，如果你后退到页面 b 后，点击了新的页面 d，那就无法再通过前进、后退功能查看页面 c 了。

队列

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ZMreDaYd-1574007113176)(76320119DF1B47DAAAADFBDD1F12ED0D)]
作为一种非常基础的数据结构，队列的应用也非常广泛，特别是一些具有某些额外特性的队列，比如循环队列、阻塞队列、并发队列。它们在很多偏底层系统、框架、中间件的开发中，起着关键性的作用。

队列的实现

• Queue() 创建一个空的队列
• enqueue(item) 往队列中添加一个item元素
• dequeue() 从队列头部删除一个元素
• is_empty() 判断一个队列是否为空
• size() 返回队列的大小

class MyQueue(object):
    def __init__(self):
        self.item = []

    def EnQueun(self, item):
        return self.item.append(item)

    def DeQueue(self):
        return self.item.pop(0)

    def is_empty(self):
        return self.item == []

    def size(self):
        print(len(self.item))

    def travel(self):
        for i in self.item:
            print(i, end=' ')

if __name__ == '__main__':

    q = MyQueue()
    print(q.is_empty())
    q.EnQueun(1)
    q.EnQueun(5)
    q.EnQueun(2)
    q.EnQueun(0)
    q.DeQueue()
    q.travel()
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

双端队列

双端队列（dequeue,double-ended queue),是一种具有队列和栈的性质的数据结构

双端队列中的元素可以从两端弹出，其限定入队和出队的操作在两端进行。双端队里可以在任意一端入队和出队。

操作
Deque() 创建一个空的双端队列

• add_front(item) 从队头加入一个item元素
• add_rear(item) 从队尾加入一个item元素
• remove_front() 从队头删除一个item元素
• remove_rear() 从队尾删除一个item元素
• is_empty() 判断双端队列是否为空
• size() 返回队列的大小

class QueueOpertion(object):
    def __init__(self):
        self.item = []

    def EnQueue(self, item):
        return self.item.append(item)

    def DeQueue(self):
        return self.item.pop(0)

    def is_empty(self):
        return self.item == []

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

    def travel(self):
        for i in self.item:
            print(i, end=' ')

class DoubleQ(QueueOpertion):
    def add_front(self, item):
        self.item.insert(0, item)

    def remove_rear(self):
        self.item.pop()


if __name__ == '__main__':
    d = DoubleQ()
    print(d.is_empty())

    d.EnQueue(6)
    d.EnQueue(9)
    d.EnQueue(7)
    d.add_front("r")
    d.add_front("y")
    d.add_front("h")
    d.DeQueue()
    d.remove_rear()

    print(d.size())
    d.travel()
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

阻塞队列

阻塞队列实在队列的基础上加了阻塞操作。如果队列为空或是不满的情况下，从头部提取数据会被阻塞，因为此时没有数据可取，直到队列满了，才能返回。相同，当队列满的时候，入队时会被阻塞，直到队列中有空闲的位置时才能入队，然后返回。

阻塞有两种处理方式：

1. 排队请求：当队列满的时候，无法入队，等待有空闲位置的时候执行
2. 拒绝请求：当队列满的时候，无法入队，直接拒绝，直接中断。