C++代写：CSCI104 Stack Implementation

发表于 | 分类于
Stack，也就是数据结构中的栈。本题定义了栈的模板和接口，我们只需要实现isEmpty()，push()，pop()，top()这四个函数，以及类的构造函数和析构函数即可。

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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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模板库，因此基本的数据结构都需要我们来实现。

Tip

下面简单给出ListStack.h文件的示例代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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;
}