全文链接：tecdat.cn/?p=29648
Requirement
Implement a templated Stack class. It must implement the following interface (abstract class), which you should inherit from. In other words, create a file IStack.h which contains this definition, and then your own class (which may be called something like ListStack or ArrayStack or other, depending on how you impement it) should inherit publicly from IStack.
template <class T>
class IStack
{
public:
/ returns whether the stack contains any elements /
virtual bool isEmpty() const = 0;
/ adds a value to the top of the stack /
virtual void push(const T& val) = 0;
/* deletes the top value from the stack.
Throws EmptyStackException if stack was empty.
However, you should avoid having this exception thrown,
by checking whether the stack is empty before calling it. */virtual void pop() = 0;
/* returns the top value on the stack.
Throws EmptyStackException if stack was empty.
However, you should avoid having this exception thrown,
by checking whether the stack is empty before calling it. */virtual const T& top() const = 0;
};
复制代码
Your implementation can reuse some of your earlier linked list code, or you can build it on top of an array (which you dynamically allocate) – your choice. You must ensure that all functions run in time O(1) (amortized time O(1) if you use an array implementation), and should give an explanation with your code for why your code runs in O(1) time.
Your solution to this problem absolutely cannot use STL container classes (so no stack or vector or deque or list or such provided by STL).
Analysis
Stack，也就是数据结构中的栈。本题定义了栈的模板和接口，咱们只须要实现 isEmpty()，push()，pop()，top() 这四个函数，以及类的构造函数和析构函数即可。咱们能够利用 linked list，即线性链表来存储数据，这样也能保障 functions run in time O(1)，即工夫复杂度为 1。
另外一点须要留神的是，本题不能应用 STL 模板库，因而根本的数据结构都须要咱们来实现。
Tips
上面简略给出 ListStack.h 文件的示例代码
template <class T>
class ListStack: public IStack
{
public:
ListStack();
ListStack(int sz = 20);
ListStack(const ListStack<T>& ls);
~ListStack();
void bool isEmpty() const;
void push(const T& val);
void pop();
const T& top() const;
private:
T* listStack;
int size;
}
复制代码