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

python用数组和链表实现栈

程序员文章站 2022-06-15 21:22:56
python用数组和链表实现栈阿里笔试题题目描述:实现一个枝的数据结构,使其具有以下方法 :压栈、弹栈、取栈顶元素、判断校是否为空以及获取战中元素个数。方法一 : 数组实现从上图中可以看出,可以把数组的首元素 当做栈底 ,同时记录栈中元素的个数size 设数组首地址为 arr,从上图可以看出,压校的操作其实是把待压校的元素放到数组 arr[size] 中,然后执行 size+操作;同理,弹枝操作其实是取数组 arr[size-1]元素,然后执行 size-操作。 根据这个原理可以非常容易实现拢,...

python用数组和链表实现栈

阿里笔试题
题目描述:
实现一个枝的数据结构,使其具有以下方法 :压栈、弹栈、取栈顶元素、判断校是否为空以及获取战中元素个数。

方法一 : 数组实现

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
弹栈成功
栈为空

方法二:链表实现

在创建链表的时候经常采用 一种从头结点插入新结点的方法,可以采用这种方法来实现 拢,最好使用带头结点的链表,这样可以保证对每个结点的操作都是相同的,实现思路如下 图所示。
python用数组和链表实现栈
在上图中,在进行压枝操作的时候,首先需要创建新的结点,把待压桔的元素放到新结 点的数据域中,然后只需要 (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

相关标签: leetcode