CCI题目3-3:Set Of Stacks

By | 2012 年 11 月 20 日

就用一个vector来装所有的stack。
遇到push操作,先查看最后一个stack有没有装满。没有的话直接push进该栈即可;否则新建一个stack,push进去然后将这个栈加入vector。
遇到pop操作,将最后一个stack进行pop操作,然后如果该stack空了的话,从vector移除该栈。
遇到top操作,返回最后一个stack的top即可。
遇到popAt操作,和pop类似,完了之后查看一下栈是否为空,如果空了的话,就将该栈从vector移除。



题目
Imagine a (literal) stack of plates. If the stack gets too high, it might topple. There- fore, in real life, we would likely start a new stack when the previous stack exceeds some threshold. Implement a data structure SetOfStacks that mimics this. SetOf- Stacks should be composed of several stacks, and should create a new stack once the previous one exceeds capacity. SetOfStacks.push() and SetOfStacks.pop() should behave identically to a single stack (that is, pop() should return the same values as it would if there were just a single stack).
FOLLOW UP
Implement a function popAt(int index) which performs a pop operation on a specific sub-stack.



代码


//
//  main.cpp
//  CCI.3.3.SetOfStack
//
//  Created by Qiu Xiangyu on 12-11-20.
//  Copyright (c) 2012年 Qiu Xiangyu. All rights reserved.
//

#include 
#include 
using namespace std;

template 
class stackNode {
public:
    T                value;
    stackNode    *pre;
};

template 
class singleStack {
    int              _size;
    stackNode    *_top;
public:
    singleStack() {
        _size = 0;
        _top = NULL;
    }
    int size() {
        return _size;
    }
    T *top() {
        return _top ? &_top->value : NULL;
    }
    void push(T val) {
        stackNode *newnode = new stackNode();
        newnode->value = val;
        newnode->pre = _top;
        _top = newnode;
        ++_size;
    }
    void pop() {
        if (_top) {
            stackNode *oldtop = _top;
            _top = _top->pre;
            delete oldtop;
            --_size;
        }
    }
};

template 
class setOfStack {
    int                          _size;
    int                          _singleLmt;
    vector >      _stacks;
public:
    setOfStack(int sizeLimitOnSingleStack = 10){
        _singleLmt = sizeLimitOnSingleStack;
        _size = 0;
    }
    void push(T val) {
        if (_stacks.size() > 0 && _stacks.back().size() < _singleLmt) {
            singleStack &targetStack = _stacks.back();
            targetStack.push(val);
        } else {
            cout<<"new stack for item: "< newstack;
            newstack.push(val);
            _stacks.push_back(newstack);
        }
        ++_size;
    }
    void pop() {
        if (_stacks.size() > 0) {
            singleStack &targetStack = _stacks.back();
            targetStack.pop();
            if (targetStack.size() == 0) {
                cout<<"remove stack at size: "<<_size< 0) {
            return _stacks.back().top();
        }
        return NULL;
    }
};

int main(int argc, const char * argv[])
{
    // insert code here...
    std::cout << "Hello\n";
    setOfStack stk(3);
    for (int i = 0; i < 10; ++i) {
        stk.push(i);
    }
    while (stk.size() > 0) {
        int v = * stk.top();
        cout<

发表评论

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