algorithms/algorithms/stack/is_consecutive.py at master · lualgorithm/algorithms · GitHub

History

58 lines (51 loc) · 1.92 KB

Raw

"""

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

algorithms/algorithms/stack/is_consecutive.py at master · lualgorithm/algorithms · GitHub

Uh oh!

Expand file tree

Breadcrumbs

is_consecutive.py

Latest commit

History

Breadcrumbs

is_consecutive.py

File metadata and controls