Stack and queue classic interview questions

Bidirectional linked list to realize stack and queue

First use the two-way linked list to build a DoubleEndsQueue Containers , Data can be inserted head or tail , You can delete the header or the footer , Then use this container to build stacks and queues , Stack push and pop It's header insertion and header deletion , Queued push and poll That is, head insertion and tail deletion or tail insertion and head deletion

package com.zzf.algorithm;

/** * @author zzf * @date 2022-01-26 */
public class DoubleLinkedListToStackAndQueue {
    
    public static class Node<T>{
    
        public T value;
        public Node<T> last;
        public Node<T> next;

        public Node(T data){
    
            value = data;
        }
    }

    public static class DoubleEndsQueue<T>{
    
        public Node<T> head;
        public Node<T> tail;

        // The first interpolation 
        public void addFormHead(T value){
    
            Node<T> cur = new Node<>(value);
            if(head == null){
    
                head = cur;
                tail = cur;
            }else{
    
                cur.next = head;
                head.last = cur;
                head = cur;
            }
        }

        // The tail interpolation 
        public void addFromBottom(T value){
    
            Node<T> cur = new Node<>(value);
            if(head == null){
    
                head = cur;
                tail = cur;
            }else{
    
                cur.last = tail;
                tail.next = cur;
                tail = cur;
            }
        }

        // Head deletion 
        public T popFromHead(){
    
            if(head == null){
    
                return null;
            }
            Node<T> cur = head;
            if(head == tail){
    
                head = null;
                tail = null;
            }else{
    
                head = head.next;
                cur.next = null;
                head.last = null;
            }
            return cur.value;
        }

        // Tail deletion 
        public T popFromBottom(){
    
            if(head == null){
    
                return null;
            }
            Node<T> cur = tail;
            if(head == tail){
    
                head = null;
                tail = null;
            }else {
    
                tail = tail.last;
                tail.next = null;
                cur.last = null;
            }
            return cur.value;
        }

        public boolean isEmpty(){
    
            return head == null;
        }

    }

    //DoubleEndsQueue Implementation stack 
    public static class MyStack<T>{
    
        private DoubleEndsQueue<T> queue;

        public MyStack(){
    
            queue = new DoubleEndsQueue<>();
        }

        public void push(T value){
    
            queue.addFormHead(value);
        }

        public T pop(){
    
            return queue.popFromHead();
        }

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

    //DoubleEndsQueue Implementation queue 
    public static class MyQueue<T>{
    
        private DoubleEndsQueue<T> queue;
        public MyQueue(){
    
            queue = new DoubleEndsQueue<>();
        }

        public void push(T value){
    
            queue.addFormHead(value);
        }

        public T poll(){
    
            return queue.popFromBottom();
        }

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

Array implementation stack and queue

The array implementation stack uses a index Here comes the pointer push and pop,limit To limit the maximum amount of data , At the beginning index Point to 0,push when , First add data to index Location , then index++,pop when , First judge index Is it 0, To determine whether the stack is empty , If it is not empty index-1, Then return the value pointed to

The array implements the queue with two pointers pushi and polli Point to push Location and poll Location , use size and limit Control the full and empty of the queue , Definition nextIndex Function to realize the circular utilization of array position

package com.zzf.algorithm;

/** * @author zzf * @date 2022-01-26 */
public class ArrayToStackAndQueue {
    

    // Array implementation stack 
    public static class MyStack{
    
        private int[] arr;
        private int index;
        private final int limit;

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

        public void push(int value){
    
            if(index == limit){
    
                throw new RuntimeException(" The stack is full ");
            }
            arr[index++] = value;
        }

        public int pop(){
    
            if(index == 0){
    
                throw new RuntimeException(" The stack is empty ");
            }
            return arr[--index];
        }
        public boolean isEmpty(){
    
            return index == 0;
        }
    }

    // Array implementation queue 
    public static class MyQueue{
    
        private int[] arr;
        private int pushi;
        private int polli;
        private int size;
        private final int limit;
        
        public MyQueue(int limit){
    
            arr = new int[limit];
            pushi = 0;
            polli = 0;
            size = 0;
            this.limit = limit;
        }
        
        public void push(int value){
    
            if(size == limit){
    
                throw new RuntimeException(" The queue is full ");
            }
            size++;
            arr[pushi] = value;
            pushi = nextIndex(pushi);
        }
        public int poll(){
    
            if(size == 0){
    
                throw new RuntimeException(" The queue is empty ");
            }
            size--;
            int ans = arr[polli];
            polli = nextIndex(polli);
            return ans;
        }
        
        public boolean isEmpty(){
    
            return size == 0;
        }
        
        // Returns the next position of the current pointer , Used to cycle 
        private int nextIndex(int i){
    
            return i < limit - 1 ? i+1 : 0; 
        }
    }
}

Special stack

The first treatment ： Prepare two stacks , One is the data stack , One is the minimum stack ,push when , The first one is to count both , after , Each number is compared with the top of the minimum stack , When it is less than or equal to, both of them are put , Otherwise, they will only be put into the data stack .pop when , Only the value at the top of the data stack is equal to the value at the top of the minimum stack , Just together pop, Otherwise, only pop The data stack , The minimum value of the data stack is maintained at the top of the stack

The second treatment ： Prepare two stacks , One is the data stack , One is the minimum stack ,push when , The first one is to count both , after , Each number is compared with the top of the minimum stack , When it is less than or equal to, both are put , Greater than , Put new data in the data stack , The minimum stack is placed at the top of the stack .pop when , Together pop, The minimum value of the data stack is maintained at the top of the stack

package com.zzf.algorithm;

import java.util.Stack;

/** * @author zzf * @date 2022-01-26 */
public class GetMinStack {
    
