首页 > 编程语言 >算法15:冷门面试题_队列实现栈,栈实现队列

算法15:冷门面试题_队列实现栈,栈实现队列

时间:2023-02-08 21:46:22浏览次数:47  
标签:面试题 15 队列 System public int println stack out

 

经常有些面试官很变态,一般都是老阴逼级别的,喜欢问一些变态的问题。但是,反过来思考一下,这些题目也确实具备一些动手的能力,变相能够考查面试者的coding能力。

面试一:怎么样用数组实现不产过固定大小的队列和栈?

队列实现:

package code2.数组实现栈和队列_02;

public class Queue_02 {

    class MyQueue {
        private int pollIndex;
        private int pushIndex;
        private int size;
        private int[] arr;
        private int limit;

        MyQueue(int limit) {
            pollIndex = 0;
            pushIndex = 0;
            arr = new int[limit];
            size = 0;
            this.limit = limit;
        }

        private int nexIndex(int index) {
            return index == limit-1 ? 0 : ++index;
        }

        public void push(int data) {
            if (size == limit) {
                System.out.println("队列满了,无法添加元素:" + data);
                return;
            }
            arr[pushIndex] = data;
            pushIndex = nexIndex(pushIndex);
            size++;
        }

        public int poll () {
            if (size == 0) {
                System.out.println("队列为空,无法取出元素");
                return -1;
            }
            int temp = arr[pollIndex];
            pollIndex = nexIndex(pollIndex);
            size--;
            return temp;
        }
    }

    public static void main(String[] args) {
        Queue_02 test = new Queue_02();
        MyQueue queue = test.new MyQueue(5);
        for(int i = 0; i < 6; i++) {
            queue.push(i);
        }
        System.out.println("取出对应元素" + queue.poll());
        System.out.println("取出对应元素" + queue.poll());
        System.out.println("取出对应元素" + queue.poll());
        queue.push(11);
        queue.push(12);
        queue.push(13);
        queue.push(14);

        //遍历队列
        System.out.println("=========遍历============");
        for(int i =0; i < 5; i++) {
            System.out.println("取出对应元素" + queue.poll());
        }
    }
}

  

 栈实现:

package code2.数组实现栈和队列_02;

public class Stack_01 {

    class MyStack {
        private int[] arr = null;
        private int index;
        private int size;

        public MyStack(int limit) {
            arr = new int[limit];
            size = limit;
            index = 0;
        }

        public void pushElement (int data)
        {
            if (size == index) {
                System.out.println("准备插入数据:" + data + " ,由于栈已满,无法插入成功");
                return;
            }
            arr[index] = data;
            index++;
        }

        public int pollElement()
        {
            if (index == 0) {
                System.out.println("栈为空, 无法获取数据");
                return -1;
            }
            index--;
            int temp = arr[index];
            return temp;
        }
    }


    public static void main(String[] args) {
        Stack_01 test = new Stack_01();
        MyStack stack =test.new MyStack(5);
        for (int i = 0; i < 8; i++) {
            stack.pushElement(i);
        }

        for (int i = 0; i < 8; i++) {
            System.out.println(stack.pollElement());
        }
    }

}

  

面试题二:

实现一个特殊的栈,在基本功能的基础上,再实现返回栈中最小元素的功能

1)pop、push、getMin操作的时间复杂度都是 O(1)。

2)设计的栈类型可以使用现成的栈结构

解题思路就是用2个数组,一个数组存储栈的元素,另一个数组这是存储栈中的最小值,下图是我手绘的流程:

 

package code2.数组实现栈和队列_02;
/**
 * 实现一个特殊的栈,在基本功能的基础上,再实现返回栈中最小元素的功能
 * 1)pop、push、getMin操作的时间复杂度都是 O(1)。
 * 2)设计的栈类型可以使用现成的栈结构。
 */

public class Stack_03 {

    class MyStack {
        private int[] arr = null;
        private int[] minArr = null;
        private int index;
        private int limit;

        public MyStack(int limit) {
            arr = new int[limit];
            minArr = new int[limit];
            this.limit = limit;
            index = 0;
        }

        public void pushElement (int data)
        {
            if (index == limit) {
                System.out.println("准备插入数据:" + data + " ,由于栈已满,无法插入成功");
                return;
            }
            arr[index] = data;
            setMin(data);
            index++;
        }

        public int pollElement()
        {
            if (index == 0) {
                System.out.println("栈为空, 无法获取数据");
                return -1;
            }
            index--;
            int temp = arr[index];
            arr[index] = 0;
            minArr[index] = 0;
            return temp;
        }

        public void setMin(int data) {

            if (index != 0) {
                int temp = index;
                int value = minArr[--temp];
                if (data < value) {
                    minArr[index] = data;
                }
                else {
                    minArr[index] = value;
                }
            }
            else {
                minArr[0] = data;
            }
        }

        public int getMin() {
            int temp = index;
            return minArr[--temp];
        }
    }


    public static void main(String[] args) {
        Stack_03 test = new Stack_03();
        MyStack stack =test.new MyStack(5);
        for (int i = 8; i > 6; i--) {
            stack.pushElement(i);
        }

        stack.pushElement(11);
        stack.pushElement(2);
        stack.pushElement(13);

        System.out.println("获取最小值:" + stack.getMin());
        stack.pushElement(14);

        System.out.println("删除:" + stack.pollElement());
        System.out.println("获取最小值:" + stack.getMin());
        System.out.println("删除:" + stack.pollElement());
        System.out.println("获取最小值:" + stack.getMin());
        System.out.println("删除:" + stack.pollElement());
        System.out.println("获取最小值:" + stack.getMin());

        stack.pushElement(6);
        System.out.println("获取最小值:" + stack.getMin());


        System.out.println("删除:" + stack.pollElement());
        System.out.println("获取最小值:" + stack.getMin());
        System.out.println("删除:" + stack.pollElement());
        System.out.println("获取最小值:" + stack.getMin());

        //8, 7,11,2,13
    }

}

  

