分类： C/C++
2013-11-18 20:59:15
使用一个数组实现栈，很容易。
使用一个数组实现两个栈，也容易想到，使用两端来构造两个栈。
若是使用一个数组来实现三个栈呢。你可能还会想，两端可以构造两个栈。那么在中间某处在开辟一处不就可以
实现三个栈了。
但是这样做的弊端是你需要知道这三个栈的预期大小才能 合理的找到这个中间点来实现第三个栈的位置。但往往栈的使用情况
是不能预期的。
更一般的如果我想在一个数组中实现多个栈呢，比如4个5个``` 个栈呢。那么如何在中间找位置来确定其他栈的位置就显得
更加困难。
为了解决上面的问题，我们来构造下面这种可行的方案，
使用三个指针分别来指向三个栈的栈顶。因为存在三个栈，所以这就导致
一个栈（比如 A 栈，）的栈顶指针并不是指向下一个元素入（人A栈）栈的位置。所以我们需要一个指针指向当下一个入栈的位置（不论是入哪个栈），
对于出栈，我们需要出栈后栈顶指针需要指向哪个位置，所以对于每个元素我们需要有一个域来记录他上一个入栈元素的位置.
我们还需要一个标志符 来标志说明时候栈空.
数组的大小可用用来标志栈慢.
但是需要注意的是,一个栈空了,其他栈不一定空.但是一个栈满了,就等于其他栈也满了(因为数组已经被填满，没有位置在放别的元素了)
下面给出具体的实现代码
Head.h文件
#ifndef HEAD_H_
#define HEAD_H_
typedef int TYPE;
#define FORMAT "%d "
#define STACK_FIRST (0) //第一个栈
#define STACK_SECOND (1) //第二个栈
#define STACK_THIRD (2) //第三个栈
struct stack;
typedef struct stack *STACK;
/*
初始化栈，用数组构建，所以需要声明大小
*/
void init_stack(STACK *s,unsigned int size);
//which 指定操作作用于哪个栈
void push(TYPE key,STACK s,int which);
TYPE pop(STACK s,int which);
void print_stack(STACK stack);//打印数组，即打印三个栈,按出栈顺序打印
#endif
Head.c文件
#include
#include
#include"head.h"
#define STACK_BOTTOM (-1) //栈底索引值(出栈越界标志)
#define INDEX int //索引值，用来指示该元素在所属栈中的下一个元素(按出栈顺序的下一个)
struct node{
TYPE key;
INDEX next;
};
struct stack{
int first_top; //第一个栈的栈顶指针
int second_top; //第二个栈的栈顶指针
int third_top; //第三个栈的栈顶指针
unsigned int stack_size; //数组的大小，即栈的总大小
unsigned int current_size; //当前数组的大小，用来指示下一个入栈关键字的位置
struct node *array;
};
static int is_fully(STACK s);
static int is_empty(STACK s,int which);
void init_stack(STACK *s ,unsigned int size ){
(*s) = (STACK)malloc(sizeof(struct stack));
(*s)->first_top = STACK_BOTTOM; //初始化，三个栈的栈顶指针都应指向公共的栈底（准确的说是界限标志）
(*s)->second_top = STACK_BOTTOM;
(*s)->third_top = STACK_BOTTOM;
(*s)->stack_size = size;
(*s)->current_size = 0; //初始化后的第一次入栈位置（无论哪一个栈的入栈)
(*s)->array = (struct node *)malloc(sizeof(struct node)*size); //创建数组
}
void push(TYPE key,STACK stack,int which){
if(is_fully(stack)){
printf("stack is full!\n");
exit(1);
}else{
unsigned int insert_position = stack->current_size; //找到当前入栈元素入栈的位置
stack->array[insert_position].key = key;
switch(which){
case STACK_FIRST:
stack->array[insert_position].next = stack->first_top; //设置最新入栈的元素的上一个一个元素位置为之前的栈顶
stack->first_top = insert_position; //更新当前这个栈的栈顶指针
break;
case STACK_SECOND:
stack->array[insert_position].next = stack->second_top;
stack->second_top = insert_position;
break;
case STACK_THIRD:
stack->array[insert_position].next = stack->third_top;
stack->third_top = insert_position;
break;
}
stack->current_size++; //跟新，当前栈的大小，也就是下一个入栈元素(无论入哪一个栈)的入栈位置
}
}
TYPE pop(STACK s,int which){
if(is_empty(s,which)){
printf("stack is empty\n");
exit(1);
}
int top;
switch(which){
case STACK_FIRST:
top = s->first_top; //或得栈顶元素的位置
s->first_top = s->array[top].next; //出栈后需要跟新栈顶指针
break;
case STACK_SECOND:
top = s->second_top;
s->second_top = s->array[top].next;
break;
case STACK_THIRD:
top = s->third_top;
s->third_top = s->array[top].next;
break;
}
return s->array[top].key;
}
static int is_fully(STACK s){ //因为三个栈用同一个数组，所以只要一个满了，另外两个也就等于满了
return s->current_size == s->stack_size;
}
static int is_empty(STACK s,int which){ //一个栈空时，其他栈不一定空。所以需要指示判断哪个栈
switch(which){
case STACK_FIRST:
return s->first_top == STACK_BOTTOM;
case STACK_SECOND:
return s->second_top == STACK_BOTTOM;
case STACK_THIRD:
return s->third_top == STACK_BOTTOM;
}
printf("parameter error\n");
exit(1);
}
static void print_one_stack(STACK stack,unsigned int top,int end){ //打印数组中的某个栈
while(top != end){
printf("(%d)"FORMAT,top,stack->array[top].key);
top = stack->array[top].next;
}
}
void print_stack(STACK stack){ //打印三个栈
int top = stack->first_top;
int end = STACK_BOTTOM;
printf(" FIRST STACK: ");
print_one_stack(stack,top,end);
printf("\n");
printf(" SECOND STACK: ");
top = stack->second_top;
print_one_stack(stack,top,end);
printf("\n");
printf("THIRD STACK : ");
top = stack->third_top;
print_one_stack(stack,top,end);
printf("\n");
printf("\n");
}
测试代码如下
Main.c
#include
#include
#include
#include"head.h"
#define ARRAY_SIZE 50
int main(void){
srand((unsigned int)time(0));
int which;
STACK stack;
init_stack(&stack,ARRAY_SIZE);
for(int i=0;i<50;i++){
which=rand()%3;
switch(which){
case STACK_FIRST: printf("push to first stack\n");break;
case STACK_SECOND: printf("push to second stack\n");break;
case STACK_THIRD: printf("push to third stack\n");break;
}
push(rand()%100,stack,which);
print_stack(stack);
}
for(int j=0;j<50;j++){
which=rand()%3;
switch(which){
case STACK_FIRST: printf("pop from first stack\n");break;
case STACK_SECOND: printf("pop from second stack\n");break;
case STACK_THIRD: printf("pop from third stack\n");break;
}
pop(stack,which);
print_stack(stack);
}
return 0;
}
