C++模拟线性数据结构(堆栈和队列)

在JavaScript、Ruby等解释型动态语言中,数组都是高级数据结构,其中就包含了堆栈和队列这两种数据结构,一般由C链表编写。下面就不用C,用C++的valarray库简单模拟这两种数据结构中。

其中:

  1. 堆栈:先进后出
  2. 队列:先进先出

Array.hxx

/**
 * @{file} Array.hxx
 * @{author} YanWen
 * @{class} Array
 * @{last_modified} 2017-10-18
 */

#ifndef ARRAY_H_
#define ARRAY_H_ 2017

#include <iostream>
#include <valarray>
#include <cstddef>            // size_t

using std::valarray;

template <typename T, int max = 10>      // lenght should be given when instantialize the template (default is 10)
class Array {
private:
  /* data */
  valarray<T> _data = valarray<T>(max);
  int _length       = 0;

public:
  // constructors
  Array() { }
  Array(Array & t)                  : _data(t._data), _length(t.length()) { }
  Array(const Array & t)            : _data(t._data), _length(t.length()) { }
  Array(T t[], size_t length)       : _data(t, length), _length(length) { }
  Array(const T t[], size_t length) : _data(t, length), _length(length) { }

  // methods
  bool isempty()            { return _length == 0; }
  bool isfull()             { return _length == max; }

  T shift();
  T pop();

  bool push(T & t)          { return _length < _data.size() ? _data[++_length - 1] = t, true : false; }
  bool push(const T & t)    { return _length < _data.size() ? _data[++_length - 1] = t, true : false; }

  int  length()             { return _length; }
  int  size()               { return _data.size(); }
  void resize(int new_size) { _data.resize(new_size); _length = 0; }

  // overload operators
  T &             operator[](size_t i)       { return _data[i]; }
  T               operator[](size_t i) const { return _data[i]; }
  Array<T, max> & operator=(const Array & a);

  std::ostream & ostream(std::ostream & os);

  // distructor
  virtual ~Array() { }
};

// Implementation
// Public
template <typename T, int max>
T Array<T, max >::shift() {
  T shifted_val = _data[0];

  _data = _data.shift(1);
  _length--;
  return shifted_val;
}

template <typename T, int max>
T Array<T, max>::pop() {
  T poped_val = _data[_length - 1];

  _data[_length - 1] = T();
  _length--;
  return poped_val;
}

// Override
template <typename T, int max>
Array<T, max> & Array<T, max >::operator=(const Array & a) {
  if (this == & a) return * this;

  if (!isempty()) {
    _data.shift(_length);
    _length = 0;
  }

  _data   = a._data;
  _length = a._length;
  return * this;
}

// Friends
template <typename T, int max>
std::ostream & Array<T, max>::ostream(std::ostream & os) {
  for (auto it = begin(_data); it < end(_data); it++)
    os << ' ' << * it;

  return os;
}

#endif

一般来说,在动态语言数组里,常用的堆栈操作为push和pop,常用的队列操作为push和shift,在以上Array类中都有模拟。当然,这个Array很简陋,不能和JS等语言里的数组相比,不过如果你有兴趣可以设计一个更强大的Array。

作者: V

Web Dev

發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com 標誌

您的留言將使用 WordPress.com 帳號。 登出 /  變更 )

Google photo

您的留言將使用 Google 帳號。 登出 /  變更 )

Twitter picture

您的留言將使用 Twitter 帳號。 登出 /  變更 )

Facebook照片

您的留言將使用 Facebook 帳號。 登出 /  變更 )

連結到 %s