Sword finger Offer 09 Queue with two stacks

Sword finger Offer 09 Queue with two stacks

Implement a queue with two stacks. The declaration of the queue is as follows. Please implement its two functions appendTail and deleteHead to insert integers at the end of the queue and delete integers at the head of the queue respectively. (if there is no element in the queue, the deleteHead} operation returns - 1)

Example 1:

Input:
["CQueue","appendTail","deleteHead","deleteHead"]
[[],[3],[],[]]
Output:[null,null,3,-1]

Example 2:

Input:
["CQueue","deleteHead","appendTail","appendTail","deleteHead","deleteHead"]
[[],[],[5],[2],[],[]]
Output:[null,-1,null,null,5,2]

Tips:

1 <= values <= 10000
At most appendTail,deleteHead conduct 10000 Call times

Solution 1:

Stack1 is used to store data and stack2 is used to assist in fetching data. When fetching data, if stack1 is empty, it will directly return to - 1. Otherwise, first press all elements into stack2, pop up and record the top elements of stack2, and then press all elements of stack2 back to stack1

 1 class CQueue {
 2 
 3     Stack<Integer> stack1;
 4     Stack<Integer> stack2;
 5 
 6     public CQueue() {
 7         stack1 = new Stack<Integer>();
 8         stack2 = new Stack<Integer>();
 9     }
10     
11     public void appendTail(int value) {
12         stack1.push(value);
13     }
14     
15     public int deleteHead() {
16         // If stack1 Null, return directly-1
17         if(stack1.isEmpty()){
18             return -1;
19         }else{
20             // Otherwise, press all elements into stack2 in
21             while(!stack1.isEmpty()){
22                 stack2.push(stack1.pop());
23             }
24             // Pop up and record stack top elements
25             int top = stack2.pop();
26 
27             // hold stack2 All elements are pressed back stack1
28             while(!stack2.isEmpty()){
29                 stack1.push(stack2.pop());
30             }
31             return top;
32         }
33     }
34 }

The running time of leetcode is 332ms and the space is 46.7mb. This time is terrible

Complexity analysis:

Time complexity: the complexity of inserting elements is O(1), and the complexity of deleting elements is O(2n)

Space complexity: two stacks, so it is O(2n)

Solution 2:

Idea source: https://leetcode-cn.com/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof/solution/mian-shi-ti-09-yong-liang-ge-zhan-shi-xian-dui-l-3/597550

Two stacks, one for storage and one for retrieval. The sum of the elements of the two stacks is equal to all the current elements. Stack2 is not an auxiliary stack for fetching elements, but is specially used for fetching elements. When fetching elements, first judge whether stack2 is empty. If it is empty, move all elements in stack1 to stack2. At this time, the arrangement order of elements from the top to the bottom of stack2 is the order of fetching elements in the future

 1 class CQueue {
 2 
 3     Stack<Integer> stack1;
 4     Stack<Integer> stack2;
 5 
 6     public CQueue() {
 7         stack1 = new Stack<Integer>();
 8         stack2 = new Stack<Integer>();
 9     }
10     
11     public void appendTail(int value) {
12         stack1.push(value);
13     }
14     
15     public int deleteHead() {
16         if(stack2.isEmpty()){
17             while(!stack1.isEmpty()){
18                 stack2.push(stack1.pop());
19             }
20         }
21         if(stack2.isEmpty()){
22             return -1;
23         }else{
24             // If it is not empty, return directly stack2 Stack top element
25             return stack2.pop();
26         }
27     }
28 }

The running time of leetcode is 55ms and the space is 46.5mb. This time is much better

Complexity analysis:

Time complexity: the time of saving elements is O(1). Although it is sometimes necessary to copy all elements of stack1 to stack2, each element will only be put into and out of stack2 once, so the average time of taking elements is also O(1)

Space complexity: two stacks, one for storage and one for retrieval. The sum of the elements of the two stacks is equal to all the current elements, so the space complexity is O(n)

 

Tags: Algorithm

Posted by anothersystem on Sat, 14 May 2022 05:02:52 +0300