剑指offer 21---实现一个栈, 要求实现Push( 出栈) 、 Pop( 入栈) 、 Min( 返回最小值的操作) 的时间复杂度为O(1)

xiaoxiao2021-02-27  481

栈:先进后出

实现方法:

利用栈的性质,首先建立q1,q2两个栈,两个栈均为空。

1.插入数据时,第一个数据在q1,q2中均插入。

2.后面的数据依次插入q1中,每次插入一个数据后均和q2中的栈顶比较,如果此时数据大于s2的栈顶,则该数据不插入q2 中,如果此时数据小于或等于此时q2的栈顶,则将该数据插入s2,依次进行。

3.当所有数据入栈完毕后,s2的栈顶存储的即为该列所有数据的最小值。

代码实现如下:

#include <iostream> #include <stack> #include <Windows.h> using namespace std; template <class T> class Stack { public: Stack() {} ~Stack() {} void Push(const T& data) //入栈 { q1.push(data); //不做判断,先将所有数据压入q1 if (q2.empty() || data <= q2.top()) //如果q2为空或者要插入的数据小于或等于q2的栈顶,即插入q2中,否则不插入q2 { q2.push(data); } } void Pop() //出栈 { if (!q1.empty()) //q1不为空时,才可出栈 { if (q1.top() == q2.top()) //如果存在q1和q2有相同数据,即说明,该数据压入了q1和q2 { q2.pop(); } q1.pop(); //q1每次均需要出栈 } } T Min() //找栈中的最小数据 { //即q2的栈顶就是用来存放最小数据 if (q2.empty()) { return 0; } return q2.top(); } void Print() //打印 { size_t size = q1.size(); cout << "q1:"; while (size) { cout<< q1.top() << "->"; q1.pop(); --size; } cout << endl; size = q2.size(); cout << "q2:"; while (size) { cout<< q2.top() << "->"; q2.pop(); --size; } cout << endl; } protected: stack<T> q1; //栈1 stack<T> q2; //栈2 };

PS:因为打印时,每一次打印均pop一次数据,当所有数据打印完时,q1,q2中已经没有数据,所以无法将pop前,pop后结果展现在一起,每次pop数据,这样可以防止内存泄漏。

一、原始插入的结果:

#include "stack.h" void TestStack() { Stack<int> pp; pp.Push(16); pp.Push(3); pp.Push(6); pp.Push(7); pp.Push(4); pp.Push(2); pp.Push(1); pp.Push(9); pp.Push(10); pp.Push(8); cout <<"pp.Min:"<< pp.Min() << endl;  pp.Print(); } int main() { TestStack(); system("pause"); return 0; }

二、pop后的结果

#include "stack.h" void TestStack() { Stack<int> pp; pp.Push(16); pp.Push(3); pp.Push(6); pp.Push(7); pp.Push(4); pp.Push(2); pp.Push(1); pp.Push(9); pp.Push(10); pp.Push(8); //pp.Print(); Pop前打印的为原始插入的数据,每一次打印时均会pop掉栈中的数据,数据打印完时,q1,q2为空,优点是可以防止内存泄漏。所以看原始现象时,需要将下面代码注释掉 pp.Pop(); pp.Pop(); pp.Pop(); pp.Pop(); pp.Pop(); //pp.Pop(); //pp.Pop(); //pp.Pop(); cout << "pp.Min:" << pp.Min() << endl; pp.Print(); } int main() { TestStack(); system("pause"); return 0; }

转载请注明原文地址: https://www.6miu.com/read-214.html

最新回复(0)