精选算法面试 - 队列

李孟

关注

发布于: 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

原文链接:【http://xie.infoq.cn/article/a9f2a863593f7f20b57da7f28】。文章转载请联系作者。

李孟

关注

还未添加个人签名 2017.10.18 加入

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

发布

暂无评论

创作场景

精选算法面试 - 队列

一.简介

二.示例

2.1 用队列实现栈

李孟

评论