文章目录
  1. 表
  2. 栈
    1. 栈的Python实现
  3. 队列
    1. 队列的Python实现（链表）
    2. 队列的Python实现（数组）

表

表有数组和链表两种实现。表一般有插入、删除、查找、判空、打印等操作；此外，也可以增加前驱、后继等操作。一个数组或链表加上这些操作称为表。

栈

栈是限制插入与删除在一个位置上进行的表，此位置称为栈顶。栈一般有入栈、出栈、判空等基本操作。和表一样，栈也可以用数组或链表实现。

栈的Python实现

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 Stack():
    def __init__(self, n=0):
        if n==0:
            self._list=[]
        else:
            self._list=[0]*n
        self.len=0
    
    def push(self, val):
        if self.len>=len(self._list):
            self._list.append(val)
        else:
            self._list[self.len]=val
        self.len+=1
    
    def pop(self):
        if self.len==0:
            return None
        else:
            self.len-=1
            return self._list[self.len]
    
    def print_vals(self):
        buffer=''
        for x in self._list[:self.len]:
            buffer+='{} '.format(x)
        print(buffer)

if __name__=='__main__':
    test=[(1, 'a'), (1, 'b'), (1, 'c'), (1, 'a'), (1, 'b'), (1, 'c'), -1, -1, -1, -1, -1, -1, -1, -1]
    stack=Stack()
    for x in test:
        if isinstance(x, int):
            val=stack.pop()
        else:
            stack.push(x[1])
        stack.print_vals()

队列

队列是限制插入在一端、删除在另一端的表，插入一端称为队尾、删除一端称为队首。队列一般有出队、入队、判空等基本操作。和表一样，队列也可以用数组或链表实现。

队列的Python实现（链表）

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():
    def __init__(self, val):
        self.val=val
        self.next=None

class Queue():
    def __init__(self):
        self.head=None
        self.tail=None
    
    def join(self, val):
        if self.head is None:
            self.head=Node(val)
            self.tail=self.head
        else:
            self.tail.next=Node(val)
            self.tail=self.tail.next
    
    def remove(self):
        retval=None
        if self.head is not None:
            retval=self.head.val
            self.head=self.head.next
        return retval
    
    def print_vals(self):
        node=self.head
        buffer=''
        while node is not None:
            buffer+='{} '.format(node.val)
            node=node.next
        print(buffer)

if __name__=='__main__':
    test=[(1, 'a'), (1, 'b'), (1, 'c'), (1, 'a'), (1, 'b'), (1, 'c'), -1, -1, -1, -1, -1, -1, -1, -1]
    queue=Queue()
    for x in test:
        if isinstance(x, int):
            queue.remove()
        else:
            queue.join(x[1])
        queue.print_vals()

队列的Python实现（数组）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Queue():
    def __init__(self, n=0):
        self.low, self.high=0, 0
        if n==0:
            self._list=[]
        else:
            self._list=[0]*n
    
    def join(self, val):
        if self.high==len(self._list):
            self._list.append(val)
        else:
            self._list[self.high]=val
        self.high+=1
    
    def remove(self):
        retval=None
        if self.low<self.high:
            retval=self._list[self.low]
            self.low+=1
        if self.low==self.high:
            self.low, self.high=0, 0
        return retval