Queue | Stack about leetcode

[tech-cow]

Queue

Data Structure实现

以下代码原地址

"""
Queue Abstract Data Type (ADT)
* Queue() creates a new queue that is empty.
  It needs no parameters and returns an empty queue.
* enqueue(item) adds a new item to the rear of the queue.
  It needs the item and returns nothing.
* dequeue() removes the front item from the queue.
  It needs no parameters and returns the item. The queue is modified.
* isEmpty() tests to see whether the queue is empty.
  It needs no parameters and returns a boolean value.
* size() returns the number of items in the queue.
  It needs no parameters and returns an integer.
* peek() returns the front element of the queue.
"""
from abc import ABCMeta, abstractmethod
class AbstractQueue(metaclass=ABCMeta):

    def __init__(self):
        self._size = 0

    def __len__(self):
        return self._size

    def is_empty(self):
        return self._size == 0

    @abstractmethod
    def enqueue(self, value):
        pass

    @abstractmethod
    def dequeue(self):
        pass

    @abstractmethod
    def peek(self):
        pass

    @abstractmethod
    def __iter__(self):
        pass


class ArrayQueue(AbstractQueue):

    def __init__(self, capacity=10):
        """
        Initialize python List with capacity of 10 or user given input.
        Python List type is a dynamic array, so we have to restrict its
        dynamic nature to make it work like a static array.
        """
        super().__init__()
        self._array = [None] * capacity
        self._front = 0
        self._rear = 0

    def __iter__(self):
        probe = self._front
        while True:
            if probe == self._rear:
                return
            yield self._array[probe]
            probe += 1

    def enqueue(self, value):
        if self._rear == len(self._array):
            self._expand()
        self._array[self._rear] = value
        self._rear += 1
        self._size += 1

    def dequeue(self):
        if self.is_empty():
            raise IndexError("Queue is empty")
        value = self._array[self._front]
        self._array[self._front] = None
        self._front += 1
        self._size -= 1
        return value

    def peek(self):
        """returns the front element of queue."""
        if self.is_empty():
            raise IndexError("Queue is empty")
        return self._array[self._front]

    def _expand(self):
        """expands size of the array.
         Time Complexity: O(n)
        """
        self._array += [None] * len(self._array)


class QueueNode:
    def __init__(self, value):
        self.value = value
        self.next = None

class LinkedListQueue(AbstractQueue):

    def __init__(self):
        super().__init__()
        self._front = None
        self._rear = None

    def __iter__(self):
        probe = self._front
        while True:
            if probe is None:
                return
            yield probe.value
            probe = probe.next

    def enqueue(self, value):
        node = QueueNode(value)
        if self._front is None:
            self._front = node
            self._rear = node
        else:
            self._rear.next = node
            self._rear = node
        self._size += 1

    def dequeue(self):
        if self.is_empty():
            raise IndexError("Queue is empty")
        value = self._front.value
        if self._front is self._rear:
            self._front = None
            self._rear = None
        else:
            self._front = self._front.next
        self._size -= 1
        return value

    def peek(self):
        """returns the front element of queue."""
        if self.is_empty():
            raise IndexError("Queue is empty")
        return self._front.value

Leetcode

232. Implement Queue using Stacks

时间复杂度:

Push() : O(1)
Pop(): O(n) | Amortized O(1)

第一次要执行pop()运算的时候，我们将stack1的值反方向的加入到stack2里面去，我们把这个行为抽象到一个fill_stack方程。

然后之后只要stack2不为空，我们就直接stack2里面pop()， 为空的话，我们再重复执行fill_stack这个过程

class MyQueue:
    def __init__(self):
        self.stack1 = []
        self.stack2 = []

    def push(self, x):
        self.stack1.append(x)

    def pop(self):
        self.fill_stack()
        return self.stack2.pop()

    def peek(self):
        self.fill_stack()
        return self.stack2[-1]
        
    def empty(self):
        return not self.stack2 and not self.stack1
    
    def fill_stack(self):
        if not self.stack2 and self.stack1:
            while self.stack1:
                self.stack2.append(self.stack1.pop())

[tech-cow]

Stack

Data Structure实现

以下代码原地址

