栈、队列（1）

拼搏现实的明天。 2022-06-09 02:14 156阅读 0赞

*   *   *  可查询最值的栈
         *  双栈队列
         *  栈的反转
         *  双栈排序

--------------------

### 可查询最值的栈 ###

定义栈的数据结构，请在该类型中实现一个能够得到栈最小元素的min函数。

**我的提交**

# -*- coding:utf-8 -*-
    class Solution:
        def __init__(self):
            self.stack = []
            self.minStack = []
    
        def push(self, node):
            self.stack.append(node)
            if not self.minStack:
                self.minStack.append(node)
            elif self.minStack[-1] <= node:
                self.minStack.append(self.minStack[-1])
            else:
                self.minStack.append(node)
    
        def pop(self):
            self.minStack.pop()
            return self.stack.pop()
    
        def top(self):
            return self.stack[-1]
    
        def min(self):
            return self.minStack[-1]

--------------------

### 双栈队列 ###

编写一个类,只能用两个栈结构实现队列,支持队列的基本操作(push，pop)。

给定一个操作序列ope及它的长度n，其中元素为正数代表push操作，为0代表pop操作，保证操作序列合法且一定含pop操作，请返回pop的结果序列。

测试样例：
    [1,2,3,0,4,0],6
    返回：[1,2]

**我的提交**

# -*- coding:utf-8 -*-
    
    class TwoStack:
        def __init__(self):
            self.pushStack = []
            self.popStack = []
        def twoStack(self, ope, n):
            result = []
            for op in ope:
                if op == 0:
                    result.append(self.pop())
                else:
                    self.push(op)
            return result
    
        def push(self, node):
            self.pushStack.append(node)
    
        def pop(self):
            if not self.popStack:
                if not self.pushStack:
                    return None
                while self.pushStack:
                    self.popStack.append(self.pushStack.pop())
                return self.popStack.pop()
            else:
                return self.popStack.pop()
    
    if __name__ == '__main__':
        two = TwoStack()
        print(two.twoStack([287,202,181,156,0],5))

--------------------

### 栈的反转 ###

实现一个栈的逆序，但是只能用递归函数和这个栈本身的pop操作来实现，而不能自己申请另外的数据结构。

给定一个整数数组A即为给定的栈，同时给定它的大小n，请返回逆序后的栈。

测试样例：
    [4,3,2,1],4
    返回：[1,2,3,4]

> 参考：[http://www.cnblogs.com/4everlove/p/3666016.html][http_www.cnblogs.com_4everlove_p_3666016.html]

数据稍微多点时，**严重超时**！！！

# -*- coding:utf-8 -*-
    
    class StackReverse:
        def reverseStack(self, A, n):
            # write code here
            if n == 0:
                return
            if n == 1:
                return A
            temp1 = A.pop()
            self.reverseStack(A, n - 1)
            temp2 = A.pop()
            self.reverseStack(A, n - 2)
            A.append(temp1)
            self.reverseStack(A, n - 1)
            A.append(temp2)
            return A
    
    
    if __name__ == '__main__':
        r = StackReverse()
        print(r.reverseStack([1, 2, 3, 4, 5, 6 ,7, 8, 9],9))

--------------------

### 双栈排序 ###

请编写一个程序，按升序对栈进行排序（即最大元素位于栈顶），要求最多只能使用一个额外的栈存放临时数据，但不得将元素复制到别的数据结构中。

给定一个int\[\] numbers(C++中为vector&ltint>)，其中第一个元素为栈顶，请返回排序后的栈。请注意这是一个栈，意味着排序过程中你只能访问到第一个元素。

测试样例：
    [1,2,3,4,5]
    返回：[5,4,3,2,1]

**我的提交**

# -*- coding:utf-8 -*-
    class TwoStacks:
        def __init__(self):
            self.stack = []
    
        def twoStacksSort(self, numbers):
            # write code here
            if not numbers:
                return 
    
            top = numbers.pop()
            if not self.stack:
                self.stack.append(top)
            elif top < self.stack[-1]:
                length = 0
                while self.stack and top < self.stack[-1]:
                    numbers.append(self.stack.pop())
                    length += 1
                self.stack.append(top)
                for _ in range(length):
                    self.stack.append(numbers.pop())
            else:
                self.stack.append(top)
    
            self.twoStacksSort(numbers)
    
            while self.stack:
                numbers.append(self.stack.pop())
            return numbers

[http_www.cnblogs.com_4everlove_p_3666016.html]: http://www.cnblogs.com/4everlove/p/3666016.html