CCI题目3-1:Three Stacks in One Array

By | 2012 年 11 月 18 日

一个简单的办法是把array均分成三段,每段用作一个stack;
更灵活的方法是把这个array当链表用。每个节点放一个value和一个pointer,每个pointer指向栈下一位。



题目
Describe how you could use a single array to implement three stacks.



代码


//
//  main.cpp
//  CCI.3.1.Three Stacks in One Array
//
//  Created by Qiu Xiangyu on 12-11-17.
//  Copyright (c) 2012年 Qiu Xiangyu. All rights reserved.
//

#include 
using namespace std;

template 
class stackNode {
public:
    Ts                value;
    stackNode    *pre;
    stackNode() {pre = NULL;}
    stackNode(Ts&avalue, stackNode*thePre):value(avalue),pre(thePre) {;}
};

template 
class triStack {
    int              stackSize[3];
    stackNode    *tops[3];    
    stackNode    *empty;
    stackNode    *buffer = NULL;
    int              bufferSize = 0;
    inline stackNode *getEmptySlot() {
        if (empty == NULL) {
            return NULL;
        }
        stackNode *etop = empty;
        empty = etop->pre;
        return etop;
    }
    inline void reuse(stackNode * node) {
        node->pre = empty;
        empty = node;
    }
public:
    inline int totleSize() {
        int sum = 0;
        for (int i = 0; i < 3; ++i) {
            sum += stackSize[i];
        }
        return sum;
    }
    inline bool isFull() {
        return NULL == empty;
    }
    bool push(int stackIndex,T value) {
        if (stackIndex < 0 || stackIndex >= 3) {
            return false;
        }
        stackNode *slot = getEmptySlot();
        if (NULL == slot) {
            //stack full
            return false;
        }
        stackNode *last = tops[stackIndex];
        slot->pre = last;
        tops[stackIndex] = slot;
        ++stackSize[stackIndex];
        return true;
    }
    bool pop(int stackIndex) {
        if (stackIndex < 0 || stackIndex >= 3) {
            return false;
        }
        stackNode *top = tops[stackIndex];
        if (NULL == top) {
            return false;
        }
        tops[stackIndex] = top->pre;
        --stackSize[stackIndex];
        reuse(top);
    }
    T *top(int stackIndex) {
        if (stackIndex < 0 || stackIndex >= 3) {
            //error
            return NULL;
        }
        stackNode *topNode = tops[stackIndex];
        if (NULL == topNode) {
            return NULL;
        }
        return &topNode->value;
    }
    triStack(int totalSize) {
        if (totalSize > 0) {
            bufferSize = totalSize;
            buffer = new stackNode [bufferSize];
            
            //initilize the empty chain.
            stackNode * last = NULL;
            for (int i = 0; i < bufferSize; ++i) {
                stackNode *pnode = buffer + i;
                pnode->pre = last;
                last = pnode;
            }
            empty = buffer + bufferSize - 1;
            
            //initilize the stacks
            for (int i = 0; i < 3; ++i) {
                tops[i] = NULL;
                stackSize[i] = 0;
            }
        } else {
            cout<<"Error stack size\n";
        }
    }
    ~triStack() {
        if (buffer) {
            delete buffer;
            buffer = NULL;
        }
    }
};

int main(int argc, const char * argv[])
{
    std::cout << "Hello\n";
    
    triStack teststack(3);
    if (true != teststack.push(0, 0)) cout<<"err\n";
    if (true != teststack.push(1, 1)) cout<<"err\n";
    if (true != teststack.push(2,2)) cout<<"err\n";
    if (false != teststack.push(2,3)) cout<<"err\n";
    if (true != teststack.isFull()) cout<<"err\n";
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注