使用列表结构模拟Python栈，但不使用列表方法

Question

你会怎么做来模拟一个栈的推入（push）和弹出（pop）功能，而不使用列表的方法呢？

到目前为止，我有这样的代码，但我不确定这样是否可行：

stack = []

def Push(stack, element):
    stack[len(stack)] = element

def Pop(stack):
    element = tos
    stack[len(stack) - 1] = None

    return element;

这样推入数据，动态地添加到列表中，是否能正常工作？而且列表的长度（len）会不会正确更新呢？

至于弹出数据，怎么在不使用任何列表函数的情况下，从栈中“删除”数据呢？

Answer 1

你可以提前分配一个列表：

class Stack:
    def __init__(self, max_items):
        self.data = [0] * max_items
        self.max_items = max_items
        self.top = -1

    def push(self, i):
        self.top += 1
        if self.top < self.max_items:
            self.data[self.top] = i
        else:
            self.top -= 1
            raise ValueError("stack is full")

    def pop(self):
        if self.top >= 0:
            i = self.data[self.top]
            self.top -= 1
            return i
        else:
            raise ValueError("stack is empty")

    def __len__(self):
        return self.top + 1

Answer 2

我想这个练习的目的是让我们了解栈这种< a href="http://en.wikipedia.org/wiki/Abstract_data_type" rel="nofollow">抽象数据类型。其实你可以完全不使用列表来实现栈。如果你坚持要用列表的话，我不太明白你所说的“不要使用列表方法”是什么意思。

栈（作为一种列表）是一种数据类型，有两个基本的构造方式：(a) 一个空栈，和 (b) 把一个元素放到栈上后的结果。你可以在Python中想出很多不同的实现方式。例如，None可以表示空栈，而(x, s)可以表示把x放到s栈顶后的结果。我建议你先自己尝试做一些这样的事情，再去寻求更多的帮助。

Answer 3

你可以使用类似这样的代码 (注意：这只是一个简单的实现 - 它没有对传入的参数进行检查)：

class Stack(object):
    def __init__(self):
        self._stack = [] # Allocate an empty list

    def push(self, ele):
        self._stack += [ele] # Use list concatenation to emulate the `push` operation

    def pop(self):
        last = self._stack[-1:] # Return the last element of the list (also works for empty lists)
        self._stack = self.stack[0:-1] # Copy the elements from the beginning of the list to the last element of the list
        return last # return the last element

    # All stacks should have the `size` function to determine how many elements are
    # in the stack:
    def size(self):
        return len(self._stack)

    # Occasionally you'll want to see the contents of the stack, so we have to
    # implement the `__str__` magic method:
    def __str__(self):
        return '[%s]' % ','.join(map(str, self._stack))

注意：这个方法没有使用任何的 list 方法，比如 append 和 pop。

示例：

s = Stack()

# fill the stack with values:
for i in xrange(10):
    s.push(i+1)

print s # Outputs: [1,2,3,4,5,6,7,8,9,10]

s.pop()
s.pop()

print s # Outputs: [1,2,3,4,5,6,7,8]