一、顺序栈的思考

栈的顺序存储结构其实挺方便的,因为栈只从栈顶进出元素,所以不存在线性表插入和删除时移动元素位置的问题,不过他有一个重大的缺陷,就是要事先确定数组存储空间的大小,万一不够用了呢,那么就需要通过编程手段来扩展数组的容量,非常麻烦。对于一个栈,也只能尽量考虑周全,设计出合适大小的数组来处理。但是对于两个相同类型的栈,却可以做到最大限度的利用事先开辟的存储空间来操作。

如果有两个相同类型的栈,为他们各自开辟了数组空间,可能第一个栈已经满了,在进栈就溢出了,而此时第二个栈还有很多存储空间,这样是不是有点浪费内存空间。完全可以用一个数组来存储两个站,只不过需要点小技巧

二、两栈共享内存空间的C++实现

#include <iostream>
#include <cstdlib>
using namespace std;
#define MAX_SIZE = 0xFFFF;
template<typename T>
class SeqStack {
public:
 SeqStack();
 SeqStack(int size);
 virtual ~SeqStack();
 void push(const T &item, int stackNumber);
 T pop(int stackNumber);
 T getTop(int stackNumber);
 bool empty(int stackNumber) const;
 bool full() const;
 void clear(int stackNumber);
 int length(int stackNumber) const;
protected:
 // 栈顶1 指示
 int top1;
 // 栈顶2 指示
 int top2;
 // 数组名
 T *stack;
 // 栈最大可容纳元素个数
 int maxSize;
};
template<typename T>
SeqStack<T>::SeqStack() : top1(-1), top2(MAX_SIZE), maxSize(MAX_SIZE) {
 this->stack = new T[MAX_SIZE];
 if (this->stack == nullptr) {
  cout << "动态存储分配失败!" << endl;
 }
}
template<typename T>
SeqStack<T>::SeqStack(int size) : top1(-1), top2(size), maxSize(size) {
 this->stack = new T[size];
 if (this->stack == nullptr) {
  cout << "动态存储分配失败!" << endl;
 }
}
template<typename T>
SeqStack<T>::~SeqStack() {
 delete[]stack;
}
template<typename T>
void SeqStack<T>::push(const T &item, int stackNumber) {
 if (this->top1 + 1 == this->top2) {
  cout << "栈已满,不能压栈!" << endl;
 }
 else {
  if (stackNumber == 1) {
   this->stack[++top1] = item;
  }
  else {
   this->stack[--top2] = item;
  }
 }
}
template<typename T>
T SeqStack<T>::pop(int stackNumber) {
 if (stackNumber == 1) {
  if (this->top1 == -1) {
   cout << "1号栈 是空栈" << endl;
  }
  else
  {
   return this->stack[this->top1--];
  }
 }
 else if (stackNumber == 2) {
  if (this->top2 == this->maxSize) {
   cout << "2号栈 是空栈" << endl;
  }
  else
  {
   return this->stack[this->top2++];
  }
 }
}
template<typename T>
T SeqStack<T>::getTop(int stackNumber) {
 if (stackNumber == 1) {
  if (this->top1 == -1) {
   cout << "1号栈 是空栈" << endl;
  }
  else
  {
   return this->stack[this->top1];
  }
 }
 else if (stackNumber == 2) {
  if (this->top2 == this->maxSize) {
   cout << "2号栈 是空栈" << endl;
  }
  else
  {
   return this->stack[this->top2];
  }
 }
}
template<typename T>
bool SeqStack<T>::empty(int stackNumber) const {
 if (stackNumber == 1) {
  return this->top1 == -1;
 }
 else if (stackNumber == 2) {
  return this->top2 == this->maxSize;
 }
}
template<typename T>
bool SeqStack<T>::full() const {
 return this->top1 + 1 == this->top2;
}
template<typename T>
void SeqStack<T>::clear(int stackNumber) {
 if (stackNumber == 1) {
  this->top1 = -1;
 }
 else if (stackNumber == 2) {
  this->top2 = this->maxSize;
 }
}
template<typename T>
int SeqStack<T>::length(int stackNumber) const {
 if (stackNumber == 1) {
  return this->top1 + 1;
 }
 else if (stackNumber == 2) {
  return this->maxSize - this->top2;
 }
}
int main() {
 int data[5] = { 1, 2 ,3, 4, 5 };
 SeqStack<int> stack(10);
 cout << "入栈1 元素: ";
 for (int i = 1; i <= 5; i++) {
  stack.push(i, 1);
  cout << i << " ";
 }
 cout << endl;
 cout << "入栈2 元素: ";
 for (int i = 21; i <= 25; i++) {
  stack.push(i, 2);
  cout << i << " ";
 }
 cout << endl;
 cout << "栈1 的元素个数: " << stack.length(1) << endl;
 cout << "栈2 的元素个数: " << stack.length(2) << endl;
 cout << "栈顶1 元素: " << stack.getTop(1) << endl;
 cout << "栈顶2 元素: " << stack.getTop(2) << endl;
 cout << "是否栈满: " << stack.full() << endl;
 cout << "栈1 是否栈空: " << stack.empty(1) << endl;
 cout << "栈2 是否栈空: " << stack.empty(2) << endl;
 cout << "出栈元素: ";
 while (!stack.empty(1))
 {
  cout << stack.pop(1) << " ";
 }
 cout << endl;
 cout << "栈1 的元素个数: " << stack.length(1) << endl;
 cout << "栈2 的元素个数: " << stack.length(2) << endl;
 cout << "栈顶1 元素: " << stack.getTop(1) << endl;
 cout << "栈顶2 元素: " << stack.getTop(2) << endl;
 cout << "是否栈满: " << stack.full() << endl;
 cout << "栈1 是否栈空: " << stack.empty(1) << endl;
 cout << "栈2 是否栈空: " << stack.empty(2) << endl;
 cout << "再一次入栈2 元素: ";
 for (int i = 26; i <= 27; i++) {
  stack.push(i, 2);
  cout << i << " ";
 }
 cout << "栈顶2 元素: " << stack.getTop(2) << endl;
 cout << "栈2 的元素个数: " << stack.length(2) << endl;
 system("pause");
 return 0;
}


关注【游戏讲坛】微信公众号,获取最新动态!