stack using queue

implement_stack_using_queue.py

from collections import deque


# push O(n)
# top, pop, O(1)
class Stack1:
    # initialize your data structure here.
    def __init__(self):
        self.q = deque()

    # @param x, an integer
    # @return nothing
    def push(self, x):
        n = len(self.q)
        self.q.append(x)
        for i in range(n):
            self.q.append(self.q.popleft())

    # @return nothing
    def pop(self):
        self.q.popleft()

    # @return an integer
    def top(self):
        return self.q[0]

    # @return an boolean
    def empty(self):
        return not self.q


# push O(1)
# top, pop O(n)
class Stack2:
    # initialize your data structure here.
    def __init__(self):
        self.q = deque()

    # @param x, an integer
    # @return nothing
    def push(self, x):
        self.q.append(x)

    # @return nothing
    def pop(self):
        n = len(self.q)
        for i in range(n-1):
            tmp = self.q.popleft()
            self.q.append(tmp)
        self.q.popleft()

    # @return an integer
    def top(self):
        n = len(self.q)
        for i in range(n):
            tmp = self.q.popleft()
            self.q.append(tmp)
        return tmp

    # @return an boolean
    def empty(self):
        return not self.q

topk.py

def partition(nums, left, right):
    smallerIdx = left
    for idx in xrange(left+1, right+1):
        if nums[idx] < nums[left]:
            smallerIdx += 1
            nums[idx], nums[smallerIdx] = nums[smallerIdx], nums[idx]
    nums[smallerIdx], nums[left] = nums[left], nums[smallerIdx]
    return smallerIdx


def topk_util(nums, left, right, k):
    idx = partition(nums, left, right)
    rank = idx-left+1
    if rank == k:
        return nums[idx]
    elif rank < k:
        return topk_util(nums, idx+1, right, k-rank)
    else:
        return topk_util(nums, left, idx-1, k)

def topk(nums, k):
    if len(nums) < k:
        return None
    return topk_util(nums, 0, len(nums)-1, k)

nums = [5, 3, 4, 2, 1]
print topk(nums, 3)