我想反转堆栈，但我不知道如何使用递归来反转。。。如何在不使用递归的情况下反转堆栈

Question

我想通过使用堆栈数据结构而不使用递归来反转字符串

str= we defeated Corona

reversed str = anoroC detaefed ew

from collections import deque

class Stack:
    def __init__(self):
        self.container = deque()
    def rev(self):
        nstk= deque()
        for i in self.container(len(self.container),0,-1):
            nstk.append(i)
        return nstk
    def push(self,val):
        self.container.append(val)
    def peek(self):
        return self.container
        
st = Stack()
lst= list('we defeated Corona')
st.push(lst)
print(st.peek())
revStack= st.rev()
print(revStack) 

为什么我不能使用下面的代码来反转

def rev(self):
    self.container.reverse()

Answer 1

普通列表和普通函数

如果您只需要实现一个堆栈，我认为没有理由使用collections.deque。我们可以很容易地构建一个简单的列表，[]-

# stack.py

def empty():
  return []

def push(t, x):
  t.append(x)

def pop(t):
  return t.pop()

def load(t, iterable):
  for x in iterable:
    push(t, x)

def unload(t):
  while t:
    yield pop(t)

使用堆栈很直观-

# main.py

import stack

input = "we have not defeated corona"

s = stack.empty()
stack.load(s, input)

output = "".join(stack.unload(s))

print(output)

anoroc detaefed ton evah ew

---

让它感觉更像python

如果您希望stack具有更面向对象的感觉，我们可以在普通函数周围添加一个接口-

# stack.py (continued)

class stack:
  def empty(): return stack(empty())
  def __init__(self, t): self.t = t
  def push(self, v): return push(self.t, v)
  def pop(self): return pop(self.t)
  def load(self, iterable): return load(self.t, iterable)
  def unload(self): return unload(self.t)

现在我们可以这样写main

# main.py

from stack import stack

input = "we have not defeated corona"

s = stack.empty()
s.load(input)
output = "".join(s.unload())

print(output)

anoroc detaefed ton evah ew

---

展开堆栈模块

继续向堆栈模块添加其他功能-

# stack.py (continued)

def reverse(t):
  t.reverse()

def peek(t):
  if not t:
    return None
  else:
    return t[-1]

在面向对象的界面中包装新函数-

# stack.py (continued)

class stack:
  def empty(): ...
  def __init__(): ...
  def push(): ...
  def pop(): ...
  def load(): ...
  def unload(): ...
  def reverse(self): return reverse(self.t)  # <-
  def peek(self): return peek(self.t)        # <-

让我们验证一下seek和reverse是否正常工作-

# main.py

from stack import stack

input = "we have not defeated corona"

s = stack.empty()
s.load(input)

print(s.peek())
s.pop()
print(s.peek())
s.reverse()
print(s.peek())

a
n
w

---

相关阅读

在recent Q&A中，我展示了如何设计类似于上面stack的模块。如果您想了解随着程序的发展如何应用此技术，我鼓励您查看post:D

---

持久堆栈

作为一个有趣的练习，我们可以在不使用deque、一个list或任何其他内置数据容器的情况下实现堆栈。相反，我们将使用普通的None和匿名函数。我分享这个例子是为了让你意识到程序员可以在他们的想象中构建任何东西，即使你使用的语言不包含特定的功能-

# stack.py

empty = None

def push(t, v):
  return lambda k: k(t, v)

def pop(t):
  if not t:
    raise RuntimeError("cannot pop empty stack")
  else:
    return t(lambda next, v: (next, v))

def load(t, iterable):
  for v in iterable:
    t = push(t, v)
  return t

def unload(t):
  while t:
    (next, v) = pop(t)
    yield v
    t = next

def reverse(t):
  return load(empty, unload(t))

def peek(t):
  if not t:
    return None
  else:
    (_, v) = pop(t)
    return v

class stack:
  def empty(): return stack(empty)
  def __init__(self, t): self.t = t
  def push(self, v): return push(self.t, v)
  def pop(self):
    (next, v) = pop(self.t)
    return (stack(next), v)
  def load(self, iterable): return stack(load(self.t, iterable))
  def unload(self): return unload(self.t)
  def reverse(self): return stack(reverse(self.t))
  def peek(self): return peek(self.t)

每个堆栈操作都创建一个新的堆栈，而不是使用.append、.pop或.reverse修改底层堆栈。请注意，如果需要，我们可以unload两次（或更多次）调用堆栈-

from stack import stack

input = "we have not defeated corona"

s = stack.empty().load(input)

print("".join(s.unload()))
print("".join(s.reverse().unload()))
print("".join(s.unload()))

anoroc detaefed ton evah ew
we have not defeated corona
anoroc detaefed ton evah ew