preface

Before we get into the formal algorithm parsing, let’s fill in the blanks: How do you understand stacks and queues from the ground up?

All data structures can be implemented by arrays and linked lists. In this family of data structures, arrays and linked lists are the foundation of the structure, and other data structures are superstructures based on arrays and linked lists.

For example, the “queue” and “stack” data structures can be implemented using either linked lists or arrays. With array implementation, it is necessary to deal with the problem of capacity expansion and reduction; The linked list implementation does not have this problem, but requires more memory space to store node Pointers.

So what’s the origin of queues and stacks? We all know that stacks are fifin and fifout data structures and queues are fifin and fifout data structures, so we just need to change the causality of queues, that is, the first queue to queue and then queue, so as to become fifin and fifout stack. If you have this idea in your head, it will be easy to solve the following problems.

1.1 Description

Implement MyStack class:

Void push(int x) pushes element x to the top of the stack. Int pop() removes and returns the top element of the stack. Int top() returns the top element of the stack. Boolean empty() Returns true if the stack is empty; Otherwise, return false.

1.2 Ideas and complexity analysis

First we need to declare a queue, not the native queue, we use Deque implementation class LinkedList. The reason why ArrayDeque is not used here is that this problem needs to do a lot of data moving when joining the team. Using arrays with the characteristics of continuous storage space, performance is really touching.

The LinkedList is implemented based on a double-entailed LinkedList and encapsulates the operations commonly used by queues and stacks in a friendly way, as follows:

  • Note: It is recommended to use the specific peekFirst() instead of peek(). This is more readable.

After the queue element, iterate through the queue and fetch the existing element and use the offer method to join the queue. Otherwise, the unstructured call API is ok.

1.3 Interesting Diagram

  • Pictures from the official problem:Leetcode-cn.com/problems/im…

1.4 Code Demonstration

Class MyStack {Deque
      
        queue; /** Initialize your data structure here. */
      
    public MyStack(a) {
        queue = new LinkedList<>();
    }
    
    /** Push element x onto stack. */
    public void push(int x) {
        queue.offer(x);
        for(int i=1; i<=queue.size()-1;i++){
            queue.offer(queue.poll());
        }
        
    }
    
    /** Removes the element on top of the stack and returns that element. */
    public int pop(a) {
        return queue.poll();   
    }
    
    /** Get the top element. */
    public int top(a) {
        return queue.peek();
    }
    
    /** Returns whether the stack is empty. */
    public boolean empty(a) {
        if(! queue.isEmpty())return false;
        return true; }}/** * Your MyStack object will be instantiated and called as such: * MyStack obj = new MyStack(); * obj.push(x); * int param_2 = obj.pop(); * int param_3 = obj.top(); * boolean param_4 = obj.empty(); * /

Copy the code

Day arch a pawn, work does not donate tang.