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

短命女 2021-11-10 23:46 321阅读 0赞

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

push(x) – 元素 x 入栈  
  pop() – 移除栈顶元素  
  top() – 获取栈顶元素  
  empty() – 返回栈是否为空  
**注意:**

1.你只能使用队列的基本操作-- 也就是 push to back, peek/pop from front, size, 和 is empty 这些操作是合法的。  
  2.你所使用的语言也许不支持队列。 你可以使用 list 或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。  
  3.你可以假设所有操作都是有效的（例如, 对一个空的栈不会调用 pop 或者 top 操作）。  
**解决方案一：** 用普通队列实现栈  
**思路：** 主要讲两个函数，其他两个比较简单，没什么技术含量。**1.** 实现栈的 pop() 函数，删除栈顶元素：做一个循环把栈顶下面两个元素用首先用队列的 front() 把队头取出来，再用队列 push() 函数插到栈顶后面，再用队列 pop() 函数把取出来的元素的位置清空，即出队列，一个循环之后，之前要删除的栈顶元素变成了队头元素，再用队列 pop() 函数，把队头元素删除，即 删除之前要删除的栈顶元素。  
**2.** 用普通队列实现栈的 top() 函数，即获得栈顶元素的值： 做一个循环把栈顶下面两个元素用首先用队列的 front() 把队头取出来，再用队列 push() 函数插到栈顶后面，再用队列 pop() 函数把取出来的元素的位置清空，即出队列，一个循环之后，之前要获得值的栈顶元素变成了队头元素，用队列的 front() 函数获得该值，再用队列 push() 把改值插到栈顶，用 队列 pop() 函数把 改值从队头删除，即不改变原栈的结构。**详情看代码**  
**代码：**

class MyStack { 
            
       private:
     		// 常规队列实现 
     		queue<int> elements;
     		int temp;
        public:
            /** Initialize your data structure here. */
            MyStack() { 
    
            }
    
            /** Push element x onto stack. */
            void push(int x) { 
            	elements.push(x);       	
            }
    
            /** Removes the element on top of the stack and returns that element. */
            int pop() { 
            	// 移除栈顶元素
            	//int temp; 
            	// 获得队列尾元素 
            	for(int i = 0; i < elements.size() - 1; i++){ 
            		// 获取队头元素 
            		 temp = elements.front();
            		//把队头元素插到队尾 
            		elements.push(temp);
                    // 队头出队列
            		elements.pop(); 
    			} 
    			// temp 现在为队头元素，(实际上就是需要移除的栈顶元素) 
    			temp = elements.front();
    			// 用队列 pop()删除队头元素 (实际上就是需要移除的栈顶元素) 
            	elements.pop();
    			return temp; 
            }
    
            /** Get the top element. */
            int top() {         	
            	for(int i = 0; i < elements.size() - 1; i++){        		  
            		// 获取队头元素 
            		 temp = elements.front();
            		//把队头元素插到队尾 
            		elements.push(temp);
                    // 队头出队列
            		elements.pop(); 
    			} 
    			// temp 现在为队头元素，(实际上就是需要获得的栈顶元素) 
    			temp = elements.front(); 
            	// 用队列 pop()删除队头元素 (实际上就是需要获得的栈顶元素) 
            	elements.pop();
            	elements.push(temp); 
            	return temp; 
    
            }
    
            /** Returns whether the stack is empty. */
            bool empty() { 
            	// 队列为空则所表示栈为空，不为空则栈也不为空 
            	return elements.empty();
            }
    };

**解决方案二：** 用双端循环队列实现栈  
**思路：** 用双端循环队列实现栈思路很简单，看代码及注释即可。双端循环队列详情可参考我另一篇博客：[从零开始算法之路 ---- 设计循环双端队列][----]  
**代码:**

class MyStack { 
            
       private:
     		deque<int> elements;
    	 	 
        
        
        public:
            /** Initialize your data structure here. */
            MyStack() { 
    
            }
    
            /** Push element x onto stack. */
            void push(int x) { 
                //用双端循环队列的 push_back(x) 函数元素从队尾进队列
            	elements.push_back(x);       	
            }
    
            /** Removes the element on top of the stack and returns that element. */
            int pop() { 
            	// 移除栈顶元素
            	// // 用双端循环队列back() 函数获得栈顶元素 
            	int temp = elements.back();
                // 用双端循环队列的 pop_back() 函数移除栈顶元素
                // 用双端循环队列的 pop_back() 在队列中的作用就是移除队尾元素
            	elements.pop_back();
    			return temp; 
    
            }
    
            /** Get the top element. */
            int top() { 
            	// 用双端循环队列的 back() 函数获得栈顶元素 
            	return elements.back(); 
    
            }
    
            /** Returns whether the stack is empty. */
            bool empty() { 
            	// 队列为空则所表示栈为空，不为空则栈也不为空 
            	return elements.empty();
            }
    };
    
    /** * Your MyStack object will be instantiated and called as such: * MyStack* obj = new MyStack(); * obj->push(x); * int param_2 = obj->pop(); * int param_3 = obj->top(); * bool param_4 = obj->empty(); */

[https_leetcode-cn.com_problems_implement-stack-using-queues]: https://leetcode-cn.com/problems/implement-stack-using-queues/
[----]: https://blog.csdn.net/weixin_40916641/article/details/97959736