数据结构(二):栈

2019-04-12 09:30:34来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

:后进先出(LIFO)表。

特点:只允许在顶部进行存取操作的顺序表。

基本操作

  • push:入栈,即将元素压入栈顶
  • pop:出栈,即将栈顶元素删除
  • top:输出栈顶元素

应用场景

  • 平衡符号:编译器中用于检查符号是否成对出现,方法为做一个空栈,读取字符,如果字符是一个开放符号如“{”、“(”、“[”等,将其压入栈中。如果字符是一个封闭符号,如“}”、“)”、“]”,此时如果栈为空,说明有字符没有成对出现;否则将栈元素弹出,如果弹出的符号不是对应的开放符号,同样说明没有成对出现;如果字符读取完毕时栈不为空,也说明字符没有成对出现。
  • 函数调用:函数在调用的时候,需要存储所有的重要信息,如变量名、返回地址等,这些信息就是通过栈来存储,然后控制转移到新的函数,当函数返回时从栈中取出存储的信息,继续从转移前的位置往下执行。递归函数对栈的使用开销极大,而且很容易导致栈溢出,可以通过栈操作来模拟递归过程。

栈的链表实现:

 1 class Node(object):
 2     def __init__(self, value=None, next=None):
 3         self.value = value
 4         self.next = next
 5 
 6 
 7 class Stack(object):
 8     def __init__(self, maxsize=8):
 9         self._head = Node() # 表头,无实际意义
10         self._top = None
11         self.maxsize = maxsize
12         self.length = 0
13 
14     def pop(self):
15         if self.length > 0:
16             node = self._head.next
17             self._head.next = node.next
18             self.length -= 1
19             self._top = self._head.next
20         else:
21             raise Exception('Empty stack')
22 
23     def push(self, value):
24         if self.length >= self.maxsize:
25             raise Exception('Stack is full')
26         node = Node(value)
27         node.next = self._head.next
28         self._head.next = node
29         self.length += 1
30         self._top = self._head.next
31 
32     def top(self):
33         if self.length > 0:
34             return self._top.value
35         else:
36             raise Exception('Stack is empty')
37 
38     def __len__(self):
39         return self.length

栈的数组实现:

 1 from array import array
 2 
 3 class Stack(object):
 4     def __init__(self, maxsize=8):
 5         self._array = array('i', range(maxsize))
 6         self.maxsize = maxsize
 7         self.length = 0
 8         self.index = -1
 9         self._top = None
10 
11     def push(self, value):
12         if self.length >= self.maxsize:
13             raise Exception('Stack is full')
14         self.index += 1
15         self._array[self.index] = value
16         self.length += 1
17         self._top = value
18 
19     def pop(self):
20         if self.length <= 0:
21             raise Exception('Stack is empty')
22         self.index -= 1
23         self.length -= 1
24         if self.index >= 0:
25             self._top = self._array[self.index]
26         else:
27             self._top = None
28 
29     def top(self):
30         return self._top
31 
32     def __len__(self):
33         return self.length

 


原文链接:https://www.cnblogs.com/sheshouxin/p/10680634.html
如有疑问请与原作者联系

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:Numpy库的学习(二)

下一篇:一篇搞懂python文件读写操作(r/r+/rb/w/w+/wb/a/a+/ab)