剑指offer第9题--栈实现队列

左手的ㄟ右手 2021-11-11 10:36 236阅读 0赞

思路(书中标准解法：用两个队列实现一个栈）：  
（1）对于插入操作，栈与队列都是从队尾进行，因此很容易完成。  
（2）对于弹出操作，队列从队头开始，而栈从队尾开始，要想取到队尾元素，需要第二个队列的协助：假设queue1不为空，queue2为空，将queue1的原书依次取出放到queue2中，同时判断，当queue1的长度为1时，不要将该元素放到queue2中，而是直接取出丢弃，此时即完成了栈的弹出操作。也就是说，弹出一个元素，其他元素的存储位置就会从本队列移动到另一个队列中。  
总结下，运作过程中，queue，queue2一定至少一个为空。插入操作选择queue1，queue2中不为空的那个队列插入（如果都为空，随意选择一个），弹出时将不为空的队列除最后一个队列的其他元素依次取出放到另一个队列中，而将最后那一个元素取出丢弃即可。

--------------------

另种思路，仅供参考（C++代码如下）

1. 至少用两个栈  
2. 插入操作，直接入栈1；删除操作，把入栈1的数据依次弹出并且入栈2， 栈2的栈顶就是目标元素  
3. 栈1在弹出时，应该是弹到目标元素，停止出栈，栈2在接收到目标元素后，再把栈内已存放的数据再压回栈1  
4. 始终保证栈1每次都是只删除目标元素，栈2为空，其他数据以及位置不变

#include <iostream>
    using namespace std;
     
    const int MAX=100;
    typedef char Type;  //这样更安全，用户看不到内部数据类型 ，程序提供的是接口  
    struct stack{
    	int length;
    	char* base;
    	Type* top;
    }; 
    
    void push(stack &s1,char elem) 
    {
    	if(s1.length==MAX)
         {
         	cout<<"栈满";
    		exit(-1); 
    	 }
    	 else  //入栈 
    	 {
    	 	*(s1.top)=elem;  
    	 	s1.top++;
    	 	s1.length++;
    	 
    	 }
     } 
     
    void Print(const stack s) 
    {
      cout<<"长度"<<s.length<<"栈顶"<<*(s.top-1)<<"栈底"<<*(s.base)<<endl; //栈顶始终是指向元素的下一个位置 
      int i=1;
      while(i<=s.length)
      {
      	cout<<*(s.top-i)<<" ";   
      	i++;
      }
      cout<<"\n";   
    }
    
    void pop(stack &s1,stack &s2,char elem)
    {
    	while(*(s1.top-1)!=elem)  //一直找到目标 
    	{
    		*(s2.top)=*(s1.top-1);  //栈1的值倒入栈2
    		s1.top--;
    		s1.length--;
    		s2.top++;
    		s2.length++;         
    	    if(s1.top==s1.base)  //防止越界
    		{
    		  if(*(s1.top)!=elem) 
    		   { cout<<"找不到"<<endl; 
    		     exit(0); 
    		   } 
    		  else
    		    break;   
    		}
    		
    	}
    	cout<<"目标\t"<<*(s1.top-1)<<endl;   
    	s1.top--;     
    	s1.length--; 
    	
    	//再把栈2的值倒回栈1
    	while(s2.top!=s2.base)  
    	{
    	*(s1.top)=*(s2.top-1);  
    	s1.top++;
    	s1.length++;
    	s2.top--;
    	s2.length--;
    	} 
    	
    	//此时s2.top里还剩一个数字
    	if(s2.top==s2.base) 
    	{
    	*(s1.top)=*(s2.top);
    	s1.top++;
    	*(s2.top)='\0';  //或者 '空格' ，如果再s2.top-- 就野指针了 
    	}
    }
    
    int main() 
    {   //栈初始化
        stack s1,s2;
    	s1.base=new char(MAX);  
    	s2.base=new char(MAX);
    	s1.top=s1.base,s2.top=s2.base;
    	s1.length=0,s2.length=0;
    	
        //自定义队列内容
        int i=1; 
        char c;
    	while(i<10)
    	{	cout<<"enter char"<<endl;
    	    cin>>c;
    		push(s1,c); 
    		i++;
    	}  
    	Print(s1);
        pop(s1,s2,'b'); 
        Print(s1);
        Print(s2); 
        return 0;
     }