面试题三:用栈结构实现队列

package code2.数组实现栈和队列_02;

import java.util.Stack;

//栈实现队列
public class StackImpmentQueue {

    private Stack stackPush;
    private Stack stackPop;

    public StackImpmentQueue()
    {
        stackPush = new Stack<Integer>();
        stackPop = new Stack<Integer>();
    }

    public void push (int data)
    {
        if (!stackPop.isEmpty()) {
            throw new RuntimeException("stackPop中还有数据待取出,无法添加新元素");
        }

        stackPush.push(data);
    }

    public int pop () {
        while (!stackPush.isEmpty()) {
            stackPop.push(stackPush.pop());
        }

        if (stackPop.isEmpty()) {
            throw new RuntimeException("Queue is empty!");
        }
        return (int) stackPop.pop();
    }



    public static void main(String[] args)
    {
        StackImpmentQueue t = new StackImpmentQueue();
        for (int i = 0; i < 5; i++) {
            t.push(i);
        }

        for (int i = 0; i < 5; i++) {
            System.out.println("get :" + t.pop());
        }

        for (int i = 11; i < 15; i++) {
            t.push(i);
        }

        for (int i = 0; i < 5; i++) {
            System.out.println("get :" + t.pop());
        }

    }
}

  

面试题四:用队列实现栈:

package code2.数组实现栈和队列_02;

import java.util.LinkedList;
import java.util.Queue;

//队列实现栈
public class QueueImplementStack {
    private Queue queuePush;
    private Queue queueBak;

    public QueueImplementStack() {
        queueBak = new LinkedList();
        queuePush = new LinkedList();
    }

    public void push(int value) {
        queuePush.add(value);
    }

    public int pop() {

        if (queuePush.isEmpty()) {
            throw new RuntimeException("队列为空,无法获取有效数据");
        }

        while(queuePush.size() > 1) {
            queueBak.add(queuePush.poll());
        }

        Object val = queuePush.poll();

        Queue temp = queueBak;
        queueBak = queuePush;
        queuePush = temp;

        return (int)val;
    }

    public boolean isEmpty () {
        return queuePush.isEmpty();
    }

    public static void main(String[] args) {
        QueueImplementStack stack = new QueueImplementStack();
        stack.push(1);
        stack.push(2);
        stack.push(3);
        stack.push(4);

        System.out.println("获取栈元素" + stack.pop());

        stack.push(5);
        System.out.println("获取栈元素" + stack.pop());
        while (!stack.isEmpty()) {
            System.out.println("获取栈元素" + stack.pop());
        }
    }
}

  

 

标签:面试题,15,队列,System,public,int,println,stack,out
From: https://www.cnblogs.com/chen1-kerr/p/17103388.html

相关文章

  • 获取DHCP Option 15信息
    不想通过dhcpsapi.dll调用,因为我不想仅限于WindowsDHCP服务器。有没有其他方法通过C#获取DHCP信息您可以使用WMI和Win32_NetworkAdapterConfiguration类。返回的可用字......
  • 算法随想Day6【哈希表】| LC344-反转字符串、LC541-反转字符串Ⅱ、JZ-替换空格、LC151
    LC344.反转字符串voidreverseString(vector<char>&s){intsize=s.size();intleft=0,right=size-1;while(left<right){s[l......
  • C/C++ 数据结构链式队列的定义与实现
    #include<iostream>#include<Windows.h>usingnamespacestd;typedefstruct_QNode{intdata;struct_QNode*next;}QNode;typedefstruct{QNode......
  • 消息队列解析Message
    消息队列生产者@AutowiredprivatefinalAmqpTemplateamqpTemplate;publicvoidtest(){Map<String,Object>testMap=Maps.newHashMap();testMap.put(......
  • #yyds干货盘点# LeetCode面试题:字符串转换整数 (atoi)
    1.简述:请你来实现一个 myAtoi(strings) 函数,使其能将字符串转换成一个32位有符号整数(类似C/C++中的atoi函数)。函数 myAtoi(strings)的算法如下:读入字符串并丢弃......
  • 前端面试题(1) js
    keywords:JS深拷贝深拷贝:针对【引用】类型,传递的是地址,多变量同时指向同一块内存地址(比如某个对象)letobj1={ //1.不需要处理 //基本数据类型可以不做处理,typeof!==......
  • 米联客MLK-CZ05-7015-485 核心模块硬件手册
    1整体概述自2017年米联客MLK-CZ05-7015-485(MZ7XCORE485)系列开发平台发布以来,米联客ZYNQ系列开发平台和核心模块经过多次迭代升级,在工业自动化、水利电力控制设备、医......
  • vue春招面试题
       一、MVVM模型●model->data数据●view->dom模型,●viewModel->视图模型,实例。相当于一个桥梁 二、Vue中响应式数据的理解  三、Vue如何检测数组变化......
  • 由一次生产事故思考队列在实际项目中的应用价值
    话说从一名.Neter转到Java开发也已经有3年多时间了,期间也积累了一些经验。今天就来谈谈RabbitMQ在实际项目中的应用。那是2020年的某个周末,突然收到反馈,商城页......
  • 队列的顺序存储
      #include<iostream>usingnamespacestd;#defineMAXSize10typedefintElemtype;typedefstruct{ Elemtypedata[MAXSize]; intfront,rear;}SqQueue;boolIsEmp......