实现push,pop,max为O(1)的栈

一时失言乱红尘 2022-07-15 08:56 73阅读 0赞

\#原理  
使用两个栈来实现要求: 栈的push,pop,max都为O(1)。

1.  一个栈用来保存入栈数据中的最大值
2.  另一个栈用来正常保存入栈和出栈的数据，它max方法用来调用第一个栈保存的当前最大值

\#实现  
\#\#辅助栈  
作用：用于保存当前最大值的栈

template<typename T>
    class stackMax
    {
    public:
    	stackMax():size(0), capacity(1), data(new T[capacity])
    	{
    	}
    	~stackMax() 
    	{
    		if (data) {
    			delete[] data;
    		}
    	}
    	
    	void push(T x) {
    		if (size >= capacity) {
    			resize();
    		}
    		data[size++] = x;
    	}
    	
    	T top() {
    		if (size <= 0) {
    			return T();
    		}
    		return data[size-1];
    	}
    	void pop() {
    		if (size <= 0) {
    			return;
    		} else if (size <= capacity/4) {
    			resize();
    		}
    		size--;
    	}
    private:
    	void resize(unsigned size) {
    		if (size >= capacity) {
    			capacity *= 2;
    		} else if (size <= capacity/4) {
    			capacity /= 2;
    		}
    		T *copy = new T[capacity];
    		for (unsigned i = 0; i < size; i++) 
    			copy[i] = data[i];
    		delete[] data;
    		data = copy;
    	}
    private:
    	unsigned size;
    	unsigned capacity;
    	T *data;
    };

\#\#栈实现一

template<typename T>
    class stack
    {
    public:
    	stack():size(0), capacity(1), data(new T[capacity])
    	{
    	}
    	~stack() 
    	{
    		if (data) {
    			delete[] data;
    		}
    	}
    	
    	void push(T x) {
    		if (size >= capacity) {
    			resize();
    		}
    		
    		if (size == 0 || x > maxStack.top()) {
    			maxStack.push(x);
    		} else {
    			maxStack.push(maxStack.top());
    		}
    		data[size++] = x;
    	}
    	T top() {
    		if (size <= 0) {
    			return T();
    		}
    		return data[size-1];
    	}
    	void pop() {
    		if (size <= 0) {
    			return;
    		} else if (size <= capacity/4) {
    			resize();
    		}
    		size--;
    		maxStack.pop();
    	}
    	int max() {
    		return maxStack.top();
    	}
    private:
    	void resize() {
    		if (size >= capacity) {
    			capacity *= 2;
    		} else if (size <= capacity/4) {
    			capacity /= 2;
    		}
    		T *copy = new T[capacity];
    		for (unsigned i = 0; i < size; i++) {
    			copy[i] = data[i];
    		}
    		delete[] data;
    		data = copy;
    	}
    private:
    	unsigned size;
    	unsigned capacity;
    	T *data;
    	// 用于保存当前最大值得栈
    	stackMax<T> maxStack;
    };

\#测试

int main()
    {
    	stack<int> si;
    	si.push(50);
    	si.push(30);
    	si.push(60);
    	si.push(80);
    	si.push(40);
    	cout << si.max() << endl; // 80
    	si.pop();
    	cout << si.max() << endl; // 80
    	si.pop();
    	cout << si.max() << endl; // 60
    }
    /*
    	stack           maxStack
    	|----|          |----|
    	| 40 |          | 80 |
    	| 80 |          | 80 |
    	| 60 |          | 60 |
    	| 30 |          | 50 |
    	| 50 |          | 50 |
    	|----|          |----|
    */

\#缺点  
这里的实现使用动态增长内存的方式，在push时有可能无法实现O(1)的时间复杂度。要想实现O(1)时间复杂度的push, pop，可以使用**固定大小的数组来实现**。

\#参考  
[实现push,pop,max为O(1)的栈][push_pop_max_O_1]  
[一道IT技术面试题 带有max函数的栈][IT_ _max]

\#补充  
\#栈实现二

template<typename T>
    class stack
    {
    public:
    	stack():size(0), capacity(1), data(new T[capacity])
    	{
    	}
    	~stack() 
    	{
    		if (data) {
    			delete[] data;
    		}
    	}
    	
    	void push(T x) {
    		if (size >= capacity) {
    			resize();
    		}
    		
    		if (size == 0 || x < maxStack.top()) {
    			maxStack.push(x);
    		}  // x >= maxStack.top()时，不压栈
    		data[size++] = x;
    	}
    	T top() {
    		if (size <= 0) {
    			return T();
    		}
    		return data[size-1];
    	}
    	void pop() {
    		if (size <= 0) {
    			return;
    		} else if (size <= capacity/4) {
    			resize();
    		}
    		
    		if (data[size-1] == maxStack.top()) { 
    			maxStack.pop();
    		}
    		size--;
    	}
    	int max() {
    		return maxStack.top();
    	}
    private:
    	void resize() {
    		if (size >= capacity) {
    			capacity *= 2;
    		} else if (size <= capacity/4) {
    			capacity /= 2;
    		}
    		T *copy = new T[capacity];
    		for (unsigned i = 0; i < size; i++) {
    			copy[i] = data[i];
    		}
    		delete[] data;
    		data = copy;
    	}
    private:
    	unsigned size;
    	unsigned capacity;
    	T *data;
    	// 用于保存当前最大值得栈
    	stackMax<T> maxStack;
    };

[push_pop_max_O_1]: http://blog.csdn.net/zhanglei0107/article/details/12527345
[IT_ _max]: http://www.tuicool.com/articles/VvEbEv