Using stack to implement queue and using queue to implement stack

How to use stack to realize queue?
The characteristics of the queue are: first in, first out
It can be implemented by two stacks. The top element of stack A is pushed out of the stack and then pushed into stack B. Follow the action until stack A is empty. At this time, the stack top element of stack B is the team head element. The elements in stack B will be out of the queue one by one.

import java.util.ArrayList;

public class MyQueue {
    private ArrayList<Integer> in;
    private ArrayList<Integer> out;

    public MyQueue() {
        in = new ArrayList<Integer>();
        out = new ArrayList<Integer>();
    }

    public void push(int x) {
        in.add(x);
    }

    public int pop() {
        if (out.isEmpty()) {
            int size = in.size();
            for (int i = 0; i < size; i++) {
                int v = in.remove(in.size() - 1);
                out.add(v);
            }
        }

        return out.remove(out.size() - 1);
    }

    public int peek() {
        if (out.isEmpty()) {
            int size = in.size();
            for (int i = 0; i < size; i++) {
                int v = in.remove(in.size() - 1);
                out.add(v);
            }
        }

        return out.get(out.size() - 1);
    }

    public boolean empty() {
        return in.isEmpty() && out.isEmpty();
    }
}

How to implement stack with queue?
The characteristics of the stack are: first in, then out
Call the queue method, take out the first element of the queue and insert it at the end of the queue, so cycling is equivalent to reversing the queue. At this time, the team leader is the top of the stack.

import java.util.LinkedList;

class MyStack {
    private LinkedList<Integer> queue;

    /** Initialize your data structure here. */
    public MyStack() {
        queue = new LinkedList<>();
    }

    /** Push element x onto stack. */
    public void push(int x) {
        queue.addLast(x);
    }

    /** Removes the element on top of the stack and returns that element. */
    public int pop() {
        int size = queue.size();
        for (int i = 0; i < size - 1; i++) {
            int v = queue.pollFirst();
            queue.addLast(v);
        }

        return queue.pollFirst();
    }

    /** Get the top element. */
    public int top() {
        int size = queue.size();
        for (int i = 0; i < size - 1; i++) {
            int v = queue.pollFirst();
            queue.addLast(v);
        }

        int v = queue.pollFirst();
        queue.addLast(v);
        return v;
    }

    /** Returns whether the stack is empty. */
    public boolean empty() {
        return queue.isEmpty();
    }
}

Keywords: Java

Added by gunhoe86 on Mon, 04 Nov 2019 17:48:17 +0200