顺序栈(滞前)

qq1242009750

                                                                            

顺序栈(滞前)

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

        struct Stack
        {
                int *base;
                int index;
                int StackSize;
        };

        class CStack
        {
        private:
                Stack stack;
        public:
                CStack();
                ~CStack();

                void Push(int e);
                void Pop(int *e);
        };

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

CStack::CStack()
{
        //初始化
        stack.index = -1;
        stack.base = new int[STACK_INIT_SIZE];
        stack.StackSize = STACK_INIT_SIZE;
}


CStack::~CStack()
{
        delete stack.base;
}


void CStack::Pop(int *e)
{
        if (&stack.base[stack.index] - stack.base + 1 == 0)
        {
                cout << "栈空!" << endl;
                return;
        }

        *e = stack.base[stack.index];
        --stack.index;
}


void CStack::Push(int e)
{
        if (&stack.base[stack.index] - stack.base + 1 == stack.StackSize)
        {
                //扩容
                int *tmp = stack.base;
                stack.base = new int[stack.StackSize + INCREMENT];
                memcpy(tmp, stack.base, stack.StackSize);
                stack.StackSize += INCREMENT;
                delete tmp;
        }

        stack.index++;
        stack.base[stack.index] = e;
}

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

小甲鱼

支持并且鼓舞！

qq1242009750

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

谢谢 鱼哥的支持

Kitty喜欢小鱼干

涨知识了，很有用