构造一个特殊栈，实现方法getmin，返回栈中的最小元素 Python版

浅浅的花香味﹌ 2022-06-03 08:14 124阅读 0赞

**题目**：  
构造一个栈结构，其中需要实现一个方法，该方法 getmin，返回栈中的最小的元素。

**要求**：  
时间复杂度为o（1）。

**分析**：  
之前我写过了用python写一个栈数据结构，代码在这里：  
[队列和栈的Python实现][Python]

在这里，需要以时间复杂度 o（1）完成查找，也就是说，必须以空间换时间。因此，构造一个栈，这个栈的栈顶必须保持始终都是原始栈的最小值。在原始栈插入和弹出元素时，这个辅助栈必须跟着配合，保持最小值。具体操作不细述了，看代码里即可。

**代码**：

class Node(object):
        # 栈结点
        def __init__(self, value, next=0):
            self.value = value
            self.next = next  # 指针
    
    class SpecialStack(object):
        def __init__(self):
            self.head = 0
            self.stackmin = []
    
        def init_stack(self, data):
            self.head = Node(data[0])
            if self.stackmin =[]:
                self.stackmin.append(data[0])
            p = self.head
            for i in data[1:]:
                p.next = Node(i)
                pop = self.stackmin.pop()
                if pop >= i:
                    self.stackmin.append(pop)
                    self.stackmin.append(i)
                else:
                    self.stackmin.append(pop)
                p = p.next
    
        def clear_stack(self):
            self.head = 0
            self.stackmin = []
    
        def is_empty(self):
            if self.head == 0:
                return True
            else:
                return False
    
        def get_length(self):
            p, length = self.head, 0
            while p != 0:
                length += 1
                p = p.next
            return length
    
        def push(self, value):  # 向栈中添加一个结点
            if self.is_empty():
                self.head = Node(value)
            else:
                p = self.head
                for _ in xrange(self.get_length() - 1):
                    p = p.next
                p.next = Node(value)
                pop = self.stackmin.pop()
                if pop >= value:
                    self.stackmin.append(pop)
                    self.stackmin.append(value)
                else:
                    self.stackmin.append(pop)
    
        def get_top(self):  # 获得栈顶元素
            if self.is_empty():
                print 'This is an empty stack.'
                return
            else:
                p = self.head
                for _ in xrange(self.get_length()):
                    p = p.next
                return p.value
    
        def pop(self):  # 弹出栈顶元素
            length = self.get_length()
            if self.is_empty():
                print 'This is an empty stack.'
                return
            elif length == 1:
                p = self.head
                self.head = 0
                self.stackmin = []
                return p.value
            elif length == 2:
                p = self.head
                value = p.next.value
                self.head.next = 0
                if len(self.stackmin) == 2:
                    self.stackmin.pop()
                return value
            else:
                p = self.head
                for _ in xrange(1, length - 1):
                    p = p.next
                pop = p.next
                p.next = 0
                stack_min = self.stackmin.pop()
                if stack_min < pop.value:
                    self.stackmin.append(stack_min)
                return pop.value
    
        def show_stack(self):  # 打印栈中的所有元素
            if self.is_empty():
                print 'This is an empty stack.'
            else:
                p, container = self.head, []
                for _ in xrange(self.get_length() - 1):
                    container.append(p.value)
                    p = p.next
                container.append(p.value)
                print container
    
        def get_min(self):
            '''
                返回链栈中的最小的元素的值，要求时间复杂度为 o(1)，主要方法是用空间换时间，构建一个存放最小栈元素的栈 stackmin。
                每次向栈中添加元素的时候，都判断这个元素是不是比栈中的元素小，如果是相等或更小，则将该数放在 stackmin 中。
                每次弹出一个栈顶元素，判断该数是不是比 stackmin的栈顶元素大，如果大，则 stackmin不需要任何操作。
                在查询时，直接返回stackmin的栈顶元素即可。
            '''
            pop = self.stackmin.pop()
            self.stackmin.append(pop)
            return pop

[Python]: http://blog.csdn.net/dongrixinyu/article/details/78619048