Algorithms 101: Applications of Deque

Applications of Deque (双端队列的应用):

1. Sliding Window Problems (滑动窗口问题):

In sliding window problems, deques are often used to efficiently find the maximum or minimum element within a window of elements as it slides across a list. The deque helps in maintaining a list of indices of elements in such a way that the front of the deque always contains the index of the maximum (or minimum) element for the current window.

from collections import deque

def maxSlidingWindow(nums, k):
    dq = deque()
    max_values = []

    for i in range(len(nums)):
        # Remove elements out of the current window
        if dq and dq[0] < i - k + 1:
            dq.popleft()

        # Remove elements from the deque that are less than the current element
        while dq and nums[dq[-1]] < nums[i]:
            dq.pop()

        dq.append(i)

        # The first element of the deque is the max in the current window
        if i >= k - 1:
            max_values.append(nums[dq[0]])

    return max_values

nums = [1,3,-1,-3,5,3,6,7]
k = 3
print(maxSlidingWindow(nums, k))  # Output: [3, 3, 5, 5, 6, 7]

Big O Analysis:

• Time Complexity: O(n) – Each element is pushed and popped from the deque at most once.
• Space Complexity: O(k) – The deque stores at most k elements.

2. Palindrome Checking (回文检查):

A deque can be used to check if a sequence of characters is a palindrome by comparing elements from both ends. We enqueue characters from the string into the deque, then dequeue one character from the front and one from the rear, comparing them until the deque is empty or a mismatch is found.

from collections import deque

def isPalindrome(s):
    dq = deque(s)

    while len(dq) > 1:
        if dq.popleft() != dq.pop():
            return False
    return True

s = "radar"
print(isPalindrome(s))  # Output: True

s = "hello"
print(isPalindrome(s))  # Output: False

Big O Analysis:

• Time Complexity: O(n) – Each comparison operation takes constant time, and there are n/2 such operations.
• Space Complexity: O(n) – The deque stores all characters of the string.

3. Expression Parsing (表达式解析):

In expression parsing, deques help evaluate expressions where operators and operands need to be processed from both ends. For example, in a postfix expression, we can use a deque to store intermediate results.

def evaluatePostfix(expression):
    dq = deque()

    for char in expression:
        if char.isdigit():
            dq.append(int(char))
        else:
            right = dq.pop()
            left = dq.pop()
            if char == '+':
                dq.append(left + right)
            elif char == '-':
                dq.append(left - right)
            elif char == '*':
                dq.append(left * right)
            elif char == '/':
                dq.append(left // right)

    return dq.pop()

expression = "231*+9-"
print(evaluatePostfix(expression))  # Output: -4

Big O Analysis:

• Time Complexity: O(n) – Each element in the expression is processed once.
• Space Complexity: O(n) – The deque stores operands for the expression.

4. Task Scheduling (任务调度):

Deques can be used to manage tasks in both FIFO (First-In, First-Out) and LIFO (Last-In, First-Out) order. For example, a task scheduler might dequeue tasks from the front for FIFO processing or from the rear for LIFO processing.

from collections import deque

class TaskScheduler:
    def __init__(self):
        self.tasks = deque()

    def addTask(self, task):
        self.tasks.append(task)

    def processTaskFIFO(self):
        return self.tasks.popleft() if self.tasks else "No tasks"

    def processTaskLIFO(self):
        return self.tasks.pop() if self.tasks else "No tasks"

scheduler = TaskScheduler()
scheduler.addTask("Task 1")
scheduler.addTask("Task 2")
scheduler.addTask("Task 3")

print(scheduler.processTaskFIFO())  # Output: Task 1
print(scheduler.processTaskLIFO())  # Output: Task 3
print(scheduler.processTaskFIFO())  # Output: Task 2

Big O Analysis:

• Time Complexity: O(1) – Each add, pop, and popleft operation is performed in constant time.
• Space Complexity: O(n) – The deque stores all the tasks.

Summary (总结):

Deques offer a powerful and flexible way to solve a variety of problems that require operations at both ends of a data structure. Their efficiency in terms of time complexity makes them suitable for real-time applications such as sliding window problems, palindrome checking, expression parsing, and task scheduling.

双端队列为解决需要在数据结构两端进行操作的各种问题提供了一种强大而灵活的方式。它们在时间复杂度方面的高效性使其适合实时应用，例如滑动窗口问题、回文检查、表达式解析和任务调度。