【Weiss】【第03章】练习3.21：单数组模拟双栈

浏览数：42 / 时间：2015年06月08日

【练习3.21】

编写仅用一个数组而实现两个栈的例程。除非数组的每一个单元都被使用，否则栈例程不能有溢出声明。

Answer:

很简单，一个栈从数组头起，一个栈从数组尾起，分别保留左右栈头索引。

如left=5则表示array[0]~array[4]为左栈元素，right=7则表示array[8]~array[size-1]为右栈元素。

当左右索引交叉时(left=right+1)，0~left-1为左栈，left~size-1为右栈，刚好用完每一个单元。

实现代码：

  1 //练习3.21新增，单数组模拟双栈
  2 template <typename T> class Simu_Double_Stack
  3 {
  4 public:
  5     Simu_Double_Stack() :head(nullptr), left(0), right(0), size(0){}
  6     Simu_Double_Stack(unsigned int _size)
  7     {
  8         this();
  9         head = new T[_size];
 10         size = _size;
 11         right = _size - 1;
 12     }
 13     Simu_Double_Stack(const Simu_Double_Stack& another)
 14     {
 15         size = another.size;
 16         head = new T[size];
 17         left = another.left;
 18         right = another.right;
 19         for (int i = 0; i < size; ++i)
 20             head[i] = another.head[i];
 21     }
 22     ~Simu_Double_Stack(){ destory(); }
 23     Simu_Double_Stack& operator=(const Simu_Double_Stack& another)
 24     {
 25         if (&another != this)
 26         {
 27             destory();
 28             size = another.size;
 29             left = another.left;
 30             right = another.right;
 31             head = new T[size];
 32             for (int i = 0; i < size; ++i)
 33                 head[i] = another.head[i];
 34             return *this;
 35         }
 36     }
 37 public:
 38     //入栈
 39     bool leftpush(const T& item)
 40     {
 41         if (left <= right)
 42         {
 43             head[left++] = item;
 44             return true;
 45         }
 46         else
 47         {
 48             cout << "Overflow" << endl;
 49             return false;
 50         }
 51     }
 52     bool rightpush(const T& item)
 53     {
 54         if (right >= left)
 55         {
 56             head[right--] = item;
 57             return true;
 58         }
 59         else
 60         {
 61             cout << "Overflow" << endl;
 62             return false;
 63         }
 64 
 65     }
 66     //出栈
 67     bool leftpop()
 68     {
 69         if (left > 0)
 70         {
 71             --left;
 72             return true;
 73         }
 74         else
 75         {
 76             cout << "Stack empty" << endl;
 77             return false;
 78         }
 79     }
 80     bool rightpop()
 81     {
 82         if (right < size - 1)
 83         {
 84             ++right;
 85             return true;
 86         }
 87         else
 88         {
 89             cout << "Stack empty" << endl;
 90             return false;
 91         }
 92     }
 93     //获取长度信息
 94     unsigned int leftsize()const{ return left; }
 95     unsigned int rightsize()const{ return size - right - 1; }
 96     unsigned int getsize()const{ return size; }
 97     unsigned int getused()const{ return left + size - right - 1; }
 98     //打印
 99     void leftprint() const
100     {
101         for (unsigned int i = front - 1; i != -1; --i)
102             cout << " " << head[i] << flush;
103     }
104     void rightprint() const
105     {
106         for (unsigned int i = right + 1; i != size; ++i)
107             cout << " " << head[i] << flush;
108     }
109     //清空
110     void leftclear()const{ left = 0; }
111     void rightclear()const{ right = size - 1; }
112 private:
113     //释放内存
114     void destory()
115     {
116         left = right = size = 0;
117         delete[] head;
118         head = nullptr;
119     }
120     T* head = nullptr;
121     unsigned int left;
122     unsigned int right;
123     unsigned int size;
124 };