我想反转堆栈，但我不知道如何使用递归来反转此...我如何不使用递归来反转堆栈 [英] I want to reverse the stack but i dont know how to use recursion for reversing this... How can i reverse the stack without using Recursion

问题描述

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

str =我们打败了电晕

str= we defeated Corona

str反向=厌氧的ew

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) 

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

Why i Cant use this below code to reverse...

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

推荐答案

普通列表和普通功能

如果您只需要实现堆栈，我认为没有理由联系 collections.deque .我们可以轻松地基于简单列表 [] -

I see no reason to reach for collections.deque if you only need to implement a stack. We can easily build around a plain list, [] -

# 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 具有更面向对象的感觉，我们可以在普通函数周围添加一个接口-

If you want stack to have a more object-oriented feel, we can add an interface around the plain functions -

# 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 如下-

Now we can write main as follows -

# 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模块-

Go ahead and add other capabilities to the Stack module -

# stack.py (continued)

def reverse(t):
  t.reverse()

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

在面向对象的界面中包装新功能-

Wrap your new functions in the object-oriented interface -

# 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 是否正常-

Let's verify seek and reverse working -

# 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

---

相关阅读

在最近的问题与解答中，我展示了如何设计与上述 stack 类似的模块.如果您想了解随着程序的增长如何应用该技术，建议您查看该帖子:D

In a recent Q&A I showed how to design modules similar to stack above. If you want to see how this technique is applied as your program grows, I encourage you to check out that post :D

永久堆栈

作为一个有趣的练习，我们可以在不使用 deque ， list 或任何其他内置数据容器的情况下实现堆栈.相反，我们将使用普通的 None 和匿名函数.我分享了这个示例，因此您可以意识到，即使您使用的语言不包含特定功能，程序员也可以发挥他们的想象力.

As a fun exercise, we can implement a stack without using deque, a list, or any other built-in data container. Instead, we'll use plain None and anonymous functions. I share this example so you can realize that the programmer can build anything in their imagination, even if the language you are using doesn't include particular features -

# 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 修改基础堆栈，而是每个堆栈操作都创建_ new_堆栈.请注意，如果需要，我们如何卸载两次(或多次)-

Instead of modifying the underlying stack using .append, .pop, or .reverse, each stack operation creates _ new_ stack. Notice how we can unload the stack twice (or more), if we wanted -

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

这篇关于我想反转堆栈，但我不知道如何使用递归来反转此...我如何不使用递归来反转堆栈的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！