forked from keon/algorithms
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathis_consecutive.py
More file actions
60 lines (51 loc) · 1.9 KB
/
is_consecutive.py
File metadata and controls
60 lines (51 loc) · 1.9 KB
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
59
60
"""
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