Implement queues 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
  • Most meeting forappendTail,deleteHeadMake 10,000 calls

Review the knowledge

The stack

Stack: A linear LIFO table.

Terms related to stacks:

  • Push – Inserts elements
  • Out of the stack – Removes elements
  • Top of stack – One end that allows elements to be inserted and deleted
  • Bottom of stack – one end of an element cannot be inserted or removed.
  • Top element – The element at the top of the stack.
  • Bottom element – The element at the bottom of the stack.
  • Empty stack — a stack without any data elements.
  • Overflow – continue to be loaded when the stack is full
  • Underflow — continues to unload the stack when it is empty

Stack features:

  • Back in, back out.
  • Inserts and deletions are only allowed at one end of the linear table.

The queue

Queue: A linear first-in, first-out (FIFO) list.

Terms related to queues:

  • Join – Insert elements
  • Out of line – Removes elements
  • Front – One end that allows elements to be deleted
  • Rear – one end of the line that allows insertion of elements
  • Team head element – The element at the head of the team
  • End element – The element at the end of the queue
  • Empty queue – a queue without any data elements

Characteristics of queues:

  1. First in first out
  2. Insert and delete operations are at both ends of the linear table

Circular queue (sequential storage)

A circular queue is formed by connecting the ends of a one-dimensional array of sequentially stored elements in a queue.

Loop queue array subscript: [0~ maxsize-1]

Rear =rear+1 — > rear=(rear+1)%MAXSIZE

Front =front+1 — > front=(front+1)%MAXSIZE

Rear = MAXSIZE – 1 — > (rear+1)%MAXSIZE = front

Front == rear

QueueLength = (rear-front + MAXSIZE) % MAXSIZE

The principle of the above changes: the loss of a cell is not needed, i.e. the loop queue is considered full when the number of elements in the loop queue is MAXSIZE-1. [Using the mold operation to achieve logical cycle structure]

Problem solved by circular queues? Sequential queue spurious overflow

Chain queue

Queues implemented with chained storage structures are called chain queues. A chain queue requires a head pointer and a tail pointer to be uniquely determined. For ease of operation, a header node is appended to the header element, and the header pointer points to the header node.

Array Array operations

The method name role The return value
push() Add elements to the end of the array Array length
pop() Deletes the last item of the array Deleted items
shift() Deletes the first item of the array Returns the deleted item
unshift() Add multiple values at the beginning of the array Returns the length of the new array

Stack behavior: Push () and pop()

Queue behavior: push() and shift()

Simulate queues in opposite directions: push() and unshift()

Answer key

Implement queues with two stacks, that is, you cannot use the Shift () method.

[“CQueue”,”appendTail”,”deleteHead”,”deleteHead”] indicates the method to be executed, left to right.

[[],[3],[],[] correspond to the above methods respectively. The CQueue and deleteHead methods do not need arguments; appendTail is added to pass arguments.

  1. Create a queue and return NULL
  2. Push 3 onto the stack and return NULL
  3. Removes the bottom element from the stack and is returned by the bottom element.
  4. Continue to delete the bottom element of the stack, but return NULL if there are no elements

[null, NULL,3,-1]

According to the characteristics of stack fifo, one stack cannot achieve similar queue fifO operations, so two stacks are used. One stack implements queue entry and the other implements queue exit. When the second stack is empty, the elements of the first stack can be pushed into the second stack, and then fifO can be achieved through the second stack.

class CQueue = function() { this.stack1 = [] this.stack2 = [] } CQueue.prototype.appendTail = function(value) { this.stack1.push(value) return null } CQueue.prototype.deleteHeade = function() { if(! this.stack2.length) { while(! this.stack1.length) { this.stack2.push(this.stack1.pop()) } } if (! (this.stack1.length || this.stack2.length)) { return -1 } return this.stack2.pop() }Copy the code