algorithms/algorithms/stack/stutter.py at master · upzone/algorithms · GitHub

44 lines (38 loc) · 1.29 KB

"""

Given a stack, stutter takes a stack as a parameter and replaces every value

in the stack with two occurrences of that value.

For example, suppose the stack stores these values:

bottom [3, 7, 1, 14, 9] top

Then the stack should store these values after the method terminates:

bottom [3, 3, 7, 7, 1, 1, 14, 14, 9, 9] top

Note: There are 2 solutions:

first_stutter: it uses a single stack as auxiliary storage

second_stutter: it uses a single queue as auxiliary storage

"""

import collections

def first_stutter(stack):

storage_stack = []

for i in range(len(stack)):

storage_stack.append(stack.pop())

for i in range(len(storage_stack)):

val = storage_stack.pop()

stack.append(val)

return stack

def second_stutter(stack):

q = collections.deque()

# Put all values into queue from stack

for i in range(len(stack)):

q.append(stack.pop())

# Put values back into stack from queue

for i in range(len(q)):

stack.append(q.pop())

# Now, stack is reverse, put all values into queue from stack

for i in range(len(stack)):

q.append(stack.pop())

# Put 2 times value into stack from queue

for i in range(len(q)):

val = q.pop()

stack.append(val)

return stack

Expand file tree