精华内容
下载资源
问答
  • 循环队列每加入一个元素
    2022-05-11 22:02:56

    初始化循环队列、添加元素、打印循环队列

    学习队列重要的是理解如何判空、如何判断队满以及如何得出循环队列的元素个数。还应该知道为什么11个元素容量的循环队列一般只放10个元素。这些如果能够理解了,增删改查就都明白了。请看代码,我已将重要的东西注释出来了哦!!!!

    #include <stdio.h>
    #include <iostream>
    #define maxsize 10
    using namespace std;
    //利用受限顺序表来表示队列
    typedef struct queue {
    	int data[maxsize];
    	int f, r;
    };
    bool init_queue(queue* t) {
    	//初始化循环队列,首尾部对其为0位
    	t->r = 0;
    	t->f = t->r;
    	return true;
    }
    bool append(queue* t, int data) {
    	//添加元素时先判断循环队列是否满了,尾部向前一步为首则为满
    	if ((t->r + 1) % maxsize == t->f) {
    		cout << "添加失败" << endl;
    		return false;
    	}
    	//添加元素时先存数据,尾部再向前一步。
    	t->data[t->r] = data;
    	//取余的方法巧妙的避免了10到0位的溢出!!!
    	t->r = (t->r + 1) % maxsize;
    	cout << "添加成功" << endl;
    	return true;
    }
    void print(queue* t) {
    	//队列为空时首尾相等,尾指针指向的区域不存放元素。
    	if (t->f == t->r) {
    		cout << "队列为空!" << endl;
    	}
    	else {
    		int p = t->f;
    		//循环次数取自队列元素个数
    		for (int i = 0; i < (t->r - t->f + maxsize) % maxsize; i++) {
    			cout << t->data[(p + i) % maxsize] << endl;
    		}
    	}
    	return;
    }
    int main() {
    	queue q;
    	init_queue(&q);
    	bool b = true;
    	while ((q.r + 1) % maxsize != q.f) {
    		int num;
    		cout << "请输入一个数字" << endl;
    		cin >> num;
    		b = append(&q, num);
    		print(&q);
    	}
    	cout << "-----------打印最终队列元素----------" << endl;
    	print(&q);
    	return 0;
    }
    

    运行结果:

    在这里插入图片描述

    更多相关内容
  • 队列及循环队列为什么用空一个元素的位置

    千次阅读 多人点赞 2020-07-09 10:25:41
    队列,循环队列为什么用空一个元素的位置 队列介绍 1)队列是一个有序列表,可以用数组或是链表表示。 2)遵循先入先出的原则。即:先存入队列的数据,要先取出。后存入的要后取出。 front及rear分别记录队列前后端...

    队列,循环队列为什么用空一个元素的位置

     本篇笔记是我在B站上跟着尚硅谷教程进行学习,记录的学习笔记,在学习中产生了疑问,并通过查找资料解决了相关问题。

    队列介绍

    1)队列是一个有序列表,可以用数组或是链表表示。

    2)遵循先入先出的原则。即:先存入队列的数据,要先取出。后存入的要后取出。

    • front及rear分别记录队列前后端的下标,front随着数据的输出而改变,而rear则是随着数据输入而改变。
    image-20200708160054824

    代码实现

    import java.util.Scanner;
    
    public class ArrayQueueDemo {
        public static void main(String[] args) {
            //创建一个队列
            ArrayQueue arrayQueue = new ArrayQueue(3);
            char key = ' ';//接受用户输入
            Scanner scanner = new Scanner(System.in);
            boolean loop = true;
            //输出一个菜单
            while(loop){
                System.out.println("s(show):显示队列");
                System.out.println("e(exit):退出程序");
                System.out.println("a(add):添加数据到队列");
                System.out.println("g(get):从队列取出数据");
                System.out.println("h(head):查看队列头的数据");
                key = scanner.next().charAt(0);
                switch (key){
                    case 's':
                        arrayQueue.showQueue();
                        break;
                    case 'a':
                        System.out.println("请输入一个数字:");
                        int value = scanner.nextInt();
                        arrayQueue.addQueue(value);
                        break;
                    case 'g':
                        try {
                            int res = arrayQueue.getQueue();
                            System.out.println("取出数据:"+res);
                        }catch (Exception e){
                            System.out.println(e.getMessage());
                        }
                        break;
                    case 'h':
                        try {
                            int res = arrayQueue.headQueue();
                            System.out.println("队列头数据:"+res);
                        }catch (Exception e){
                            System.out.println(e.getMessage());
                        }
                        break;
                    case 'e':
                        scanner.close();
                        loop = false;
                        break;
                    default:
                        break;
                }
            }
            System.out.println("程序退出");
        }
    }
    
    class ArrayQueue{
        private int maxSize;
        private int front;
        private int rear;
        private int[] arr;//模拟队列,该数组用于存放数据
    
        //创建队列的构造器
        public ArrayQueue(int arrMaxSize){
            maxSize = arrMaxSize;
            arr = new int[maxSize];
            front = -1;//指向队列头部(第一个数据的前面)
            rear = -1;//指向队列尾部(最后一个数据)
        }
        //判断队列是否满
        public boolean isFull(){
            return rear == maxSize-1;
        }
        //判断队列是够为空
        public boolean isEmpty(){
            return front==rear;
        }
        //添加数据到队列
        public void addQueue(int n){
            if(isFull()){
                System.out.println("队列已满,不可加入数据");
                return;
            }
            rear++;
            arr[rear] = n;
        }
        //从队列中取出数据
        public int getQueue(){
            if(isEmpty()){
                throw new RuntimeException("队列为空,不可取出数据");
            }
            front++;
            return arr[front];
        }
        //显示队列的中的所有数据
        public void showQueue(){
            if(isEmpty()){
                System.out.println("队列为空");
                return;
            }
            for (int i = 0; i <arr.length ; i++) {
                System.out.print(i+":"+ arr[i]+"\n");
            }
        }
        //显示队列的头数据,不是取出数据
        public  int headQueue(){
            if(isEmpty()){
                System.out.println("队列为空");
                throw new RuntimeException("队列为空");
            }
            return arr[front+1];
        }
    }
    
    

    问题分析并优化:

    • 目前数组使用了一次就不能用了,没有达到复用的效果

    • 我们要使用算法,将目前的数组改成一个环形的队列 取模%

    数组环形队列思路:

    1、front变量的含义做一个调整:front就指向队列的第一个元素,就是是说arr[front]就是队列的第一个元素,front初始值为0;

    2、rear变量的含义做一个调整:rear指向队列的最后一个元素的后一个位置,rear的初始值为0;

    3、队列满的条件:(rear+1)%maxSize ==front

    4、队列空的条件是:rear == front

    5、此时队列的有效长度是: (rear+maxSize-front)%maxSize

    遇到的问题(循环队列空一个元素的位置)

    在得到队列满的条件:(rear+1)%maxSize ==front时,我充满了疑惑,怎么算都觉得在rear已经表示最后元素的后一位了,这种情况下加一肯定是不对的,后来我查了一些资料。
    别人规定的循环队列

    那么,循环队列为什么用空一个元素的位置呢???

    这个是根据需要来用的
    循环队列中,由于入队时尾指du针向前追赶头指针;zhi出队时头指针向前追赶尾指针,造成dao队空和队满时头尾指针均相等。因此,无法通过条件front==rear来判别队列是"空"还是"满"。
    解决这个问题的方法至少有三种:
    ①另设一布尔变量以区别队列的空和满;
    ②少用一个元素的空间。约定入队前,测试尾指针在循环意义下加1后是否等于头指针,若相等则认为队满(注意:rear所指的单元始终为空);
    ③使用一个计数器记录队列中元素的总数(即队列长度)。

    代码实现(循环队列)

    import java.util.Scanner;
    
    public class CicleArrayQueueDemo {
        public static void main(String[] args) {
    
            System.out.println("测试数组模拟环形数据");
            CircleArray queue = new CircleArray(4);//空出一个位置,其队列有效数据为3;
            char key = ' ';
            Scanner scanner = new Scanner(System.in);
            boolean loop = true;
            while(loop){
                System.out.println("s(show):显示队列");
                System.out.println("e(exit):退出程序");
                System.out.println("a(add):添加数据到队列");
                System.out.println("g(get):从队列取出数据");
                System.out.println("h(head):查看队列头的数据");
                key = scanner.next().charAt(0);
                switch (key){
                    case 's':
                        queue.showQueue();
                        break;
                    case 'a':
                        System.out.println("请输入一个数字:");
                        int value = scanner.nextInt();
                        queue.addQueue(value);
                        break;
                    case 'g':
                        try {
                            int res = queue.getQueue();
                            System.out.println("取出数据:"+res);
                        }catch (Exception e){
                            System.out.println(e.getMessage());
                        }
                        break;
                    case 'h':
                        try {
                            int res = queue.headQueue();
                            System.out.println("队列头数据:"+res);
                        }catch (Exception e){
                            System.out.println(e.getMessage());
                        }
                        break;
                    case 'e':
                        scanner.close();
                        loop = false;
                        break;
                    default:
                        break;
                }
            }
            System.out.println("程序退出");
    
        }
    
        static class CircleArray{
            private int maxSize;
            private int front;//front就指向队列的第一个元素,就是是说arr[front]就是队列的第一个元素,front初始值为0;
            private int rear;//rear指向队列的最后一个元素的后一个位置,rear的初始值为0;
            private int[] arr;//模拟队列,该数组用于存放数据
    
            public CircleArray(int arrMaxSize){
                maxSize = arrMaxSize;
                arr = new int[maxSize];
            }
    
            //判断队列是否满
            public boolean isFull(){
                return (rear + 1)%maxSize ==front;
            }
            //判断队列是够为空
            public boolean isEmpty(){
                return front==rear;
            }
            //添加数据到队列
            public void addQueue(int n){
                if(isFull()){
                    System.out.println("队列已满,不可加入数据");
                    return;
                }
                arr[rear] = n;
                rear = (rear+1)%maxSize;
            }
            //从队列中取出数据
            public int getQueue(){
                if(isEmpty()){
                    throw new RuntimeException("队列为空,不可取出数据");
                }
                int value = arr[front];
                front = (front+1) % maxSize;
                return value;
            }
            //求出当前队列的个数
            public int arrCount(){
                return (rear+maxSize-front)%maxSize;
            }
            //显示队列的中的所有数据
            public void showQueue(){
                if(isEmpty()){
                    System.out.println("队列为空");
                    return;
                }
                for (int i = front; i <front+arrCount(); i++) {
                    System.out.print((i%maxSize)+":"+ arr[i%maxSize]+"\n");
                }
            }
            //显示队列的头数据,不是取出数据
            public  int headQueue(){
                if(isEmpty()){
                    System.out.println("队列为空");
                    throw new RuntimeException("队列为空");
                }
                return arr[front];
            }
    
        }
    }
    
    展开全文
  • 如果队列中没有元素,则称为空队列 队列抽象数据类型:其中T表示队列中数据的类型 public interface Queue { public void enqueue(T t); //元素入队,在队尾插入元素T public T dequeue(); //元素出队,

    队列(3.0笔记)
    1、定义:
    Queue)是插入和删除操作在线性表的两端进行,一端允许插入操作,而另一端只允许删除操作,允许插入的一端称为队尾(Rear),允许删除的另一端则称为队头(Front)。队列的插入操作通常称为入队或进队,删除操作通常称为出队。如果队列中没有元素,则称为空队列。

    队列抽象数据类型

    //其中T表示队列中数据的类型
    public interface Queue<T> {
    	public void enqueue(T t);  //元素入队,在队尾插入元素T
    	public T dequeue();       //元素出队,队头元素出队
    	public T peek();          //取队头元素值,但队头元素不出队
    	public boolean isEmpty();  //判断队列是否为空
    }
    
    队列的插入和删除操作在两端进行,使用队头指针(front)和
    队尾指针(rear)表示队列的操作的两端。
    队列的基本操作主要有创建队列、入队、出队、取队头元素、
    判断队列是否为空等。
    

    2、队列的顺序存储称为顺序队列(Sequential Queue):
    顺序队列用一个一维数组存放元素数据,用两个变量front和rear,分别表示队头和队尾的位置。

    public class SeqQueue<T> implements Queue<T> {
    	private T[] queue=null;  //声明一维数组,存储队列元素
    	private int length;      //数组的大小,表示队列的最大容量 
    	private int front;       //表示队头位置
    	private int rear;        //表示队尾位置
    	//实现队列接口的相关方法
    	……
    }
    

    3、顺序循坏队列

    3.01、定义:顺序循环队列是将顺序队列设计成逻辑上头尾相接的循环结构
    在这里插入图片描述
    3.02、表达式:
    入队操作时改变rear值,计算表达式为:rear=(rear+1)%length
    入队操作时改变rear值,计算表达式为:rear=(rear+1)%length

    3.03对空和队满判断
    约定队列中预留一个空位,在队头位置和队尾位置相差为1时,即认为队列已满,此时队满条件为:front=(rear+1)% length,队列中最多放length-1个元素。
    在这里插入图片描述
    在这里插入图片描述
    3.04、入队的操作

    //元素入队
    @Override
    public void enqueue(T t) {
    //判断队列是否满,若已满,则抛出异常,若未满,队尾位置向前移动1,插入元素
    	if(front==(rear+1) % length) {
    		throw new RuntimeException("队列已满,元素不能入队");
    	}else {
    		rear=(rear+1)%length;
    		queue[rear]=t;
    	}
    }
    
    

    3.05、出队的操作

    //元素出队
    @Override
    public T dequeue() {
    //判断队列是否空,若为空,抛出异常,若不为空,队头位置向前移动1,取出元素
    	if(isEmpty()) {
    		throw new RuntimeException("队列空,没有元素出队");
    	}else {
    		front=(front+1) %length;
    		T t=queue[front];
    		queue[front]=null;
    		return t;
    	}
    }
    //时间复杂度为O(1)
    

    3.06、取头元素

    @Override
    public T peek() {
    //判断队列是否空,若为空,抛出异常,若不为空,直接取出队头元素
    	if(isEmpty()) {
    		throw new RuntimeException("队列空,没有元素获取");
    	}else {
    		return queue[front+1];    //直接将队头元素取出
    	}
    }
    

    注意:获取队头元素和出队操作的区别在于,队头位置不移动

    3.07、判断队列是否为空

    @Override
    public T peek() {
    //判断队列是否空,若为空,抛出异常,若不为空,直接取出队头元素
    	if(isEmpty()) {
    		throw new RuntimeException("队列空,没有元素获取");
    	}else {
    		return queue[front+1];    //直接将队头元素取出
    	}
    }
    

    如有不对请指正!

    展开全文
  • 单向队列会出现“假溢出”问题,而循环队列却能解决“假溢出”问题。常规的循环队列实现方法需要浪费一个存储空间,那么如果不浪费一个空间是否也能实现一个循环队列呢?

    什么是队列

    队列和数组,链表,栈一样都是属于线性数据结构,而队列又和栈比较相似,都属于操作受限的数据结构,其中栈是“后入先出”,而队列是“先进先出”。

    和栈一样,队列也仅有两个基本操作:入队和出队(栈则是入栈和出栈)。往队列中放元素称之为入队,往队列中取元素称之为出队,然而相对于栈来说,队列又会复杂一点。

    队列中通常需要定义两个指针:headtail(当然,也有称之为:frontrear)分别用来表示头指针和尾指针。初始化队列时,headtail 相等,当有元素入队时,tail 指针往后移动一位,当有元素出队时,head 指针往后移动一位。

    在这里插入图片描述

    队空和队满

    根据上面的队列初始化和入队出队的过程,我们可以得到以下三个关系:

    • 初始化队列时:head=tail=-1(这里也可以设置为 0,看具体实现)。
    • 队列满时:tail=size-1(其中 size 为初始化队列时队列的大小)。
    • 队列空时:head=tail(比如上图中的第一和第三个队列)。

    队列的实现

    和栈一样,队列也可以通过数组或者链表来实现,通过数组来实现的队列我们称之为“顺序队列”,通过链表实现的队列称之为“链式队列”。

    数组实现队列

    package com.lonely.wolf.note.queue;
    
    /**
     * 基于数组实现自定义单向队列。FIFO(first in first out)先进先出
     * @author lonely_wolf
     * @version 1.0
     * @date 2021/12/26
     * @since jdk1.8
     */
    public class MyQueueByArray<E> {
        public static void main(String[] args) {
            MyQueueByArray myQueue = new MyQueueByArray(3);
            System.out.println("队列是否为空:" + myQueue.isEmpty());//输出:true
            myQueue.enqueue(1);
            myQueue.enqueue(2);
            myQueue.enqueue(3);
            System.out.println("队列是否已满:" + myQueue.isFull());//输出:true
            System.out.println("第1次出队:" + myQueue.dequeue());//输出:1
            System.out.println("第2次出队:" + myQueue.dequeue());//输出:2
            System.out.println("第3次出队:" + myQueue.dequeue());//输出:3
            System.out.println("队列是否为空:" + myQueue.isEmpty());//输出:true
            System.out.println("队列是否已满:" + myQueue.isFull());//输出:true
        }
    
        private Object[] data;
        private int size;//队列长度
        private int head;//队列头部
        private int tail;//队列尾部
    
        public MyQueueByArray(int size) {//初始化
            this.size = size;
            data = new Object[size];
            head = -1;
            tail = -1;
        }
    
        /**
         * tail=size-1 表示队列已满
         * @return
         */
        public boolean isFull(){
            return tail == size - 1;
        }
    
        /**
         * head=tail表示队列为空
         * @return
         */
        public boolean isEmpty(){
            return head == tail;
        }
    
    
        /**
         * 元素入队,tail指针后移一位
         * @param e
         * @return
         */
        public boolean enqueue (E e){
            if (isFull()){
                return false;
            }
            data[++tail] = e;//tail 指针后移
            return true;
        }
    
    
        /**
         * 元素出丢
         * @return
         */
        public E dequeue (){
            if (isEmpty()){
                return null;
            }
            E e = (E)data[++head];//出队
            return e;
        }
    }
    

    链表实现队列

    有了上面基于数组实现的简单队列例子,基于链表实现队列相信大家也能写出来,如果用链表实现队列,我们们同样需要head 指针和 tail 指针。其中 head 指向链表的第一个结点,tail 指向最后一个结点。

    入队时:

    tail.next = newNode;
    tail = tail.next;
    

    出队时:

    head = head.next;
    

    假溢出问题

    我们回到上面数组实现的例子中,我们发现最后的两个输出语句两个都是 true,也就是队列又是空的又是满的,这看起来是一个自相矛盾的事情却在队列里面出现了,我们来看看这时候队列的示意图:

    在这里插入图片描述

    通过上图中我们发现,因为 tail=size-1,所以队列是满的;而此时又同时满足:head=tail,所以根据上面队空的条件,我们又可以得到当前队列是空的,也就是当前队列是没有元素的。这时候我们已经无法继续入队了,但是这时候队列中的其实是有空间的,有空间却不能被利用,这就是单向队列的“假溢出”问题。

    那么如何解决这个问题呢?解决这个问题有两个思路。

    • 思路一

    前面我们学习数组的时候提到了,当数组中删除一个元素,那么这个位置之后的所有元素都需要往前移动一位,所以队列中也是同理,假如我们用数组来实现的话,当元素出队时,我们把所有元素都往前移,不过这样因为每次都需要搬移数据,导致入队的时间复杂度是 O(n)

    • 思路二

    因为搬移数据会影响到入队效率,那么如何不搬移数据又能将队列的空闲空间利用起来呢?答案也很简单,那就是当再次有新元素入队时,我们把 tail 指针又重新移动到队列的最开头位置,这样也能避免出现“假溢出”问题,同时时间复杂度仍然保持为 O(1)

    循环队列

    上面提到的第二种思路来解决单向队列的“假溢出”问题,实际上就构成了一个循环队列。而上面单向队列判断当前队列是否队满时仅需要满足 tail=size-1 即可,但是循环队列肯定不行,因为当 tail=size-1 时继续添加元素,tail 可能可以移动到 size=0 的位置,所以如果要实现循环队列最关键还是需要确定好队空和队满的条件。

    队空和队满

    在循环队列中,当初始化队列时,一般会将其设置为 0,而队空条件仍然是 head=tail,循环队列最关键的是如何确定队满条件。

    下图是初始化一个长度为 6 的队列以及连续入队 5 个元素后的循环队列中 headtail 指针示意图:

    在这里插入图片描述

    上图中第二个队列表示的是入队 5 个元素之后 tail 指针的位置,这时候如果继续入队,那么 tail 只能指向队列开头也就是元素 1 所在的位置,此时会得到下面这个示意图的场景:
    在这里插入图片描述

    这时候发现 head=tail,和队空时的条件冲突了,那么如何解决这个问题呢?主要有三种解决办法:

    1. (tail+1)%size=head 时就表示队列已满,这时候 tail 所在位置为空,所以会浪费一个空间(也就是第一幅图中第二个队列的场景就算队列已满)。
    2. 新增一个容量 capacity 字段,并进行维护,当 capacity=size 表示队列已满。
    3. 和第二个办法差不多,我们可以再维护一个标记,或者当 head=tail 时同步判断当前位置是否有元素来判断当前是队空还是队满。

    这三种思路我们发现都各有缺点:方法 1 会浪费一个空间;方法 2 每次入队和出队时候都需要维护 capacity 字段;方法 3 就是不论队列空或者队列满时都要多一次判断方式。

    相互比较之下,其实方法一的思路就是空间换时间,而另外两种办法当数据量并发量很大时,多一次判断其实也是会对性能有所影响,常规的循环链表会采用方法 1 进行处理,也就是选择浪费一个空间的方式。当然大家在实际开发过程中也可以自行斟酌。

    实现循环队列

    下面我们就以方法 1 的思路基于数组来实现一个循环队列:

    package com.lonely.wolf.note.queue;
    
    /**
     *
     * 实现循环队列
     * @author lonely_wolf
     * @version 1.0
     * @date 2021/12/26
     * @since jdk1.8
     */
    public class MyCycleQueueByArray<E> {
    
        public static void main(String[] args) {
            MyCycleQueueByArray cycleQueue = new MyCycleQueueByArray(3);
            System.out.println("循环队列是否为空:" + cycleQueue.isEmpty());//输出:true
            System.out.println("1是否入队成功:" + cycleQueue.enqueue(1));//输出:true
            System.out.println("2是否入队成功:" + cycleQueue.enqueue(2));//输出:true
            System.out.println("3是否入队成功:" + cycleQueue.enqueue(3));//输出:false
            System.out.println("循环队列是否已满:" + cycleQueue.isFull());//输出:true
            System.out.println("第1次出队:" + cycleQueue.dequeue());//输出:1
            System.out.println("第2次出队:" + cycleQueue.dequeue());//输出:2
            System.out.println("第3次出队:" + cycleQueue.dequeue());//输出:null,因为 3 入队失败
            System.out.println("循环队列是否为空:" + cycleQueue.isEmpty());//输出:true
            System.out.println("循环队列是否已满:" + cycleQueue.isFull());//输出:false
        }
    
        private Object[] data;
        private int size;
        
        private int head;//队列头部
        private int tail;//队列尾部
    
        public MyCycleQueueByArray(int size) {
            this.size = size;
            data = new Object[size];
            head = 0;
            tail = 0;
        }
    
        public boolean isFull(){
            return (tail + 1) % size == head;
        }
    
        public boolean isEmpty(){
            return head == tail;
        }
    
        /**
         * 入队
         * @param e
         * @return
         */
        public boolean enqueue (E e){
            if (isFull()){
                return false;
            }
            data[tail] = e;
            tail =  (tail + 1) % size;//注意这里不能直接 tail++,否则无法循环使用
            return true;
        }
    
    
        /**
         * 出队
         * @return
         */
        public E dequeue (){
            if (isEmpty()){
                return null;
            }
            E e = (E)data[head];
            head =  (head + 1) % size;//head 也同样不能直接 head++
            return e;
        }
    }
    

    这时候我们发现,虽然队列空间有 3 个,但是实际上只能存放 2 个元素,而最后两条输出语句的输出结果也说明了循环队列不会出现单向队列的“假溢出问题”。

    队列实战

    队列其实在 Javajuc 中有广泛应用,比如 AQS 等,在这里,我们继续来看一看队列的相关算法题来加深对队列的理解。

    两个栈实现队列

    前面我们讲栈的时候,用了两个队列来实现栈,这道题却正好相反,是利用两个栈来实现队列。

    LeetCode232 题:请你仅使⽤两个栈实现先⼊先出队列,队列应当⽀持⼀般队列⽀持的所有操作(push、pop、peek、empty)。

    这道题目其实相比较之前两个队列实现栈还是会更简单一点,因为栈是后入先出,所以我们只需要将入队和出队使用不同的栈就可以解决了。

    具体解题思路为:将⼀个栈当作输⼊栈,⽤于压⼊(push)传⼊的数据;另⼀个栈当作输出栈,⽤于 pop(出队) 和 peek(查看队列头部元素) 操作。 每次 poppeek 时,若输出栈为空则将输⼊栈的全部数据依次弹出并压⼊输出栈,再将元素从输出栈输出。

    具体代码实现为:

    package com.lonely.wolf.note.queue;
    
    import java.util.Stack;
    
    /**
     * LeetCode 232
     * 请你仅使⽤两个栈实现先⼊先出队列。队列应当⽀持⼀般队列⽀持的所有操作(push、pop、peek、empty):
     *
     * void push(int x) 将元素 x 推到队列的末尾
     * int pop() 从队列的开头移除并返回元素
     * int peek() 返回队列开头的元素
     * boolean empty() 如果队列为空,返回 true ;否则,返回 false
     *
     * 说明:
     * 你只能使⽤标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
     * 你所使⽤的语⾔也许不⽀持栈。你可以使⽤ list 或者 deque(双端队列)来模拟⼀个栈,只要是标准的栈操作即可。
     *
     * 解题思路
     * 将⼀个栈当作输⼊栈,⽤于压⼊ push 传⼊的数据;另⼀个栈当作输出栈,⽤于 pop 和 peek 操作。
     * 每次 pop 或 peek 时,若输出栈为空则将输⼊栈的全部数据依次弹出并压⼊输出栈,
     *
     * @author lonely_wolf
     * @version 1.0
     * @date 2021/12/26
     * @since jdk1.8
     */
    public class MyQueueByTwoStack<Integer> {
        private Stack<Integer> inStack;//输入栈
        private Stack<Integer> outStack;//输出栈
    
        /**
         * 即入队:enqueue 操作
         * @param e
         */
        public void push(Integer e){
            inStack.push(e);//压入输入栈
        }
    
        /**
         * 查看并移除队列头部元素,即:出队 dequeue 操作
         * @return
         */
        public Integer pop(){
            if (!outStack.isEmpty()){//输出栈不为空则直接出栈
                return outStack.pop();
            }
            while (!inStack.isEmpty()){//输出栈为空,则检查输入栈
                outStack.push(inStack.pop());//输入栈不为空,则将其压入输出栈
            }
            if (!outStack.isEmpty()){//再次检查输出栈是否有元素出栈
                return outStack.pop();
            }
            return null;
        }
    
        /**
         * 查看队列头部元素,相比较 pop,这里只查看元素,并不移除元素
         **/
        public Integer peek(){
            if (!outStack.isEmpty()){
                return outStack.peek();
            }
            while (!inStack.isEmpty()){
                outStack.push(inStack.pop());
            }
            if (!outStack.isEmpty()){
                return outStack.peek();
            }
            return null;
        }
    
        /**
         * 队列是否为空
         * @return
         */
        public boolean empty(){
            return inStack.isEmpty() && outStack.isEmpty();
        }
    }
    

    总结

    本文主要讲述了队列这种操作受限的数据结构,文中通过一个例子说明了单向链表为什么会存在“假溢出“问题,并最终引出了循环链表,而循环链表的实现同样有三种不同思路,并通过以空间换时间的方法基于数组实现了一个简单的循环链表。最后我们还讲述了如何利用两个栈来实现一个队列。

    展开全文
  • 下面小编就为大家分享篇java队列实现方法(顺序队列,链式队列,循环队列),具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧
  • 在我们生活中有很多队列的影子,可以说与时间相关的问题,一般都会涉及到队列问题;本文详细介绍了如何使用C语言实现循环队列,下面起来看看。
  • javascript中利用数组实现的循环队列代码,需要的朋友可以参考下。
  • 文章目录前言一、思路二、代码实现1.MyCircularQueue(k) 构造方法2.Front 从队首获取元素3.Rear 获取队尾元素4.enQueue(value) 向循环队列插入一个元素5.deQueue():从循环队列中删除一个元素6.isEmpty() 判断循环...
  • 队列循环队列的创建添加和删除操作 1实验目的掌握循环队列的基本操作并对其进行简单应用 2实验内容 假设循环队列的最大长度为7现在依次将以下数据入队列{753924}接着进行3次出队列的操作再将1518这两数据入队列...
  • 循环队列元素个

    万次阅读 多人点赞 2017-06-17 08:30:14
    1. 设有一个用数组Q[1..m]表示的环形队列,约定f为当前队头元素在数组中的位置,r为队尾元素的后一位置(按顺时针方向),若队列非空,则计算队列元素个数的公式应为() A、 (m+r-f)mod m B、 r-f C、 (m-r-f)...
  • 循环队列添加删除元素

    千次阅读 2017-11-14 10:51:11
    #include using namespace std; const int Maxsize = 12; struct QNode { int *Data; int front, rear; int Maxsize; }; typedef struct QNode * Queue; Queue CreatQueue(int Maxsize) ... Queue Q = new struct
  • C语言实现循环队列

    2021-01-19 23:53:05
    本文实例为大家分享了C语言实现循环队列的具体代码,供大家参考,具体内容如下 注意事项: 1、循环队列,是队列的顺序...4、在每一个指针递增的表达式中,都要加上一个% MAXQUEUE已使得一次增值都在范围内。 #inclu
  • CircularPriorityQueue:循环优先级队列结构的实现及其基本功能,例如添加和删除元素,显示第一个元素,容量和当前元素
  • 结论: 某元素前方的个数 = (元素index - 首指针+ 数组长度)% 数组长度 和求元素的总数思路一样,你可以认为求当前元素的前方元素(不包含当前元素)的...尾指针指向最后插入元素的下一个位置,在我的循环队列中留一...
  • 下面小编就为大家分享篇基于Java数组实现循环队列的两种方法小结,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧
  • 队列一个有序列表,可以用数组或是链表来实现。 遵循先入先出的原则。即:先存入队列的数据,要先取出。后存入的要后取出。 数组模拟队列 队列本身是有序列表,若使用数组的结构来存储队列的数据,则队列数组的...
  • 主要介绍了Java循环队列原理与用法,结合实例形式详细分析了Java循环队列基本概念、原理、用法及操作注意事项,需要的朋友可以参考下
  • import java.awt.Font; import java.util.Scanner; import javax.management.RuntimeErrorException; ... //创建队列 CircleArrayQueue circleArrayQueue = new CircleArrayQueue(4); char k
  • 定义一个数组,int型的top表示栈顶(表示当前可以插入元素的位置),usesize表示使用的栈的大小 栈的push和pop要注意top的移动,usesize的增加减小 3、栈的练习题之括号匹配 可以在leetcode上找到 明确,括号的几种...
  • 下面小编就为大家带来篇Java用数组实现循环队列的示例。小编觉得挺不错的,现在就分享给大家,也给大家做参考。一起跟随小编过来看看吧
  • java实现循环队列

    2021-03-17 16:21:45
    java实现循环队列循环队列的优点普通队列出队操作开销大:在出队操作时,索引为0后面的所有元素,都需要往前移动位,元素越多,消耗的时间也越多,时间复杂度为O(N)。循环队列的逻辑:1、当元素较少时(tail位置在...
  • Q 是一个队列,S 是一个空栈,实现将队列中的元素逆置的算法。
  • https://blog.csdn.net/m0_58672924/article/details/122647558https://blog.csdn.net/m0_58672924/article/details/122647558之所以没有选择数组来实现,是因为一个元素出队,数组中所有剩下的元素都需要向前...
  • Java实现循环队列

    2019-12-03 14:59:25
    队列作为种基础的数据结构,具有先进先出的特性,也就是从队列中取元素始终取得是队首元素。由于队列元素元素之间没有强关联性,所以我们可以采用Java中得数组来存储队列元素。 普通队列 采用数组存储队列元素...
  • 数组实现循环队列

    千次阅读 2021-01-22 22:18:30
    这实际上是把队列空间想象成一环形空间,环形空间中的存储单元循环使用,用这种方法管理的队列也就称为循环队列。除了一些简单应用之外,真正实用的队列是循环队列。 顺序队列的假溢出:当元素被插
  • 循环队列Python

    2021-02-10 08:39:47
    我试图在Python中创建一个循环队列,以便在到达数组中的最后一个元素时指向头部。我正在研究排队方法,我遇到了一些问题。我正在尝试使用一个大小为4的数组,并且能够将值排队到第4个点,但是当它执行elif语句时,我...
  • 实现一个优先队列:设置优先级,然后在正确的位置添加元素。 我们这里实现的是最小优先队列,优先级的值小(优先级高)的元素被放置在队列前面。 //创建一个类来表示优先队列 function Priorityqueue(){ var items...
  • 队列种线性结构。...队列的操作:队列的实现:添加元素(入队) : void enqueue(E) 删除、取出元素(出队) : E dequeue()。 取得队首元素 :E getFront() 查看队列有多少元素 :int getSize() 判断队列是否...
  • 这是因为队列在顺序存储上的不足:每次从数组头部删除元素(出队)后,需要将头部以后的所有元素往前移动一个位置,这是一个时间复杂度为O(n)的操作: 思路二: 可能有人说,把队首标志往后移动不就不用移动元素了...
  • C++实现循环队列前言1.什么时候循环队列为空2.Push()操作(1)何时队列满了?(2)当队列满了,怎样扩大...创建一个Queue类,确定成员函数和数据成员 template <typename T> class Queue { Queue(int _capacity = 1

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 129,449
精华内容 51,779
关键字:

循环队列每加入一个元素