"""
Stack Abstract Data Type (ADT)
Stack() creates a new stack that is empty.
   It needs no parameters and returns an empty stack.
push(item) adds a new item to the top of the stack.
   It needs the item and returns nothing.
pop() removes the top item from the stack.
   It needs no parameters and returns the item. The stack is modified.
peek() returns the top item from the stack but does not remove it.
   It needs no parameters. The stack is not modified.
isEmpty() tests to see whether the stack is empty.
   It needs no parameters and returns a boolean value.
size() returns the number of items on the stack.
   It needs no parameters and returns an integer.
"""
from abc import ABCMeta, abstractmethod
class AbstractStack(metaclass=ABCMeta):
    """Abstract Class for Stacks."""
    def __init__(self):
        self._top = -1

    def __len__(self):
        return self._top + 1

    def __str__(self):
        result = " ".join(map(str, self))
        return 'Top-> ' + result

    def is_empty(self):
        return self._top == -1

    @abstractmethod
    def __iter__(self):
        pass

    @abstractmethod
    def push(self, value):
        pass

    @abstractmethod
    def pop(self):
        pass

    @abstractmethod
    def peek(self):
        pass


class ArrayStack(AbstractStack):
    def __init__(self, size=10):
        """
        Initialize python List with size of 10 or user given input.
        Python List type is a dynamic array, so we have to restrict its
        dynamic nature to make it work like a static array.
        """
        super().__init__()
        self._array = [None] * size

    def __iter__(self):
        probe = self._top
        while True:
            if probe == -1:
                return
            yield self._array[probe]
            probe -= 1

    def push(self, value):
        self._top += 1
        if self._top == len(self._array):
            self._expand()
        self._array[self._top] = value

    def pop(self):
        if self.is_empty():
            raise IndexError("stack is empty")
        value = self._array[self._top]
        self._top -= 1
        return value

    def peek(self):
        """returns the current top element of the stack."""
        if self.is_empty():
            raise IndexError("stack is empty")
        return self._array[self._top]

    def _expand(self):
        """
         expands size of the array.
         Time Complexity: O(n)
        """
        self._array += [None] * len(self._array)  # double the size of the array


class StackNode:
    """Represents a single stack node."""
    def __init__(self, value):
        self.value = value
        self.next = None


class LinkedListStack(AbstractStack):

    def __init__(self):
        super().__init__()
        self.head = None

    def __iter__(self):
        probe = self.head
        while True:
            if probe is None:
                return
            yield probe.value
            probe = probe.next

    def push(self, value):
        node = StackNode(value)
        node.next = self.head
        self.head = node
        self._top += 1

    def pop(self):
        if self.is_empty():
            raise IndexError("Stack is empty")
        value = self.head.value
        self.head = self.head.next
        self._top -= 1
        return value

    def peek(self):
        if self.is_empty():
            raise IndexError("Stack is empty")
        return self.head.value

Leetcode

155. Min Stack

利用两个stack，然后通过比对建立一个min_stack

class MinStack:
    def __init__(self):
        self.stack = []
        self.min_stack = []

    def push(self, x):
        self.stack.append(x)
        if not self.min_stack:
            self.min_stack.append(x)
        else:
            if x < self.min_stack[-1]:
                self.min_stack.append(x)
            else:
                self.min_stack.append(self.min_stack[-1])
        
        
    def pop(self):
        if not self.stack and not self.min_stack: return
        self.stack.pop()
        self.min_stack.pop()

        
    def top(self):
        return self.stack[-1]
        

    def getMin(self):
        return self.min_stack[-1]

优化 : min_stack的空间任然可以被优化，与其和之前stack一对一关系的储存，我们可以通过存储(min_val,len(stack))的方式，记录最小值第一次出现的位置。当我们pop的时候，如果len(stack)不是tuple[1]，就不对min_stack进行操作。

class MinStack:
    def __init__(self):
        self.stack = []
        self.min_stack = []

    def push(self, x):
        self.stack.append(x)
        if not self.min_stack:
            self.min_stack.append((x, len(self.stack)))
        else:
            if x < self.min_stack[-1][0]:
                self.min_stack.append((x, len(self.stack)))
        
    def pop(self):
        if not self.stack and not self.min_stack: return
        if self.min_stack[-1][1] == len(self.stack):
            self.min_stack.pop()
        self.stack.pop()
        
    def top(self):
        return self.stack[-1]
        
    def getMin(self):
        return self.min_stack[-1][0]