Day20——队列和栈专题

女爷i 2024-04-01 11:08 117阅读 0赞

#### 文章目录 ####

*   *  栈和队列专题
     *   *  1.用栈实现队列
         *  2.用队列实现栈

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

### 栈和队列专题 ###

**栈：先进后出**,是只允许在一端进行插入或删除的线性表。首先栈是一种线性表，但限定这种线性表只能在某一端进行插入和删除操作。

**队列：先进先出**,是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。

#### 1.用栈实现队列 ####

**`java`中栈的方法**

判空: empty()  
添加元素: push  
弹出栈顶元素: pop()  
获取栈顶元素: peek()

\*\*思路：\*\*队列是先进先出，而栈是先进后出，我们可以通过两个栈来模拟队列。

*  将所有元素放入入栈中
 *  将入栈中的所有元素弹出，压入出栈中，此时出栈的出栈顺序即达到了模拟队列的效果（先进先出）

**代码实现：**

class MyQueue {
        
        Stack<Integer> stackIn;
        Stack<Integer> stackOut;
        public MyQueue() {
        
            stackIn = new Stack<>();
            stackOut = new Stack<>();
        }
        
        public void push(int x) {
        
            stackIn.push(x);
        }
        
        public int pop() {
        
            dumpstackIn();
            return stackOut.pop();
        }
        
        public int peek() {
        
            dumpstackIn();
            return stackOut.peek();
        }
        
        public boolean empty() {
        
            return stackIn.isEmpty()&&stackOut.isEmpty();
        }
         private void dumpstackIn(){
        
             if(stackOut.isEmpty()){
        
                 while(!stackIn.isEmpty()){
        
                     stackOut.push(stackIn.pop());
                 }
             }
         }
    }

#### 2.用队列实现栈 ####

**`java`中队列的方法:**

判空: `isEmpty()`  
添加元素: offer()  
弹出栈顶元素 poll()  
获取栈顶元素 peek()

**思路**：一个队列在模拟栈弹出元素的时候只要将队列头部的元素（除了最后一个元素外） 重新添加到队列尾部，此时在去弹出元素就是栈的顺序。

**代码实现：**

class MyStack {
        
    
        Queue<Integer> queue;
    
        public MyStack() {
        
            queue = new LinkedList<>();
        }
    
        //每 offer 一个数（A）进来，都重新排列，把这个数（A）放到队列的队首
        public void push(int x) {
        
            queue.offer(x);
            int size = queue.size()-1;
            //移动除了 A 的其它数
            while (size-- > 0)
                queue.offer(queue.poll());
        }
    
        public int pop() {
        
            return queue.poll();
        }
    
        public int top() {
        
            return queue.peek();
        }
    
        public boolean empty() {
        
            return queue.isEmpty();
        }
    }