算法与数据结构八 - 堆栈与队列

class ArrayStack(object):
    def __init__ (self):
        self._data = []
        
    def __len__ (self):
        return len(self._data)
    
    def is_empty(self):
        return len(self._data) == 0
    
    # O(1)
    def push(self, e):
        self._data.append(e)
        
    # O(1)
    def top(self):
        if self.is_empty( ):
            raise ValueError( ‘Stack is empty‘ )
        return self._data[-1]
    
    # O(1)
    def pop(self):
        if self.is_empty( ):
            raise ValueError( ‘Stack is empty‘ )
        return self._data.pop( )  
        
    def printstack(self):
        for i in range(len(self._data)):
            print(self._data[i], end = ‘ ‘)
        print()

class LinkedStack(object):
    def __init__ (self):
        self._list = LinkedList()
        
    def __len__ (self):
        return self._list.length
    
    def is_empty(self):
        return self._list.length == 0
    
    # O(1)
    def push(self, e):
        self._list.add_first(e);
        
    # O(1)
    def top(self):
        return self._list.get_first().value;
    
    # O(1)
    def pop(self):
        return self._list.remove_first().value;
        
    def printstack(self):
        self._list.printlist()

class ArrayQueue:
    DEFAULT_CAPACITY = 10
    def __init__(self):
        self._data = [None] * ArrayQueue.DEFAULT_CAPACITY
        self._size = 0
        self._front = 0
        
    def __len__(self):
        return self._size
    
    def is_empty(self):
        return self._size == 0
    
    def first(self):
        if self.is_empty( ):
            raise ValueError( ‘Queue is empty‘ )
        return self._data[self._front]
    
    def dequeue(self):
        if self.is_empty( ):
            raise ValueError( ‘Queue is empty‘ )
        answer = self._data[self._front]
        self._data[self._front] = None
        self._front = (self._front + 1) % len(self._data)
        self._size -= 1
        return answer
    
    def enqueue(self, e):
        if self._size == len(self._data):
            self._resize(2 * len(self._data))
        pos = (self._front + self._size) % len(self._data)
        self._data[pos] = e
        self._size += 1
        
    def resize(self, cap):
        old = self._data
        self._data = [None] * cap
        walk = self._front
        for k in range(self._size):
            self._data[k] = old[walk]
            walk = (1 + walk) % len(old)
        self._front = 0
        
    def printqueue(self):
        for i in range(self._size):
            pos = (self._front + self._size - 1 - i) % len(self._data)
            #print(str(i), ": ", str(pos))
            print(self._data[pos], end = " ")  
        print()

class LinkedQueue(object):
    def __init__(self):
        self.head = None
        self.tail = None
        self.count = 0  
        
    def enqueue(self, value):
        new_node = Node(value)

        if self.tail is not None:
            self.tail.next = new_node
        else:
            self.head = new_node

        self.tail = new_node
        self.count += 1

    def dequeue(self):
        if not self.is_empty():
            # point head to next node
            tmp = self.head
            self.head = self.head.next
            print("dequeue sucess")
            self.count -= 1
            return tmp
        else:
            raise ValueError("Empty QUEUE")

    def is_empty(self):
        if self.head is None and self.tail is None:
            return True
        else:
            return False

    def peek(self):
        return self.head.data

    def __len__(self):
        return self.count    

    def is_empty(self):
        return self.count == 0
    
    def print(self):
        node = self.head
        while node:
            print(node.value, end = " ")
            node = node.next
        print(‘‘)