“This is the 22nd day of my participation in the August Gwen Challenge.

Topic describes

Implement a queue with two stacks. Implement appendTail and deleteHead to insert an integer at the end of the queue and delete an integer at the head of the queue. (If there are no elements in the queue, the deleteHead operation returns -1)

Example 1:

Input: [" CQueue appendTail ", ""," deleteHead ", "deleteHead"] [[], [3], [], []] output: [3, null, null, 1]Copy the code

Example 2:

Input: [" CQueue deleteHead ", ""," appendTail ", "appendTail", "deleteHead", "deleteHead"] [[], [], [5], [2], [], []] output: [null, 1, null, null, 5, 2]Copy the code

Tip:

  • 1 <= values <= 10000
  • At most 10000 calls are made to appendTail and deleteHead

Answer key

Method 1: double stack

Ideas and Algorithms

Two stacks are maintained, the first supporting insert and the second supporting delete.

The bottom of the first stack is the last element to be added, and the top element of the child stack is the next element to be removed. In order to maintain the queue first in first out feature, we introduce a second stack, with a second stack maintenance to delete elements, delete operations in the implementation of the time we first to see if the second stack is empty, if it is not empty, we will be the first element in the stack pop-up inserted into the second stack, so that the second order of elements in the stack is to delete the order of the elements, To perform the delete operation we simply pop the second stack element return.

Member variables

  • Maintain two stacksstack1 和 stack2, includingstack1Support for insert operations,stack2Delete operations

A constructor

  • Initialize thestack1 和 stack2Is empty

Insert elements

Insert element corresponding method appendTail

  • stack1Insert elements directly

Remove elements

Deleting an element corresponds to method deleteHead

  • ifstack2Is empty, then willstack1All elements in the pop-up insert tostack2 里
  • ifstack2If it is still empty, return- 1, or fromstack2Pops up an element and returns

code

class CQueue { Deque<Integer> stack1; Deque<Integer> stack2; public CQueue() { stack1 = new LinkedList<Integer>(); stack2 = new LinkedList<Integer>(); } public void appendTail(int value) { stack1.push(value); } public int deleteHead() {// If (stack2.isempty ()) {while (! stack1.isEmpty()) { stack2.push(stack1.pop()); } } if (stack2.isEmpty()) { return -1; } else { int deleteItem = stack2.pop(); return deleteItem; }}}Copy the code

Personal understanding

  1. Individual tests can also be performed successfully using Stack, but Stack is a JDK 1.0 descendant of Vector, and Vector is no longer recommended, so Stack is also not recommended. I didn’t know that.
  2. Deque: Deque is inherited from Queue. A Deque in Java, short for “Double ended Queue”, is a collection of double-ended queues in Java. The Deque has the FIFO function of a normal queue, but it also has the LIFO function of Stack, and retains the push and pop functions, so it should be no obstacle to use.
  3. ArrayDeque: A concrete implementation of the Deque interface that relies on mutable arrays. ArrayDeque has no capacity limit and can be automatically expanded on demand. An ArrayDeque can be used as a Stack, more efficiently than a Stack. Arraydeques can also be used as queues, and are more efficient than linkedLists based on two-way lists. Note that ArrayDeque does not support null elements.
  4. Note that the type is added to the declarationIntegert.
  5. Test discovery useArrayDequeCan also.

Complexity analysis

  • Time complexity: For insert and delete operations, the time complexity is O(1). Insert doesn’t say much. For delete operations, which may seem O(N) time, consider that each element is only “inserted and popped at most.stack2“, so the time complexity for each element to be deleted is still O(1).
  • Space complexity O(N) : Need to use two stacks to store existing elements.

source

Source: LeetCode link: leetcode-cn.com/problems/yo…