专栏首页老沙课堂数据结构与算法(五) 队列

数据结构与算法(五) 队列

队列

队列 (Queue)

定义

队列是一种特殊的线性表(只能操作队头front 和 队尾rear)

•先进先出原则(First In First Out) FIFO•队尾(rear):只能进行入队操作(enQueue)->添加元素•队头(front):只能进行出队(deQueue) ->取出元素•一般底层由双链表来实现

队列简介

接口设计

int size();//大小
boolean isEmpty(); //是否为空
void enQueue(element); //入队
E deQueue();//出队
E front();// 最前面元素
void clear();//清空

双端队列 (DeQue) Double Ended Queue

定义

•双端队列是能在头尾两端都可以添加和删除的队列 •一般底层由双链表来实现

双端队列

接口设计

int size();//大小
boolean isEmpty(); //是否为空
void enQueueFront(element); //从队头入队
void enQueueRear(element); //从队尾入队
void deQueueFront(element); //从队头出队
void deQueueRear(element); //从队尾出队
E deQueue();//出队
E front();// 最前面元素
void clear();//清空

循环队列(Circle Queue)

•底层一般由数组实现•扩容问题

1、原理

循环队列原理

2、扩容问题

循环队列扩容

双端循环队列

类似于动态数组,只是在动态数组的基础上缺少插入的操作。

用栈实现队列 (leetCode 232)

题目

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

push(x) -- 将一个元素放入队列的尾部。pop() -- 从队列首部移除元素。peek() -- 返回队列首部的元素。empty() -- 返回队列是否为空。示例:

MyQueue queue = new MyQueue();

queue.push(1); queue.push(2); queue.peek(); // 返回 1 queue.pop(); // 返回 1 queue.empty(); // 返回 false 说明:

你只能使用标准的栈操作 -- 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。你所使用的语言也许不支持栈。你可以使用 list 或者 deque(双端队列)来模拟一个栈,只要是标准的栈操作即可。假设所有操作都是有效的 (例如,一个空的队列不会调用 pop 或者 peek 操作)。

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/implement-queue-using-stacks 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

思路

inStack 和 outStack

•入队时候push到 inStack•出队的时候•如果outStack为空 将所有inStack 进行pop 并push到outStack中, 再将outStack栈顶元素pop•如果outStack不为空 直接将outStack栈顶元素pop

代码

public class MyQueue {

    private Stack<Integer> inStack;
    private Stack<Integer> outStack;

    public MyQueue() {
        inStack = new Stack<>();
        outStack = new Stack<>();
    }

    /** Push element x to the back of queue. */
    public void push(int x) {
        inStack.push(x);
    }

    /** Removes the element from in front of queue and returns that element. */
    public int pop() {
        cheackOutStack();
        return outStack.pop();
    }

    /** Get the front element. */
    public int peek() {
        cheackOutStack();
        return outStack.peek();
    }

    /** Returns whether the queue is empty. */
    public boolean empty() {
        return outStack.empty() && inStack.empty();
    }

    void cheackOutStack() {
        if (outStack.empty()) {
            while (!inStack.empty()) {
                outStack.push(inStack.pop());
            }
        }
    }
}

本文分享自微信公众号 - 老沙课堂(gh_f73a6b772d4f),作者:沙睿

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-10-08

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 据结构与算法(八) 二叉树的练习

    •设定levelSize初始值为1(只有一个根节点)•当进行while循环的时候 levelsize-- 操作。因为levelSize和每层节点个数相等。所以当...

    老沙
  • iOS读写安全

    给属性添加atomic 可以保证属性的setter和getter原子性操作,也就是保证setter和getter内部是线程同步的

    老沙
  • 数据结构与算法(六) 二叉树遍历

    •任意一个节点的值都大于其左子树的值•任意一个节点的值都小于其右子树的值•他的左右子树也是一颗二叉搜索树•二叉搜索树可以大大提高效率(搜索和添加删除时间复杂度都...

    老沙
  • 并发编程之阻塞队列

    爱撒谎的男孩
  • java中的阻塞队列

    阻塞队列(BlockingQueue)是一个支持两个附加操作的队列。这两个附加的操作是:在队列为空时,获取元素的线程会等待队列变为非空。当队列满时,存储元素的线...

    用户1637228
  • Java并发编程(六)阻塞队列

    前言 在 Android多线程(一)线程池这篇文章时,当我们要创建ThreadPoolExecutor的时候需要传进来一个类型为BlockingQueue的参数...

    用户1269200
  • 【原创】Java并发编程系列31 | 阻塞队列(上)

    阻塞队列在并发编程非常常用,被广泛使用在“生产者-消费者”问题中。接下来两篇文章就来详细介绍阻塞队列。本文是阻塞队列上篇。

    java进阶架构师
  • Java阻塞队列

    ?原文地址为https://www.cnblogs.com/haixiang/p/12354520.html,转载请注明出处!

    海向
  • Java之BlockingQueue

    public interface BlockingQueue<E> extends Queue<E> {

    用户7886150
  • Java并发编程之阻塞队列

    使用非阻塞队列的时候有一个很大问题就是:它不会对当前线程产生阻塞,那么在面对类似消费者-生产者的模型时,就必须额外地实现同步策略以及线程间唤醒策略,这个实现起来...

    黄泽杰

扫码关注云+社区

领取腾讯云代金券