跳转至

NOIP 2012 提高组初赛试题 完善程序 新壳栈

题面：

设计了一个新的数据结构，一个栈，一个队列，队列里的东西可以翻转。然后实现的时候，是循环队列。

img

代码：

#include <iostream>

using namespace std; 

const int NSIZE = 100000, CSIZE = 1000; 

//数组 s 模拟一个栈，n 为栈的元素个数
//数组 q 模拟一个循环队列，tail 为队尾的下标，head 为队头的下标 
int n, c, r, tail, head, s[NSIZE], q[CSIZE]; 
bool direction, empty; 

int previous(int k) {
    if (direction)
        return ((k + c - 2) % c) + 1;   // 这样看就很好理解 (k-2+1) 防止负数处理一下
    else
        return (k % c) + 1; 
}

int next(int k) {
    if (direction)
        return (k % c) + 1; 
    else
        return ((k + c - 2) % c) + 1; 
}

void push() {
    int element; 
    cin >> element; 

    if (next(head) == tail) {    // 看队列有没有满，满就把tail指向的存在栈中
        n++; 
        s[n] = q[tail];
        tail = next(tail); 
    }

    if (empty)
        empty = false; 
    else
        head = next(head);       // 新的数据放到head位置  【我觉得这句话非常关键，从这分析是head入队】

    q[head] = element;           // 比较特殊的是，从head入队
}

void pop() {
    if (empty) {
        cout << "Error: the stack is empty!" << endl; return; 
    }

    cout << q[head] << endl;       // q[head]放的是最新的数据，所以弹出q[head]

    if (tail == head)
        empty = true; 
    else {
        head = previous(head);     // head往前倒腾

        if (n > 0) {
            tail = previous(tail); // tail也要往前倒腾
            q[tail] = s[n];        // 从栈顶拿一个数据过来，补充队列
            n--; 
        }
    }
}
void reverse() {
    int temp; 

    if (next(head) == tail) {     // 循环队列刚好排满数据，可以做翻转
        direction =  ! direction; 
        temp = head; 
        head = tail; 
        tail = temp; 
    }
    else
        cout << "Error: less than " << c << " elements in the stack!" << endl; 
}

int main() {
    cin >> c; 

    n = 0; 
    tail = 1; 
    head = 1; 
    empty = true; 
    direction = true; 

    do {
        cin >> r; 
        switch (r) {
            case 1:push(); break; 
            case 2:pop(); break; 
            case 3:reverse(); break; 
        }

        // 调试语句
        printf("---head:%d  tail:%d\n", head, tail);
        printf("q[n]: ");
        for (int i = 1; i <= 10; i++) printf("%d ", q[i]);
        puts("");
        printf("s[n]: ");
        for (int i = 1; i <= n; i++) printf("%d ", s[i]);
        puts("");

    }while (r != 0); 

    return 0; 
}

img

img