论坛 › 数据结构与算法 › 顺序栈(滞前)

qq1242009750 发表于 2017-12-23 14:58:57

顺序栈(滞前)

本帖最后由 qq1242009750 于 2017-12-23 15:09 编辑

                                                                             顺序栈(滞前)
在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.StackSize = STACK_INIT_SIZE;
}


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


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

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


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

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


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

小甲鱼 发表于 2017-12-23 15:03:26

支持并且鼓舞！

qq1242009750 发表于 2017-12-23 15:06:34

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

谢谢 鱼哥的支持 {:5_92:}

Kitty喜欢小鱼干 发表于 2018-8-9 22:11:18

涨知识了，很有用{:5_105:}

查看完整版本: 顺序栈(滞前)