@[toc]

Synchronize GitHub here at 👉Github.com/TeFuirnever…

  • Finger Offer (C++ version) series: master table of contents and some instructions for improving efficiency
  • Finger Offer (C++ version) series: repeated numbers in the finger Offer 03 array
  • Sword finger Offer (C++ version) series: sword finger Offer 04 2d array lookup
  • Offer (C++ version) series: Offer 05 replace blank
  • Finger Offer (C++ version) series: finger Offer 06 prints linked lists from end to end
  • Sword finger Offer (C++ version) series: sword finger Offer 07 rebuild binary tree

1, dry

Implement a queue with two stacks and 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 no element exists in the queue, the deleteHead operation returns -1.) Example 1: Input: ["CQueue","appendTail","deleteHead","deleteHead"] [[],[3],[],[]] [NULL, NULL,3,-1] Example 2: Enter [" CQueue deleteHead ", ""," appendTail ", "appendTail", "deleteHead", "deleteHead"] [[], [], [5], [2], [], []] output: [null,-1,null,null,5,2] 1 <= values <= 10000 maximum 10000 calls to appendTail and deleteHeadCopy the code

2. Recursion

Queues are first in, first out and stacks are first in, last out.

Algorithm flow:

  1. AppendTail (int value) adds a value to the stack STK.
  2. Add copy(stack &a, stack &b) to copy elements from stack A to stack B;
  3. DeleteHead () function:
    1. When the stack STK is empty, that is, both stacks are empty, so -1 is returned;
    2. Copy () from STK to cache;
    3. Record the top element of the cache and delete it.
    4. Copy () from cache to STK;
    5. Returns the recorded top element directly.
// Interview question 09. Implementing queues with two stacks
// Standard practice
class CQueue {
public:
	stack<int> stk, cache;
	CQueue() {}void appendTail(int value) {
		stk.push(value);
	}

	void copy(stack<int> &a, stack<int> &b) {
		while (a.size()) {
			b.push(a.top());
			a.pop();
		}
	}

	int deleteHead(a) {
		if (stk.empty())
		{
			return - 1;
		}
		copy(stk, cache);
		int res = cache.top(a); cache.pop(a);copy(cache, stk);
		returnres; }};/** * 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

4. Complexity

/* Insert element time complexity: O(1). Space complexity: O(n). In the worst case, n elements need to be saved. Time complexity of deleting elements: O(n). Space complexity: O(n). In the worst case, n elements need to be saved. * /
Copy the code

— — — — — — — — — — — — — — — — — — —

  • Finger Offer (C++ version) series: master table of contents and some instructions for improving efficiency
  • Finger Offer (C++ version) series: repeated numbers in the finger Offer 03 array
  • Sword finger Offer (C++ version) series: sword finger Offer 04 2d array lookup
  • Offer (C++ version) series: Offer 05 replace blank
  • Finger Offer (C++ version) series: finger Offer 06 prints linked lists from end to end
  • Sword finger Offer (C++ version) series: sword finger Offer 07 rebuild binary tree

— — — — — — — — — — — — — — — — — — –

This article is supported by LeetCode, Niuke, the public ha Oh, Zhihu!

Leetcode-cn.com/u/tefuirnev…

blog.nowcoder.net/wsguanxl

Mp.weixin.qq.com/s/bDwxwQfZy…

www.zhihu.com/people/tefu…