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
str[::-1]which provides your desired output. – Dillydally