实现特殊的栈,返回栈中最小元素.md

实现特殊的栈,返回栈中最小元素

实现一个特殊的栈, 在实现栈的基本功能的基础上, 再实现返回栈中最小元素的操作.
要求

1. pop、push、getMin操作的时间复杂度都是O(1)
2. 设计的栈类型可以使用现成的栈结构

知识准备

• 栈

思路

用两个栈, 一个data, 一个min,

data正常压栈出栈, min的操作如下:
1. 如果min为空, 直接入栈;
2. 如果min不为空, 元素和min栈顶比较, 若插入元素小, 向min中压入新插入元素, 若栈顶小, 向min中压入栈顶元素.
3. 出栈的时候, min正常出栈

代码

PHP

class SpecialStack
{
    private $stackData;
    private $stackMin;

    public function __construct()
    {
        $this->stackData = new SplStack();
        $this->stackMin = new SplStack();
    }

    public function push($data)
    {
        if ($this->stackMin->isEmpty()) {
            $this->stackMin->push($data);
        } else {
            if ($data < $this->stackMin->top()) {
                $this->stackMin->push($data);
            } else {
                $this->stackMin->push($this->stackMin->top());
            }
        }
        $this->stackData->push($data);
    }

    public function pop()
    {
        if ($this->stackMin->isEmpty()) {
            throw new Exception('stack is empty');
        }

        $this->stackMin->pop();
        return $this->stackData->pop();
    }

    public function getMin()
    {
        if ($this->stackMin->isEmpty()) {
            throw new Exception('stack is empty');
        }

        return $this->stackMin->top();
    }
}

// Test
$specialStack = new SpecialStack();
$specialStack->push(4);
$specialStack->push(5);
$specialStack->push(3);
$specialStack->push(6);

// 3
echo $specialStack->getMin();
$specialStack->pop();
// 3
echo $specialStack->getMin();
$specialStack->pop();
// 4
echo $specialStack->getMin();
$specialStack->pop();
// 4
echo $specialStack->getMin();
$specialStack->pop();

JAVA

import java.util.Stack;

public class SpecialStack {
	private Stack<Integer> stackData = new Stack<Integer>();
	private Stack<Integer> stackMin = new Stack<Integer>();
	
	public void push(int data) {
		if (this.stackMin.isEmpty()) {
			this.stackMin.push(data);
		} else {
			if (data < this.stackMin.peek()) {
				this.stackMin.push(data);
			} else {
				this.stackMin.push(this.stackMin.peek());
			}
		}
		this.stackData.push(data);
	}
	
	public int pop() {
		if (this.stackMin.isEmpty()) {
			throw new RuntimeException("stack is empty");
		}
		this.stackMin.pop();
		return this.stackData.pop();
	}
	
	public int getMin() {
		if (this.stackMin.isEmpty()) {
			throw new RuntimeException("stack is empty");
		}
		return this.stackMin.peek();
	}
	
	public static void main(String[] args) {
		SpecialStack specialStack = new SpecialStack();
		specialStack.push(4);
		specialStack.push(5);
		specialStack.push(3);
		specialStack.push(6);
		
		// 3
		System.out.println(specialStack.getMin());
		specialStack.pop();
		// 3
		System.out.println(specialStack.getMin());
		specialStack.pop();
		// 4
		System.out.println(specialStack.getMin());
		specialStack.pop();
		// 4
		System.out.println(specialStack.getMin());
		specialStack.pop();
	}
}