    // The first treatment 
    public static class MyStack1{
    
        private Stack<Integer> stackData;
        private Stack<Integer> stackMin;

        public MyStack1(){
    
            this.stackData = new Stack<>();
            this.stackMin = new Stack<>();
        }

        public void push(int newNum){
    
            if(this.stackMin.isEmpty()){
    
                this.stackMin.push(newNum);
            }
            else if(newNum <= this.getmin()){
    
                this.stackMin.push(newNum);
            }
            this.stackData.push(newNum);
        }

        public int pop() {
    
            if(this.stackData.isEmpty()){
    
                throw new RuntimeException(" The stack is empty ");
            }
            int value = this.stackData.pop();
            if(value == this.getmin()){
    
                this.stackMin.pop();
            }
            return value;
        }
        private int getmin() {
    
            if(this.stackMin.isEmpty()){
    
                throw new RuntimeException(" The stack is empty ");
            }
            return stackMin.peek();
        }
    }

    // The second treatment 
    public static class MyStack2{
    
        private Stack<Integer> stackData;
        private Stack<Integer> stackMin;


        public MyStack2(){
    
            this.stackData = new Stack<>();
            this.stackMin = new Stack<>();
        }

        public void push(int newNum){
    
            if(this.stackMin.isEmpty()){
    
                this.stackMin.push(newNum);
            }
            else if(newNum < this.getMin()){
    
                this.stackMin.push(newNum);
            }
            else{
    
                int newMin = this.stackMin.peek();
                this.stackMin.push(newMin);
            }
            this.stackData.push(newNum);
        }

        public int pop(){
    
            if(stackData.isEmpty()){
    
                throw new RuntimeException(" The stack is empty ");

            }
            this.stackMin.pop();
            return stackData.pop();
        }

        private int getMin() {
    
            if(this.stackMin.isEmpty()){
    
                throw new RuntimeException(" The stack is empty ");
            }
            return this.stackMin.peek();
        }
    }
}

Using queue structure to realize stack

Prepare two queues queue and help,push when , Put the data in queue in

pop when , hold queue In addition to the last one, other data are added to help in , And then queue Data in the poll, Then the two queues exchange ,queue change help,help change queue

peek when , hold queue In addition to the last one, other data are added to help in , And then queue Data in the poll As a return ,poll Output data added to help, Then the two queues exchange ,queue change help,help change queue

package com.zzf.algorithm;

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

/** * @author zzf * @date 2022-01-26 */
public class TwoQueueImplementStack {
    

    public static class TwoQueueStack<T>{
    
        public Queue<T> queue;
        public Queue<T> help;

        public TwoQueueStack(){
    
            queue = new LinkedList<>();
            help = new LinkedList<>();
        }

        public void push(T value){
    
            queue.offer(value);
        }

        public T pop(){
    
            while(queue.size() > 1){
    
                help.offer(queue.poll());
            }
            T ans = queue.poll();
            Queue<T> tmp = queue;
            queue = help;
            help = tmp;
            return ans;
        }

        public T peek() {
    
            while(queue.size() > 1){
    
                help.offer(queue.poll());
            }
            T ans = queue.poll();
            help.offer(ans);
            Queue<T> tmp = queue;
            queue = help;
            help = tmp;
            return ans;
        }

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

Implement queue with stack structure

Prepare two stacks stackPush and stackPop,add when , The data push To stackPush, And then if stackPop If it is empty, put stackPush All in stackPop,poll when , Let's see if we can stackPush Pour into stackPop, And then again pop Out stackPop The data of ,peek Let's see if we can stackPush Pour into stackPop, And then again peek stackPop The data of

package com.zzf.algorithm;

import java.util.Queue;
import java.util.Stack;

/** * @author zzf * @date 2022-01-26 */
public class TwoStacksImplementQueue {
    
    public static class TwoStackQueue{
    
        public Stack<Integer> stackPush;
        public Stack<Integer> stackPop;

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

        //push Stack direction pop Stack pour data 
        private void pushToPop(){
    
            if(stackPop.isEmpty()){
    
                while(!stackPush.isEmpty()){
    
                    stackPop.push(stackPush.pop());
                }
            }
        }

        public void add(int pushInt){
    
            stackPush.push(pushInt);
            pushToPop();
        }

        public int poll(){
    
            if(stackPop.isEmpty() && stackPush.isEmpty()){
    
                throw new RuntimeException(" The queue is empty ");
            }
            pushToPop();
            return stackPop.pop();
        }

        public int peek(){
    
            if(stackPop.isEmpty() && stackPush.isEmpty()){
    
                throw new RuntimeException(" The queue is empty ");
            }
            pushToPop();
            return stackPop.peek();
        }
    }
}