FilesExpand file tree

 master

/

is_consecutive.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

58 lines (51 loc) · 1.92 KB

 master

/

is_consecutive.py

Copy path

Top

File metadata and controls

• Code
• Blame

58 lines (51 loc) · 1.92 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

47

48

49

50

51

52

53

54

55

56

57

58

"""

Given a stack, a function is_consecutive takes a stack as a parameter and that

returns whether or not the stack contains a sequence of consecutive integers

starting from the bottom of the stack (returning true if it does, returning

false if it does not).

For example:

bottom [3, 4, 5, 6, 7] top

Then the call of is_consecutive(s) should return true.

bottom [3, 4, 6, 7] top

Then the call of is_consecutive(s) should return false.

bottom [3, 2, 1] top

The function should return false due to reverse order.

Note: There are 2 solutions:

first_is_consecutive: it uses a single stack as auxiliary storage

second_is_consecutive: it uses a single queue as auxiliary storage

"""

import collections

def first_is_consecutive(stack):

storage_stack = []

for i in range(len(stack)):

first_value = stack.pop()

if len(stack) == 0: # Case odd number of values in stack

return True

second_value = stack.pop()

if first_value - second_value != 1: # Not consecutive

return False

stack.append(second_value) # Backup second value

storage_stack.append(first_value)

# Back up stack from storage stack

for i in range(len(storage_stack)):

stack.append(storage_stack.pop())

return True

def second_is_consecutive(stack):

q = collections.deque()

for i in range(len(stack)):

first_value = stack.pop()

if len(stack) == 0: # Case odd number of values in stack

return True

second_value = stack.pop()

if first_value - second_value != 1: # Not consecutive

return False

stack.append(second_value) # Backup second value

q.append(first_value)

# Back up stack from queue

for i in range(len(q)):

stack.append(q.pop())

for i in range(len(stack)):

q.append(stack.pop())

for i in range(len(q)):

stack.append(q.pop())

return True