使用栈实现数组

Question

一种语言没有数组作为数据类型，但它有堆栈作为数据类型，并且可以声明堆栈；并定义了 push、pop 和 isempty 操作。
那么我们如何使用两个栈以及以上操作来实现数组呢？

Answer 1

效率极其低下 - 但是：

Stack 1 包含详细信息
堆栈 2 为空。

要遍历数组，请弹出堆栈 1 ，当您需要下一个时，请将前一个放入堆栈 2 中，然后再次弹出堆栈 1 。重复直到“isempty”。

如果你想要第N个值，则将非空堆栈弹出N次，同时将不需要的推入另一个堆栈。然后当你玩完它后，将其清空到另一个堆栈中。请注意，这会翻转顺序。

Answer 2

使用两个堆栈，您可以获得某种随机访问（这就是您对数组感兴趣的内容），如下所示：

• 将所有内容放在堆栈上。
• 每次您必须访问非堆栈顶部的内容（弹出）时，您都会从该堆栈中弹出所有元素，然后将它们按顺序推入第二个堆栈。

通过将元素从一个堆栈传递到另一个堆栈，可以模拟迭代。

Answer 3

数组的第一个元素是 stack1 的底部；
数组的最后一个元素是 stack2 的底部；
数组的当前元素是 stack1 的顶部；
通过将 stack1 的元素移至 stack2（移至开头）来迭代数组，反之亦然（移至结尾）。

Answer 4

#include <stdio.h>
#include <stdlib.h>

#define Type int
#define DefaultValue 0

#define bool int

typedef struct stack{
    Type *stack;
    Type *sp;
    size_t size;
} Stack;

Stack* Stack_make(size_t size){
    Stack *s;
    s = (Stack*)malloc(sizeof(Stack));
    s->stack = (Type*)malloc(sizeof(Type)*size);
    s->sp = s->stack -1;
    s->size = size;
    return s;
}

bool Stack_empty(Stack *s){//isempty
    return s->sp < s->stack;
}

void Stack_push(Stack *s, Type value){
    if(s->sp >= s->stack + s->size -1){
        fprintf(stderr, "stack over flow\n");
        exit(-1);
    }
    *(++s->sp) = value;
}

Type Stack_pop(Stack *s){
    if(Stack_empty(s)){
        fprintf(stderr, "stack is empty\n");
        exit(-2);
    }
    return *s->sp--;
}

void Stack_free(Stack *s){
    if(s!=NULL){
        free(s->stack);
        free(s);
    }
}

typedef struct array {
    Stack *front;
    Stack *back;
    size_t size;
    size_t index;
} Array;

Array* Array_make(size_t size){
    Array *a;
    int i;
    a = (Array*)malloc(sizeof(Array));
    a->front = Stack_make(size);
    a->back  = Stack_make(size);
    a->size = size;
    //initialize
    Stack_push(a->front, DefaultValue);
    for(i=0;i<size;++i){
        Stack_push(a->back, DefaultValue);
    }
    a->index = 0;
    return a;
}

void Array_pos_set(Array *a, size_t index){
    if(index < 0 || index >= a->size){
        fprintf(stderr, "out of range\n");
        exit(-11);
    }
    if(a->index < index){
        while(a->index < index){
            Stack_push(a->front, Stack_pop(a->back));
            ++a->index;
        }
    } else if(a->index > index){
        while(a->index > index){
            Stack_push(a->back, Stack_pop(a->front));
            --a->index;
        }
    }
}

Type Array_set(Array *a, size_t index, Type value){
    Array_pos_set(a, index);//a->index == index
    Stack_pop(a->front);
    Stack_push(a->front, value);

    return value;
}

Type Array_get(Array *a, size_t index){
    Type value;
    Array_pos_set(a, index);//a->index == index
    value = Stack_pop(a->front);
    Stack_push(a->front, value);

    return value;
}

void Array_free(Array *a){
    Stack_free(a->front);
    Stack_free(a->back);
    free(a);
}

int main(){
    Array *a;
    int i;

    a = Array_make(10);
    for(i=0;i<10;i++){
        Array_set(a, i, i+1);//a[i] = i+1;
    }
    for(i=0;i<10;i++){
        printf("%d\n", Array_get(a, i));// a[i];
    }
    Array_free(a);

    return 0;
}