【面试题021】包含min函数的栈
MinStack.cpp:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 | #include <iostream> #include "StackWithMin.h" #include <cstdio> using namespace std; void Test(char *testName, const StackWithMin<int> &stack, int expected) if(stack.min() == expected) int main() stack.push(3); stack.push(4); stack.push(2); stack.push(3); stack.pop(); stack.pop(); stack.pop(); stack.push(0); return 0; |
StackWithMin.cpp:
1 | #include "StackWithMin.h" |
StackWithMin.h:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 | #ifndef _STACK_WITH_MIN_H_ #define _STACK_WITH_MIN_H_ #include <stack> template <typename T> class StackWithMin T &top(void); void push(const T &value); const T &min(void) const; bool empty() const; private: template <typename T> void StackWithMin<T>::push(const T &value) // 当新元素比之前的最小元素小时,把新元素插入辅助栈里; template <typename T> void StackWithMin<T>::pop() m_data.pop(); template <typename T> const T &StackWithMin<T>::min() const return m_min.top(); template <typename T> T &StackWithMin<T>::top() template <typename T> const T &StackWithMin<T>::top() const template <typename T> bool StackWithMin<T>::empty() const template <typename T> size_t StackWithMin<T>::size() const #endif /*_STACK_WITH_MIN_H_*/ |
Makefile:
1 2 3 4 5 6 7 8 9 10 11 12 | .PHONY:clean CPP=g++ CFLAGS=-Wall -g BIN=test OBJS=MinStack.o StackWithMin.o LIBS= $(BIN):$(OBJS) $(CPP) $(CFLAGS) $^ -o $@ $(LIBS) %.o:%.cpp $(CPP) $(CFLAGS) -c $< -o $@ clean: rm -f *.o $(BIN) |