用一个数组实现两个堆栈,最好的方法就是一个从头写入,一个从尾写入。这样数组实现堆栈空间的使用效率最高。
从图上可以看到有两个箭头,当它们相遇时,就表示堆栈满。
堆栈结构定义:
1 2 3 4 5 6 |
#define MaxSize 9999 struct DStack{ ElementType Data[MaxSize]; int Top1; //堆栈1的栈顶 int Top2; //堆栈2的栈顶 }; |
实现堆栈基本操作:
- 初始化堆栈
123456void InitializeStack(DStack* Ptrs){Ptrs = new DStack();Ptrs->Top1 = -1;Ptrs->Top2 = MaxSize;} - 判断堆栈满
1 2 3 4 5 6 7 |
bool IsFull(DStack* Ptrs) { if (Ptrs->Top2 - Ptrs->Top1 == 1){ return 1; //堆栈满 } return 0; } |
- 入栈操作
1 2 3 4 5 6 7 8 9 10 11 |
void Push(DStack* Ptrs,ElementType item, int Tag) { if (IsFull){ printf("堆栈满"); return; } if (Tag == 1){ Ptrs->Data[++(Ptrs->Top1)] = item; }else{ Ptrs->Data[--(Ptrs->Top2)] = item; } } |
Tag用于标志是操作哪个堆栈
- 出栈操作实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
ElementType Pop(DStack* Ptrs, int Tag) { if (Tag == 1){ if (Ptrs->Top1 == -1){ printf("堆栈1空"); return NULL; }else return Ptrs->Data[(Ptrs->Top1)--]; }else{ if (Ptrs->Top2 == MaxSize){ printf("堆栈2空"); return NULL; }else return Ptrs->Data[(Ptrs->Top2)++]; } } |