python 如何用单向循环链表实现堆栈

Python015

python 如何用单向循环链表实现堆栈,第1张

Node没什么问题,就是变量定义的时候是一个下划线而不是两个

Stack这里有点问题,

(不知道你这里为啥需要做成一个循环的链表,不过不管了)

首先你得定义一个head和一个tail,这样的话才能把tail和head连接形成一个循环

初始化Stack的话把head和tail都设置成None表示这是个空的stack

push的话看你喜欢这么写了,比较喜欢的是把push进去的Node作为新的head,然后修改一下self._head为新Node,然后修改新Node的next为老的head,再连接一下Tail和Head便可,这样就省掉一些循环

pop的话就加一些判定好了,首先看Head是不是None,如果是就说明Stack是空的。如果发现Tail和Head都是同一个的话就说明Stack里就一项了,提取完Head之后就设置Stack为空吧。然后先提取Head,然后读取Head后面的那一个Node并且设置为新的Head,然后再连接一下Tail和Head便可

附上代码供参考.

class Node:

    def __init__(self, newData):

        self._data = newData

        self._next = None

    def getData(self):

        return self._data

    def getNext(self):

        return self._next

    def setData(self, newData):

        self._data = newData

    def setNext(self, newNode):

        self._next = newNode

class Stack:

    def __init__(self):

        self._head = None

        self._tail = None

    def push(self, data):

        print 'Push',data,'into stack'

        new = Node(data)

        cur = self._head

        end = self._tail

        if cur is None:

            self._head = new

            new.setNext(new)

            self._tail = new

        else:

            new.setNext(self._head)

            self._head = new

            self._tail.setNext(new)

    def pop(self):

        if self._head is not None:

            cur = self._head

            print 'pop',cur.getData(),'out of stack'

            if cur.getNext() is not cur:

                self._head = cur.getNext()

                self._tail.setNext(self._head)

            else:

                self._head = None

                self._tail = None

        else:

            print 'Stack is empty'

my = Stack()

for i in range(5):

    my.push(i)

for i in range(6):

    my.pop()

“python list[3::-1]”的意思是:从位置3反向截取list中的数组。

list参数分别是截取位置、截取方式。3代表从list第三个位置开始截取,-1代表反向截取。

在编程语言中,List是双向串行连接,用于管理线性列中的对象集合。 list的功能是在集合中的任何位置添加或删除元素都是快速的,但不支持随机访问。

list是类库提供的众多容器(container)之一,除此之外还有vector、set、map、…等等。List被实现为模板(即泛型),并且可以处理任何类型的变量,包括用户定义的数据类型。

扩展资料:

list是一个双向循环链表,每个元素都知道前一个元素和下一个元素。

在STL中,list(如vector)是常用容器,与vector不同,list不支持对元素的任意访问。 list中提供的成员函数类似于vector,但是list提供了对表的第一个元素push_front和pop_front的操作,这些操作在vector中不可用。

与vector不同,list迭代器不会失败。 与vector不同,vector保留了备份空间,当超过容量限制时,将重新分配所有内存,从而导致迭代器失败。 List没有备份空间的概念,请求元素进行空间的进出,因此其迭代器不会失败。

count = 10 # 总猴子数

i     = 0  # 开始的序号

skip  = 1  # 报数的间隔数

arr   = list(range(count)) # 创建一个列表

print(arr) # [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

while(count > 1):

    if i >= count: i = i % count

    print('删除:', arr[i], end = ' ')

    arr.pop(i)

    print('剩余:', arr)

    count = len(arr)

    i = i + skip

# 输出结果:

# [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

# 删除: 0 剩余: [1, 2, 3, 4, 5, 6, 7, 8, 9]

# 删除: 2 剩余: [1, 3, 4, 5, 6, 7, 8, 9]

# 删除: 4 剩余: [1, 3, 5, 6, 7, 8, 9]

# 删除: 6 剩余: [1, 3, 5, 7, 8, 9]

# 删除: 8 剩余: [1, 3, 5, 7, 9]

# 删除: 1 剩余: [3, 5, 7, 9]

# 删除: 5 剩余: [3, 7, 9]

# 删除: 9 剩余: [3, 7]

# 删除: 7 剩余: [3]