顺序栈(滞前)

qq1242009750

                                                                            

顺序栈(滞前)

在23到28讲中鱼哥给我们讲了滞后的循序栈,现在我们来说说滞前栈。
什么是滞后、滞前栈呢? 其实就是入栈的时候栈顶指针的位置，如果入栈时栈顶指针指向前一个元素，那么就是滞前栈。
如果入栈后栈顶指针指向后一个元素，那么就是滞后栈。
结构的定义:
       

1.         struct Stack
   
2.         {
   
3.                 int *base;
   
4.                 int index;
   
5.                 int StackSize;
   
6.         };
   
7. 
   
8.         class CStack
   
9.         {
   
10.         private:
    
11.                 Stack stack;
    
12.         public:
    
13.                 CStack();
    
14.                 ~CStack();
    
15. 
    
16.                 void Push(int e);
    
17.                 void Pop(int *e);
    
18.         };

复制代码

那滞前栈和滞后栈有什么不同呢？ 其实都是一样的，只是出入栈的操作不同下面给出滞前栈代码

1. CStack::CStack()
   
2. {
   
3.         //初始化
   
4.         stack.index = -1;
   
5.         stack.base = new int[STACK_INIT_SIZE];
   
6.         stack.StackSize = STACK_INIT_SIZE;
   
7. }
   
8. 
   
9. 
   
10. CStack::~CStack()
    
11. {
    
12.         delete stack.base;
    
13. }
    
14. 
    
15. 
    
16. void CStack::Pop(int *e)
    
17. {
    
18.         if (&stack.base[stack.index] - stack.base + 1 == 0)
    
19.         {
    
20.                 cout << "栈空!" << endl;
    
21.                 return;
    
22.         }
    
23. 
    
24.         *e = stack.base[stack.index];
    
25.         --stack.index;
    
26. }
    
27. 
    
28. 
    
29. void CStack::Push(int e)
    
30. {
    
31.         if (&stack.base[stack.index] - stack.base + 1 == stack.StackSize)
    
32.         {
    
33.                 //扩容
    
34.                 int *tmp = stack.base;
    
35.                 stack.base = new int[stack.StackSize + INCREMENT];
    
36.                 memcpy(tmp, stack.base, stack.StackSize);
    
37.                 stack.StackSize += INCREMENT;
    
38.                 delete tmp;
    
39.         }
    
40. 
    
41.         stack.index++;
    
42.         stack.base[stack.index] = e;
    
43. }
    

复制代码

可以看出滞前栈 入栈时先自增栈顶指针，后放入数值 ，而出时先去出数值后自减栈顶指针。那么栈元素的计算公式为: top - base + 1。

小甲鱼

支持并且鼓舞！

qq1242009750

小甲鱼 发表于 2017-12-23 15:03
支持并且鼓舞！

谢谢 鱼哥的支持

Kitty喜欢小鱼干

涨知识了，很有用