剑指offer之面试题7用两个栈实现一个队列

ゝ一纸荒年。 2022-08-22 01:30 105阅读 0赞

**问题描述**：

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

**实现代码**如下：

#include<stdio.h>
    #include<stdlib.h>
    #include<stdbool.h>
    
    struct Stack
    {
    	int mData[100];
    	int mLen;
    };
    typedef struct Stack Stack; 
    //初始化栈
    void InitStack(Stack *S)
    {
    	S->mLen = 0;
    }
    //元素进栈
    void Push(Stack *S,int item)
    {
    	S->mData[S->mLen++] = item;
    }
    //删除栈顶元素
    int Pop(Stack *S)
    {
    	S->mLen--;
    	return S->mData[S->mLen];
    }
    //返回栈顶元素
    int  Peek(Stack *S)
    {
    	return S->mData[S->mLen-1];
    }
    //判断栈是否为空
    bool EmptyStack(Stack *S)
    {
    	if(S->mLen == 0) return true;
    	return false;
    }
    //清空栈
    void Clear(Stack *S)
    {
    	int i = 0;
    	for(;i<S->mLen;++i)
    	{
    		Pop(S);
    	}
    }
    struct Queue{
    	Stack *S1;
    	Stack *S2;
    };
    typedef struct Queue Queue;
    void InitQueue(Queue *Q){
    	Q->S1=(Stack *)malloc(sizeof(Stack));
    	Q->S2=(Stack *)malloc(sizeof(Stack));
    	InitStack(Q->S1);
    	InitStack(Q->S2);
    }
    void appendTail(Queue *Q,int element){
    		Push(Q->S1,element);
    		return ;
    }
    int deleteHead(Queue *Q){
    	if(EmptyStack(Q->S2)){
    		while(!EmptyStack(Q->S1)){
    			Push(Q->S2,Pop(Q->S1));
    		}
    	}
    	if(!EmptyStack(Q->S2)){
    		return Pop(Q->S2);
    	}
    	
    }
    
    int main(){
    	Queue *Q=(struct Queue *)malloc(sizeof(struct Queue));
    	InitQueue(Q);
    	int i=0;
    	for(;i<40;i++){
    		appendTail(Q,i);	
    	}
    	for(i=0;i<40;i++){
    		printf("%d\n",deleteHead(Q));	
    	}
    	return 0;
    }

添加结点的时间复杂度为O(1)。

删除结点的时间复杂度为O(1)。

**参考资料**：  
剑指offer  
  
**备注**：  
转载请注明出处：http://blog.csdn.net/wsyw126/article/details/51366802  
**作者**：WSYW126