[Python数据结构] 使用List实现Stack

[Python数据结构] 使用List实现Stack

1. Stack

堆栈（Stack）又称为栈或堆叠，是计算机科学中一种特殊的串列形式的抽象数据类型（ADT），其特殊之处在于只能允许在阵列的一端进行加入数据和删除数据，并且执行顺序应按照后进先出（LIFO）的原则。

堆栈[维基百科]

2. Stack ADT

堆栈是一种抽象数据类型，其实例S需要支持两种方法：

　　1）S.push(e) : add element e to the top of stack S

　　2）S.pop( ) : remove and return the top element from the stack S

另外，为了方便使用，我们还定义了以下方法：

　　3）S.top() : return the top element from the stack S, but not remove it

　　4）S.is_empty() : Return True if the stack is empty

　　5）len(S) : Return the number of elements in the stack

3. Implementing a Stack using a List

1 class Empty(Exception):
2     """Error attempting to access an element from an empty container"""
3     pass
4  
5 class OverFlow(Exception):
6     """Error attempting to push an element to an full container"""
7     pass

 1 class ArrayStack():
 2     """LIFO Stack implementation using a Python list as underlying storage"""
 3     
 4     def __init__(self, n):
 5         """Create an empty stack."""
 6         self.data = []
 7         self.maxLen = n  # n : an integer that represent the max elements capacity of the stack
 8  
 9     def __len__(self):
10         """Return the number of elements in the stack"""
11         return len(self.data)
12     
13     def is_empty(self):
14         """Return True if the stack is empty"""
15         return len(self.data) == 0 
16     
17     def is_full(self):
18         """Return True if the stack is full"""
19         return len(self.data) == self.maxLen
20     
21     def push(self, e):
22         """Add element e to the top of the stack
23         
24          Raise Empty exception if the stack is full"""
25         if self.is_full():
26             raise OverFlow('Stack is full')            
27         return self.data.append(e)
28     
29     def top(self):
30         """Return the element at the top of the stack, but not move it.
31         
32         Raise Empty exception if the stack is empty"""
33         if self.is_empty():
34             raise Empty('Stack is empty')
35         return self.data[-1]
36     
37     def pop(self):
38         """Return the element at the top of the stack, meanwhile move it.
39         
40         Raise Empty exception if the stack is empty"""
41         if self.is_empty():
42             raise Empty('Stack is empty')
43         return self.data.pop()

4. 执行结果：

1 s = ArrayStack(10)
2 l = np.random.randint(0, 10, size=(10, ))
3 for i in l:
4     s.push(i)

1 s.data
2 [6, 8, 7, 4, 2, 3, 4, 1, 5, 8]

1 s.pop()
2 8

1 s.data
2 [6, 8, 7, 4, 2, 3, 4, 1, 5]

1 s.top()
2 5

1 s.data
2 [6, 8, 7, 4, 2, 3, 4, 1, 5]