欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

数据结构(二):栈

程序员文章站 2022-07-06 23:16:28
栈:后进先出(LIFO)表。 特点:只允许在顶部进行存取操作的顺序表。 基本操作: push:入栈,即将元素压入栈顶 pop:出栈,即将栈顶元素删除 top:输出栈顶元素 应用场景: 平衡符号:编译器中用于检查符号是否成对出现,方法为做一个空栈,读取字符,如果字符是一个开放符号如“{”、“(”、“[ ......

:后进先出(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