A language has not array as a data type but it has stack as a data type and one can declare stack's; and push, pop and isempty operations are defined.
So how can we implement array using two stacks and above operations?
-
4What is array? Which operations should be allowed on it? Do you need random access? insertion at the beginning/end? insertion in the middle? lookup?Vlad– Vlad2011-11-12 18:40:30 +00:00Commented Nov 12, 2011 at 18:40
-
2@Vlad: I think we share the pride of having a vampire namesake. :)Vlad– Vlad2011-11-12 18:44:30 +00:00Commented Nov 12, 2011 at 18:44
Add a comment
|
4 Answers
Horribly inefficient - but:
Stack 1 Contains the details Stack 2 is empty.
To go through the array, Pop Stack 1 , when you want the next one, push the previous one into stack 2 and pop stack 1 again. Repeat until 'isempty'.
If you want the Nth value, pop the not empty stack N times while pushing the unneeded ones into the other stack. Then when you're done playing with it, empty it into the other stack. Note that this;ll flip the order.
Comments
With two stacks you can get some sort of random access (which is what you're interested in an array) like this:
- Put everything on a stack.
- Every time you have to access something that's not the top of the stack (pop), you pop all elements from this stack and push them in order to the second one.
By passing elements from one stack to another you simulate iteration.
1 Comment
leo
Sure, I completely agree with you, but I don't think it was the point of the question (in that case, the answer would be 'impossible').
First element of array is a bottom of stack1;
Last element of array is a bottom of stack2;
Current element of array is a top of stack1;
Iterates through the array by shifting the elements of the stack1 to stack2(move to the begin) and vice versa (move to end).
Comments
#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;
}
