Stacks and queues – one week hot

First, stack

Stack top (top) stack bottom (bottom)

After the advanced, from the top of the stack insert, remove from the top of the stack.

Sequential stack: Stores elements from the bottom of the stack to the top of the stack at one time with a set of sequential storage units with top stack top pointers attached

　　Initialization: first allocate a space of the specified size and expand it by space after the space is insufficient.

　　base The bottom pointer of the stack always points to the bottom of the stack.

　　top The top pointer of the stack always points to the next position of the top element of the stack.

　　base = top Express stack space

　　base == null Indicates that stack structure does not exist.

Two. Queue

FIFO

Delete from team header (front) and insert from queue end (rear).

Double ended queue, which limits input and output to both ends (or ends).

Chain queue, linked list, head pointer, tail pointer.

　　The head pointer points to the head element, and the tail pointer points to the next position of the queue element.

　　Queue empty, team header pointer and tail pointer to the same element.

1.Implementing a queue with two stacks

    //Two queues are used to implement a queue and finish the queue and team operation.
    Stack<Integer> stack1 = new Stack<Integer>();
    Stack<Integer> stack2 = new Stack<Integer>();
    
    public void add(int node) {
        stack1.push(node);//
    }
    
    public int remove() {
        if(stack1.isEmpty() && stack2.isEmpty()){
            System.out.println("Queue is empty.);
            return 0;
        }else{
            if(stack2.isEmpty()){
                while(! stack1.isEmpty()){
                    stack2.push(stack1.pop());
                }
                return stack2.pop();
            }else{
                return stack2.pop();
            }
        }
        
    }

2.Implementing a stack with two queues

    //Using two queues to achieve a stack, bent into stack stack and stack operation.
    Queue<Integer> queue1 = new LinkedBlockingQueue<Integer>();
    Queue<Integer> queue2 = new LinkedBlockingQueue<Integer>();
    public int pop(){
        //When you leave the stack, each time you leave the stack, you should move the last element in one queue to another, so at any time, there is a queue that is empty
        if(queue1.isEmpty() && queue2.isEmpty()){
            //The two queues are empty.
            System.out.println("The stack is empty.);
            return 0;
        }else{
            Queue<Integer> queueEmpty = queue1.isEmpty()?queue1:queue2;//Record the empty queue.
            Queue<Integer> queueNotEmpty = queue2.isEmpty()?queue1:queue2;//Record the queue that is not empty.
            while(!queueNotEmpty.isEmpty()){
                int key = queueNotEmpty.poll();//Delete an element from the queue header//After deletion, determine whether the queue is empty, if it is empty, prove that this is the last element of the queue, that is, the stack needs to pop-up elements?
                if(queueNotEmpty.isEmpty()){
                    return key;
                }else{
                    queueEmpty.add(key);
                }
                
            }
            return 0;
        }
        
    }
    public void push(int key){
        queue1.add(key);
    }

Leave a Reply Cancel reply