This is the sixth day of my participation in the August More text Challenge. For details, see:August is more challenging

Topic describes

Implement a queue with two stacks. The queue is declared as follows. Implement its two appendTail and deleteHead functions that insert integers at the end of the queue and delete integers at the head of the queue, respectively. (If there are no elements in the queue, deleteHead returns -1)

 

Example 1: Input: ["CQueue","appendTail","deleteHead","deleteHead"] [[],[3],[]] Output: [NULL, NULL,3,-1] Source: LeetCode Link: https://leetcode-cn.com/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof copyright belongs to collar network. Commercial reprint please contact the official authorization, non-commercial reprint please indicate the source.Copy the code

Thought analysis

  • A stack, also known as a stack, is a linear table with limited operations. A linear table that is restricted to insert and delete operations only at the end of the table.
  • Queue is a special kind of linear table. What is special is that it only allows deletion in the front of the table and insertion in the rear of the table. Like stack, queue is a linear table with limited operation.
  • Stack and queue are common data structures. Stack is characterized by LIFO(last-in-first-out) and queue by FIFO (first-in-first-out).
  • The queue can be implemented using two stacks. The code is as follows.

code

class CQueue {
    
    Stack<Integer> headStack; 
    Stack<Integer> tailStack; 

    public CQueue(a) {
        headStack = new Stack<>();
        tailStack = new Stack<>();
    }
    
    public void appendTail(int value) {
        headStack.push(value);
    }
    
    public int deleteHead(a) {
        if (tailStack.isEmpty()) {
            while (!headStack.isEmpty()) {
                tailStack.push(headStack.pop());
            }
        }

        if(! tailStack.isEmpty()) {int ans = tailStack.pop();
            return ans;
        }
        
        return -1; }}/** * Your CQueue object will be instantiated and called as such: * CQueue obj = new CQueue(); * obj.appendTail(value); * int param_2 = obj.deleteHead(); * /
Copy the code

conclusion

  • In practice, we use ArrayDeque.Deque“Double Ended queue” means “double ended queue”, which can be used as either a stack or a queue.ArrayDequeThe bottom layer is implemented through an array. In order to satisfy the requirement that elements can be inserted or deleted at both ends of the array, the array must also be looping, i.eCircular Array (circular Array)That is, any point in the array can be viewed as either the starting point or the ending point.
  • Stick to a daily question, come on!