【剑指offer】-两个栈来实现一个队列-05/67

待我称王封你为后i 2023-07-13 03:53 1阅读 0赞

### 一只持续努力、梦想进大厂的程序猿 ###

*  一 题目描述
 *  二 题目分析
 *   *  （一）题目思路
     *  （二）栈和队列的解释
     *  （三）队列和栈的规则
     *  （四）队列和栈的遍历数据速度
     *  （五）Java和C++中栈和队列的区别
     *   *  1 Java栈和队列
         *   *  1.1 栈的创建方法（Stack）
             *  1.2 Stack类中的方法
             *  1.3. 队列的创建方法（Queue）
             *  1.4. Queue类中的方法\*\*
         *  2 C++栈和队列
         *   *  2.1. 栈的创建方法（Stack）
             *  2.2 Stack类中的方法
             *  2.3 队列的创建方法（Queue）
             *  2.4 Queue类中的方法
 *  三 题目代码
 *   *  （一）Java版本
     *  （二）C++版本
 *  四 随笔

# 一 题目描述 #

用两个栈来实现一个队列，完成队列的Push和Pop操作( 队列中的元素为int类型)。

# 二 题目分析 #

## （一）题目思路 ##

1.  用两个栈实现一个队列的功能?  
    入队：将元素进栈A  
    出队：判断栈B是否为空，如果为空，则将栈A中所有元素pop，并push进栈B，栈B出栈；如果不为空，栈B直接出栈。
2.  用两个队列实现一个栈的功能?  
    入栈：将元素进队列A  
    出栈：判断队列A中元素的个数是否为1，如果等于1，则出队列，否则将队列A中的元素 以此出队列并放入队列B，直到队列A中的元素留下一个，然后队列A出队列，再把 队列B中的元素出队列以此放入队列A中。

## （二）栈和队列的解释 ##

1.  队列（Queue）：是限定只能在表的一端进行插入和另一端删除操作的线性表
2.  栈（Stack）：是限定只能在表的一端进行插入和删除操作的线性表

## （三）队列和栈的规则 ##

1.  **队列：先进先出**
2.  **栈：先进后出**

## （四）队列和栈的遍历数据速度 ##

1.  队列：基于**地址指针**进行遍历，而且可以从**头部或者尾部**进行遍历，但**不能同时遍历**，无需开辟空间，因为在遍历的过程中不影响数据结构，所以遍历速度要快
2.  栈：只能从**顶部取数据**，也就是说最先进入栈底的，需要遍历整个栈才能取出来，遍历数据时需要为数据开辟临时空间，保持数据在遍历前的一致性

## （五）Java和C++中栈和队列的区别 ##

### 1 Java栈和队列 ###

#### 1.1 栈的创建方法（Stack） ####

*  创建方法： `Stack<Integer> stack1 = new Stack<Integer>();`

#### 1.2 Stack类中的方法 ####

Object push（Object element）：将元素推送到堆栈顶部。
    Object pop（）：移除并返回堆栈的顶部元素。如果我们在调用堆栈为空时调用pop（）,则抛出’EmptyStackException’异常。
    Object peek（）：返回堆栈顶部的元素，但不删除它。
    boolean empty（）：如果堆栈顶部没有任何内容，则返回true。否则，返回false。
    int search（Object element）：确定对象是否存在于堆栈中。如果找到该元素，它将从堆栈顶部返回元素的位置。否则，它返回-1。
    Object size() : 代表栈中含有多少个元素

#### 1.3. 队列的创建方法（Queue） ####

*  创建方法： `Queue<Integer> queue = new LinkedList<>();`

#### 1.4. Queue类中的方法\*\* ####

offer(element: E): boolean     插入一个元素到队列中
    poll(): E                      获取并移除队列的头元素，如果队列空则返回null
    remove(): E                    获取并移除队列头元素，如果队列空则抛出异常
    peek(): E                      获取但不移除队列头元素，如果队列为空则返回null
    element(): E                   获取但不移除队列头元素，如果队列为空则抛出异常

### 2 C++栈和队列 ###

#### 2.1. 栈的创建方法（Stack） ####

*  创建方法： `stack<int> stack1;`

#### 2.2 Stack类中的方法 ####

push(): 向栈内压入一个成员；
    pop(): 从栈顶弹出一个成员；
    empty(): 如果栈为空返回true，否则返回false；
    top(): 返回栈顶，但不删除成员；
    size(): 返回栈内元素的大小；

#### 2.3 队列的创建方法（Queue） ####

*  创建方法： `queue<int> q;`

#### 2.4 Queue类中的方法 ####

入队：q.push(x); 将x 接到队列的末端。
    出队：q.pop(); 弹出队列的第一个元素，注意，并不会返回被弹出元素的值。
    访问队首元素：q.front()，即最早被压入队列的元素。
    访问队尾元素：q.back()，即最后被压入队列的元素。
    判断队列空：q.empty()，当队列空时，返回true。

# 三 题目代码 #

## （一）Java版本 ##

import java.util.Stack;
    
    public class Solution {
        
        Stack<Integer> stack1 = new Stack<Integer>();
        Stack<Integer> stack2 = new Stack<Integer>();
        
        public void push(int node){
        
             stack1.push(node);
        }
        
        public int pop(){
        
             int a;
            if(stack2.size() != 0){
        
                a = stack2.peek();
                stack2.pop();
                return a;
            }else{
        
                while(stack1.size() != 0){
        
                    a = stack1.peek();
                    stack2.push(a);
                    stack1.pop();
                }
                a = stack2.peek();
                stack2.pop();
                return a;
            }
        }
    }

## （二）C++版本 ##

class Solution
    {
        
    public:
        void push(int node) {
        
            stack1.push(node);
        }
    
        int pop() {
        
            int a;
            if(stack2.size() != 0){
        
                a = stack2.top();
                stack2.pop();
                return a;
            }else{
        
                while(stack1.size() != 0){
        
                    a = stack1.top();
                    stack2.push(a);
                    stack1.pop();
                }
                a = stack2.top();
                stack2.pop();
                return a;
            }
            
        }
    
    private:
        stack<int> stack1;
        stack<int> stack2;
    };

# 四 随笔 #

1.  要好好的从C向JAVA方向的转变，争取在开学之前完成剑指offer的第一遍刷题
2.  刷题过程中要把之间忘记的和没学过的重新学习一遍