数据结构(二):栈

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

 

人已赞赏
随笔日记

图解简单C程序的运行时结构

2020-11-9 4:20:08

随笔日记

sqlmap Bool型&延时型 检测策略分析

2020-11-9 4:20:10

0 条回复 A文章作者 M管理员
    暂无讨论,说说你的看法吧
个人中心
购物车
优惠劵
今日签到
有新私信 私信列表
搜索