面试题 7

1 题目描述

用两个栈实现一个队列，队列的声明如下，请事先它的两个函数，appendTail 和 deleteHead 分别完成从队列尾部插入节点和在对头部删除节点的功能。

2 算法描述

appendTail：元素进队时，直接入栈 Stack1
deleteHead : 若此时 Stack2 不为空，那么直接将 Stack2 栈顶元素出栈。若Stack2 为空，那么将 Stack1 中的元素依次出栈，然后在依次入栈 Stack2 ,最后将 Stack2 栈顶元素出栈。

C 语言实现

#include<stdio.h>
typedef int ElemType;
typedef struct node{
    ElemType data;
    struct node* next;
}SNode,*Stack;

void initStack(Stack *stack){
    //初始化头结点
    (*stack)=(SNode*)malloc(sizeof(SNode));
    (*stack)->data=-1;
    (*stack)->next=NULL;
}
//所有操作都在表头进行,头插法
int push(Stack stack,ElemType data){
    SNode *push;
    //如果Stack尚未初始化
    if(stack==NULL) return 0;
    push=(SNode*)malloc(sizeof(SNode));
    push->data=data;
    push->next=stack->next;
    stack->next=push;
}
//出栈
int pop(Stack stack,ElemType* popVlaue){
    //如果Stack为空
    if(isEmpty(stack)) return 0;
    SNode *pop=stack->next;
    *popVlaue=pop->data;
    stack->next=pop->next;
    free(pop);
    return 1;
}
//获得栈顶元素
int getTop(Stack stack,ElemType* topVlaue){
    //如果Stack为空
    if(isEmpty(stack)) return 0;
    *topVlaue=stack->next->data;
    return 1;
}

//判断是否为空
int isEmpty(Stack stack){
    return stack!=NULL&&stack->next==NULL?1:0;
}

//遍历Stack
void showStack(Stack stack){
    if(isEmpty(stack)) return;
    SNode* temp=stack->next;
    printf("----- stack elements:");
    while(temp!=NULL){
        printf(" %d",temp->data);
        temp=temp->next;
    }
}
//appendTail
void appendTail(Stack s1,ElemType e){
    push(s1,e);
}

//deleteHead
void deleteHead(Stack s1,Stack s2,ElemType* e){
    if(isEmpty(s2)){
        while(!isEmpty(s1)){
            ElemType temp;
            pop(s1,&temp);
            push(s2,temp);
        }
    }
    if(isEmpty(s2)){
        printf("queue is empty");
    }else{
        pop(s2,e);
    }
}

void main(){
    Stack stack1=NULL;
    Stack stack2=NULL;
    initStack(&stack1);
    initStack(&stack2);

    appendTail(stack1,1);
    appendTail(stack1,2);
    appendTail(stack1,3);
    appendTail(stack1,4);
    appendTail(stack1,5);
    appendTail(stack1,6);

    int _delete;
    deleteHead(stack1,stack2,&_delete);
    deleteHead(stack1,stack2,&_delete);
    deleteHead(stack1,stack2,&_delete);
    deleteHead(stack1,stack2,&_delete);

    appendTail(stack1,7);
    appendTail(stack1,8);

    showStack(stack1);
    printf("\n");
    showStack(stack2);
}