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