FilesExpand file tree

 master

/

stutter.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

46 lines (38 loc) · 1.29 KB

 master

/

stutter.py

Copy path

Top

File metadata and controls

• Code
• Blame

46 lines (38 loc) · 1.29 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

"""

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)

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)

stack.append(val)

return stack