写点什么

精选算法面试 - 队列

用户头像
李孟
关注
发布于: 2021 年 01 月 11 日
精选算法面试-队列

一.简介

队列是一种特殊的线性表,它只允许在表的前端进行删除操作,而在表的后端进行插入操作。

LinkedList 类实现了 Queue 接口,因此我们可以把 LinkedList 当成 Queue 来用。

二.示例

2.1 用队列实现栈

使用队列实现栈的下列操作

  • push(x) -- 元素 x 入栈

  • pop() -- 移除栈顶元素

  • top() -- 获取栈顶元素

  • empty() -- 返回栈是否为空

注意

  • 你只能使用队列的基本操作-- 也就是 push to back, peek/pop from front, size, 和 is empty 这些操作是合法的。

  • 你所使用的语言也许不支持队列。 你可以使用 list 或者 deque(双端队列)来模拟一个队列 , 只要是标准的队列操作即可。

  • 你可以假设所有操作都是有效的(例如, 对一个空的栈不会调用 pop 或者 top 操作)。

第一种

public class MyQueue {    Queue<Integer> s1= new LinkedList<>();    Queue<Integer> s2= new LinkedList<>();    public MyQueue() {    }    /**     * 将元素x推导队列的末尾     * @param x     */    public void  push(int x){        while (!s1.isEmpty()){            s2.offer(s1.poll());        }        s1.offer(x);        while (!s2.isEmpty()){            s1.offer(s2.poll());        }    }    /**     * 从队列的开头移除并返回元素     * @return     */    public int pop(){        return s1.poll();    }    /**     * 返回队列开头元素     * @return     */    public int peek(){        return s1.peek();    }    /**     * 如果队列为空,返回true ,否则 false     * @return     */    public boolean empty(){        return !s1.isEmpty() && !s2.isEmpty();    }}
复制代码

第二种方法

public class MyQueue {Queue<Integer> s1= new LinkedList<>();public void  push(int x){    //移多少位    int size = s1.size();    //根据遍历,每次把前面的结点,放到后面,留有一个头结点    //留有一个头结点    s1.offer(x);    for (int i = 0; i < size; i++) {      s1.offer(s1.poll());    }}public int pop(){return s1.poll();}public int peek(){return s1.peek();}public boolean empty(){return s1.isEmpty();}}
复制代码


发布于: 2021 年 01 月 11 日阅读数: 19
用户头像

李孟

关注

还未添加个人签名 2017.10.18 加入

数据工程师 https://limeng.blog.csdn.net/

评论

发布
暂无评论
精选算法面试-队列