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 for
appendTail
,deleteHead
Make 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:
- First in first out
- 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.
- Create a queue and return NULL
- Push 3 onto the stack and return NULL
- Removes the bottom element from the stack and is returned by the bottom element.
- 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