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

问题描述

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

<块引用>

str= 我们打败了 Corona

<块引用>

reversed str = anoroC detaefed ew

从集合导入双端队列类堆栈:def __init__(self):self.container = deque()def rev(自我):nstk=双端队列()对于我在 self.container(len(self.container),0,-1):nstk.append(i)返回 nstk定义推送(自我，价值):self.container.append(val)def 窥视(自我):返回 self.containerst = 堆栈()lst= list('我们打败了 Corona')st.push(lst)打印(st.peek())revStack=st.rev()打印(revStack)

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

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

解决方案

简单的列表和普通函数

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

# stack.py默认空():返回 []定义推(t，x):t.append(x)定义弹出(t):返回 t.pop()默认负载(t，可迭代):对于可迭代的 x:推(t，x)默认卸载(t):而 t:产量 pop(t)

使用堆栈很直观-

# main.py导入堆栈输入=我们还没有打败电晕"；s = stack.empty()stack.load(s, 输入)输出 = "".join(stack.unload(s))打印(输出)

anoroc detaefed ton evah ew

---

让它更像 python

如果你想让 stack 有更多面向对象的感觉，我们可以在普通函数周围添加一个接口 -

# stack.py(续)类堆栈:def empty(): 返回栈(empty())def __init__(self, t): self.t = tdef push(self, v): return push(self.t, v)def pop(self): 返回 pop(self.t)def load(self, iterable): return load(self.t, iterable)def unload(self): 返回 unload(self.t)

现在我们可以将main写成如下-

# main.py从堆栈导入堆栈输入=我们还没有打败电晕"；s = stack.empty()s.load(输入)输出 = "".join(s.unload())打印(输出)

anoroc detaefed ton evah ew

---

扩展堆栈模块

继续往 Stack 模块添加其他功能 -

# stack.py(续)定义反向(t):t.reverse()定义窥视(t):如果不是 t:返回无别的:返回 t[-1]

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

# stack.py(续)类堆栈:默认空():...def __init__(): ...定义推():...定义弹出():...默认加载():...默认卸载():...def reverse(self): return reverse(self.t) # <-def peek(self): return peek(self.t) # <-

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

# main.py从堆栈导入堆栈输入=我们还没有打败电晕"；s = stack.empty()s.load(输入)打印(s.peek())s.pop()打印(s.peek())s.reverse()打印(s.peek())

anw

---

相关阅读

在最近的问答中，我展示了如何设计类似于上述stack的模块.如果您想了解随着程序的发展如何应用此技术，我鼓励您查看该帖子:D

---

持久堆栈

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

# stack.py空=无定义推(t，v):返回 lambda k: k(t, v)定义弹出(t):如果不是 t:raise RuntimeError("不能弹出空栈")别的:返回 t(lambda next, v: (next, v))默认负载(t，可迭代):对于可迭代的 v:t = 推(t, v)返回默认卸载(t):而 t:(下一个，v) = pop(t)产量 vt = 下一个定义反向(t):返回加载(空，卸载(t))定义窥视(t):如果不是 t:返回无别的:(_, v) = 流行(t)返回 v类堆栈:def empty(): 返回栈(空)def __init__(self, t): self.t = tdef push(self, v): return push(self.t, v)定义流行(自我):(下一个，v) = pop(self.t)返回(堆栈(下一个)，v)def load(self, iterable): 返回栈(load(self.t, iterable))def unload(self): 返回 unload(self.t)def reverse(self): 返回栈(reverse(self.t))def peek(self): 返回 peek(self.t)

每个堆栈操作都会创建一个 new，而不是使用 .append、.pop 或 .reverse 来修改底层堆栈 堆栈.请注意，如果我们愿意，我们可以如何unload 两次(或更多)堆栈 -

从栈导入栈输入=我们还没有打败电晕"；s = stack.empty().load(输入)print("".join(s.unload()))print("".join(s.reverse().unload()))print("".join(s.unload()))

anoroc detaefed ton evah ew我们还没有打败电晕anoroc detaefed ton evah ew

I want to reverse a string by using Stack Data Structure without using recursion

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) 

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

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

解决方案

plain list and ordinary functions

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)

Using the stack is intuitive -

# 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

---

make it feel more like python

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)

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

---

expand the stack module

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)        # <-

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

---

related reading

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

---

persistent stack

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)

Instead of modifying the underlying stack using .append, .pop, or .reverse, each stack operation creates a 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