从零开始算法之路 ---- 用栈实现队列

ゝ一世哀愁。 2021-11-11 08:10 355阅读 0赞

**前言**:小白入门题解，算法大佬可以直接跳过此博客（大佬轻喷哈）  
**题源:** 力扣(LeetCode）[https://leetcode-cn.com/problems/implement-queue-using-stacks][https_leetcode-cn.com_problems_implement-queue-using-stacks]  
**题目描述:**  
使用栈实现队列的下列操作：

push(x) – 将一个元素放入队列的尾部。  
  pop() – 从队列首部移除元素。  
  peek() – 返回队列首部的元素。  
  empty() – 返回队列是否为空。  
**示例:**

MyQueue queue = new MyQueue();  
  queue.push(1);  
  queue.push(2);  
  queue.peek(); // 返回 1  
  queue.pop(); // 返回 1  
  queue.empty(); // 返回 false  
**说明:**  
  1.你只能使用标准的栈操作 – 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。  
  2.你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。  
  3.假设所有操作都是有效的 （例如，一个空的队列不会调用 pop 或者 peek 操作）。

### 解决方案一：用栈实现 ###

**思路：** 主要讲一下队列的 pop() 和 top() 两个函数。**1.pop() 函数:** （1）先用栈的 top() 函数获得栈顶元素，再用栈顶 push() 函数把改元素插到另一个栈（辅助栈 temp）接着用栈的 pop() 函数把该元素出栈。如此往复循环直到剩下栈底元素（即需要移除的队首元素）用栈的 pop() 函数，把该元素出栈（即移除需要的队首元素）； （2）再做一个循环把辅助栈中元素重新插回到 本来的栈中。**top() 函数:** 用栈实现的队列，队列的 pop() 函数 和peek() 函数的区别：这两个函数都需要返回队首元素（即栈底元素）只是队列pop() 函数需要 调用栈的 pop() 函数把队首元素出队列而队列的 peek() 函数不需要，仅此而已。**详情看代码**  
**代码：**

class MyQueue { 
        private:
    		// 初始化一个栈用于实现队列
    		stack<int> elements; 
    		// 定义一个辅助栈 
    		stack<int> temp; 
    	
    	public:
    	    /** Initialize your data structure here. */
    	    MyQueue() { 
    	        
    	    }
    	    
    	    /** Push element x to the back of queue. */
    	    void push(int x) { 
    	    	// 无论是栈和队列，元素进入都是从尾部进入，调用 push() 函数就好 
    	    	elements.push(x);
    	        
    	    }
    	    
    	    /** Removes the element from in front of queue and returns that element. */
    	    int pop() { 
    	    	/** 思路：1.先用栈的 top() 函数获得栈顶元素，再用栈顶 push() 函数把改元素插到另一个栈（辅助栈 temp） 接着用栈的 pop() 函数把该元素出栈。如此往复循环直到剩下栈底元素（即需要移除的队首元素） 用栈的 pop() 函数，把该元素出栈（即移除需要的队首元素）； 2. 再做一个循环把辅助栈中元素 重新插回到 本来的栈中 */
    		    int score, front; 
    		    // 需要插到辅助栈中的元素个数：elements.size() - 1，剩下栈底元素（即需要移除的队首元素）
    		    int size = elements.size() - 1;		   
    	    	for(int i = 0; i < size; i++){ 
    	    		// 用栈的 top() 函数获得栈顶元素
    	    		score = elements.top();
    	    		// 用栈顶 push() 函数把改元素插到另一个栈（辅助栈 temp）
    	    		temp.push(score); 	   
    				// 用栈的 pop() 函数把该元素出栈
    				elements.pop(); 		
    			}
    			// 获取栈底元素 即需要移除的队首元素）
    			front = elements.top(); 
    			// 用栈的 pop() 函数，把栈底元素出栈（即移除需要的队首元素）
    			elements.pop();
    			//做一个循环把辅助栈中元素重新插回到 本来的栈中 
    			for(int i = 0; i < temp.size(); i++){ 
    				// 获得辅助栈栈顶元素
    				score =  temp.top();
    				// 辅助栈中元素重新插回到 本来的栈中 
    				elements.push(score);
    				// 用栈的 pop() 函数把该元素出栈
    				temp.pop();				
    			}
    		// 返回队首元素 
    		return front;	        
    	    }
    	    
    	    /** Get the front element. */
    	    /** 思路： */ 
    	    int peek() { 
    	    	int score, front; 
    	    	// 需要插到辅助栈中的元素个数：elements.size() - 1，剩下栈底元素（即需要返回的队首元素）
    	    	int size = elements.size() - 1;
    	    	for(int i = 0; i <  size; i++){ 
    	    		// 用栈的 top() 函数获得栈顶元素
    	    		score = elements.top();
    	    		// 用栈顶 push() 函数把改元素插到另一个栈（辅助栈 temp）
    	    		temp.push(score); 	   
    				// 用栈的 pop() 函数把该元素出栈
    				elements.pop(); 		
    			}
    			// 获取栈底元素 即需要移除的队首元素）
    			front = elements.top(); 
    			// 用栈实现的队列，队列的 pop() 函数 和peek() 函数的区别：这两个函数都需要返回队首元素（即栈底元素）
    			// 只是队列pop() 函数需要 调用栈的 pop() 函数把队首元素出队列而队列的 peek() 函数不需要，仅此而已。 
    			 
    			//elements.pop();
    			//做一个循环把辅助栈中元素重新插回到 本来的栈中 
    			for(int i = 0; i < temp.size(); i++){ 
    				// 获得辅助栈栈顶元素
    				score =  temp.top();
    				// 辅助栈中元素重新插回到 本来的栈中 
    				elements.push(score);
    				// 用栈的 pop() 函数把该元素出栈
    				temp.pop();				
    			}
    		// 返回队首元素 
    		return front;	        
    	        
    	    }
    	    
    	    /** Returns whether the queue is empty. */
    	    bool empty() { 
    	    	// 调用栈的 empty() 函数，判断队列是否为空
    			return  elements.empty();
    	        
    	    }
    };

### 解决方案二：用双端队列实现（有作弊嫌疑），实现很简单，详情看代码。 ###

**代码：**

class MyQueue { 
       	private:
           // 初始化一个双端队列
    		deque<int> elements;
    	
    	public:
    	    /** Initialize your data structure here. */
    	    MyQueue() { 
    	        
    	    }
    	    
    	    /** Push element x to the back of queue. */
    	    void push(int x) { 
    	    	// 调用双端队列的 push_back(x) 函数，元素从队尾进展
    	    	elements.push_back(x);
    	        
    	    }
    	    
    	    /** Removes the element from in front of queue and returns that element. */
    	    int pop() { 
    	        // 调用双端队列的 front() 函数，获取队头元素
                int score = elements.front();
                // 调用双端队列 pop_front() 函数删除队头元素
    	    	elements.pop_front();
                return score;
    	    
    	    }
    	    
    	    /** Get the front element. */
    	    int peek() { 
    	     // 调用双端队列的 front() 函数，获取队头元素
    	    return	elements.front();
    	    	
    	        
    	    }
    	    bool empty() { 
    	    	// 调用双端队列的 empty() 函数，判断队列是否为空
    			return  elements.empty();
    	        
    	    }
    };

### 解决方案三：用队列实现队列（作弊方案，不报错），实现很简单，详情看代码。 ###

**代码：**

class MyQueue { 
       		private:
            // 初始化一个队列
    		queue<int> elements;
    	
    	public:
    	    /** Initialize your data structure here. */
    	    MyQueue() { 
    	        
    	    }
    	    
    	    /** Push element x to the back of queue. */
    	    void push(int x) { 
    	    	 // 调用队列的 push(x)函数 进队列
    	    	elements.push(x);
    	        
    	    }
    	    
    	    /** Removes the element from in front of queue and returns that element. */
    	    int pop() { 
                // // 调用队列的 front() 获取队头元素
    	    	int score = elements.front();
                  // 调用队列的 pop()函数 删除队头元素
    	    	elements.pop();
    	        return score;
    	    }
    	    
    	    /** Get the front element. */
    	    /** 思路： */ 
    	    int peek() { 
                // 调用队列的 front() 获取队头元素
    	        return	elements.front();
    	    	
    	        
    	    }
    	    bool empty() { 
    	    	// 调用队列的 empty() 函数，判断队列是否为空
    			return  elements.empty();
    	        
    	    }
    };

[https_leetcode-cn.com_problems_implement-queue-using-stacks]: https://leetcode-cn.com/problems/implement-queue-using-stacks