栈
栈是只能通过访问它的一端来实现数据存储和检索的一种线性数据结构。换句话说,栈的修改是按先进后出的原则进行的。因此,栈又称为先进后出(FILO)的线性表。在栈中进行插入和删除操作的一端称为栈顶(top),相应地,另一端称为栈底(bottom)。不含数据元素的栈称为空栈。
- 初始化栈InitStack(S):创建一个空栈S。
- 判断空栈StackEmpty(S):当栈为空栈时返回“真”,否则返回“假”。
- 入栈Push(S,X)将元素x加入栈顶,并更新栈顶指针。
- 出栈Pop(S):将栈顶的元素从栈中删除,并且更新栈顶指针。
- 读栈顶元素Top(S):返回栈顶元素的值,但不修改栈顶的指针。
(1)栈的顺序存储。栈的顺序存储是指用一组地址连续的存储单元依次存储自栈顶到栈底的数据元素,同时附设指针top指示栈顶元素的位置。采用顺序存储结构的栈也称为顺序栈。在顺序存储方式下,需要预先定义或申请栈的存储空间,也就是说栈空间的容量是有限的。因此在顺序栈中,当一个元素入栈时,需要判断是否栈满(即栈空间中没有空闲单元),若栈满,则元素入栈会发生上溢现象。
(2)栈的链式存储。为了克服顺序存储的栈可以存在上溢的不足,可以用链表存储栈中的元素。用链表作为存储结构的栈也称为链栈。由于栈中元素的插入和删除仅在栈顶一端进行,因此不必另外设置头指针,链表的头指针就是栈顶指针。
import random
class node:
def __init__(self, pointer=None, data=None):
self.next = pointer
self.data = data
# 链栈
class stack:
def __init__(self):
self.head = node()
self.tail = self.head
self.length = 0
def stackEmpty(self):
if self.head == self.tail:
return True
return False
def push(self, data):
new_node = node(data=data)
self.tail.next = new_node
self.tail = new_node
self.length += 1
def pop(self):
tmp_pointer = self.head
for i in range(self.length - 1):
tmp_pointer = tmp_pointer.next
data = self.tail.data
self.tail = tmp_pointer
self.tail.next = None
self.length -= 1
return data
def top(self):
return self.tail.data
if __name__ == '__main__':
s = stack()
a = [random.randint(1, 400) for i in range(20)]
for i in range(len(a)):
print(a[i], end=' ')
s.push(a[i])
print()
print(s.stackEmpty())
print(s.length)
print(s.tail.data)
print(s.top())
for i in range(len(a)):
print(s.pop(), end=' ')
print()
print(s.stackEmpty())
Comments | NOTHING