CareerCup_3.3@1point3acres

main.cpp

//
//  main.cpp
//  cc3_3
//
//  Created by kandia on 12-5-3.
//  Copyright (c) 2012年 kandia. All rights reserved.
//

/*******************************************************************************
 * 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 singlestack) 
 * FOLLOW UP
 * Implement a function popAt(int index) which performs a pop operation on a 
 * specific sub-stack
 ******************************************************************************/

/*******************************************************************************
 * we support all elements are nonegative.
 * class Stack
 * class List
 * class SetOfStacks
 ******************************************************************************/

#include <iostream>
#define MaxCount 2

class Stack{
 public:
    void push(int n);
    int pop();
    bool isEmpty() const;
    bool isFull() const;
    int gettop() const;
    void clear();
    Stack(): top(-1){}
    
 private:
    int top;
    int arr[MaxCount];
};

void Stack::push(int n) {
    if (!isFull()) {
        arr[++top] = n;
    } else {
        std::cout << "Stack is full." << std::endl;
    }
}

int Stack::pop() {
    if(isEmpty()) {
        std::cout << "Stack is empty." << std::endl;
        return -1;
    } else {
        return arr[top--];
    }
}

bool Stack::isEmpty() const {
    return top == -1;
}

bool Stack::isFull() const {
    return top == MaxCount - 1;
}

int Stack::gettop() const {
    return arr[top];
}

void Stack::clear() {
    top = -1;
}

struct List {
    Stack s;
    List *next;
    List(): next(NULL){}
};

class SetOfStacks {
 public:
    SetOfStacks(): head(NULL), tail(NULL), stacknum(0){}
    ~SetOfStacks();
    void push(int n);
    int pop();
    bool isEmpty() const;
    int gettop() const;
    int stack_count() const;
    int popAt(int index);
    
 private:
    SetOfStacks(SetOfStacks &);//disable copy constructor
    SetOfStacks& operator=(SetOfStacks &);//disable assignment
    void add_stack();
    void rm_stack();
    List *head, *tail;
    int stacknum;
};

SetOfStacks::~SetOfStacks() {
    List *temp;
    while (head != tail) {
        temp = head;
        head = head->next;
        delete temp;
    }
    delete tail;
}

void SetOfStacks::push(int n) {
    if (head == NULL) {
        head = new List;
        tail = head;
        stacknum++;
    }
    if (tail->s.isFull()) {
        add_stack();
    }
    tail->s.push(n);
}

int SetOfStacks::pop() {
    if (isEmpty()) {
        std::cout << "no element is stacks" << std::endl;
        return -1;
    }
    int ans = tail->s.pop();
    if (tail->s.isEmpty()) {
        rm_stack();
    }
    return ans;
}

bool SetOfStacks::isEmpty() const {
    return head == NULL;
}

int SetOfStacks::gettop() const {
    return tail->s.gettop();
}

int SetOfStacks::stack_count() const {
    return stacknum;
}

void SetOfStacks::add_stack() {
    List *temp = new List;
    tail->next = temp;
    tail = temp;
    stacknum++;
}

void SetOfStacks::rm_stack() {
    if (head == tail) {
        delete tail;
        head = NULL;
        tail = NULL;
        stacknum--;
        return;
    }
    List *temp;
    temp = head;
    while (temp->next != tail) {
        temp = temp->next;
    }
    delete tail;
    tail = temp;
    stacknum--;
}

int SetOfStacks::popAt(int index)   {
    if (index < 1 || index > stacknum) {
        std::cout << "index error." << std::endl;
        return -1;
    } else {
        int i = 1;
        List *temp = head;
        while (i < index) {
            temp = temp->next;
            i++;
        }
        return temp->s.pop();
    }
}

int main() {
    SetOfStacks s;
    s.push(12);
    s.push(13);
    s.push(14);
    std::cout << s.pop() << " " << s.stack_count() << std::endl;
    std::cout << s.popAt(1) << std::endl;
    std::cout << s.pop() << " " << s.stack_count() << std::endl;
    std::cout << s.pop() << " " << s.stack_count() << std::endl;
    std::cout << s.stack_count() << std::endl;
    return 0;
}