python用数组和链表实现栈
程序员文章站
2022-06-15 21:22:56
python用数组和链表实现栈阿里笔试题题目描述:实现一个枝的数据结构,使其具有以下方法 :压栈、弹栈、取栈顶元素、判断校是否为空以及获取战中元素个数。方法一 : 数组实现从上图中可以看出,可以把数组的首元素 当做栈底 ,同时记录栈中元素的个数size 设数组首地址为 arr,从上图可以看出,压校的操作其实是把待压校的元素放到数组 arr[size] 中,然后执行 size+操作;同理,弹枝操作其实是取数组 arr[size-1]元素,然后执行 size-操作。 根据这个原理可以非常容易实现拢,...
python用数组和链表实现栈
阿里笔试题
题目描述:
实现一个枝的数据结构,使其具有以下方法 :压栈、弹栈、取栈顶元素、判断校是否为空以及获取战中元素个数。
方法一 : 数组实现
从上图中可以看出,可以把数组的首元素 当做栈底 ,同时记录栈中元素的个数size 设数组首地址为 arr,从上图可以看出,压校的操作其实是把待压校的元素放到数组 arr[size] 中,然后执行 size+操作;同理,弹枝操作其实是取数组 arr[size-1]元素,然后执行 size-操作。 根据这个原理可以非常容易实现拢,示例代码如下:
class mystack:
def __init__(self):
self.items=[]
def isEmpty(self):
return len(self.items)==0
def size(self):
return len(self.items)
def top(self):
if not self.isEmpty():
return self.items[len(self.items)-1]
else:
return None
def pop(self):
if len(self.items)>0:
return self.items.pop()
else:
print('栈为空')
return None
def push(self,item):
self.items.append(item)
if __name__=='__main__':
s=mystack()
s.push(4)
print('栈顶元素为:'+str(s.top()))
print('栈大小为:'+str(s.size()))
s.pop()
print('弹栈成功')
s.pop()
栈顶元素为:4
栈大小为:1
弹栈成功
栈为空
方法二:链表实现
在创建链表的时候经常采用 一种从头结点插入新结点的方法,可以采用这种方法来实现 拢,最好使用带头结点的链表,这样可以保证对每个结点的操作都是相同的,实现思路如下 图所示。
在上图中,在进行压枝操作的时候,首先需要创建新的结点,把待压桔的元素放到新结 点的数据域中,然后只需要 (1)和(2)两步就实现了压枝操作(把新结点加到了链表首部)。 同理,在弹枝的时候,只需要进行( 3)的操作就可以删除链表的第一个元素,从而实现弹找 操作。实现代码如下 :
class LNode:
def __init__(self,x):
self.data=x
self.next=None
class MyStack:
def __init__(self):
self.data=None
self.next=None
def empty(self):
if self.next==None:
return True
else:
return False
def size(self):
size=0
p=self.next
while p!=None:
p=p.next
size+=1
return size
def push(self,e):
p=LNode
p.data=e
p.next=self.next
self.next=p
def pop(self):
tmp=self.next
if tmp!=None:
self.next=tmp.next
return tmp.data
print('栈已经为空')
return None
def top(self):
if self.next!=None:
return self.next.data
print('栈已为空')
return None
if __name__=='__main__':
stack=MyStack()
stack.push(1)
print('栈顶元素为:'+str(stack.top()))
print('栈的大小为:'+str(stack.size()))
stack.pop()
print('弹栈成功')
stack.pop()
栈顶元素为:1
栈的大小为:1
弹栈成功
栈已经为空
本文地址:https://blog.csdn.net/weixin_42813521/article/details/107668442