How to do stack analysis including functions

This article shows you how to carry out stack analysis including functions, the content is concise and easy to understand, can definitely brighten your eyes, through the detailed introduction of this article, I hope you can get something.

To define the data structure of the stack, implement a min function in this type that can get the smallest elements of the stack. In this stack, the time complexity of calling min, push, and pop is O (1).

Example:

MinStack minStack = new MinStack ()

MinStack.push (- 2)

MinStack.push (0)

MinStack.push (- 3)

MinStack.min ();-- > returns-3.

MinStack.pop ()

MinStack.top ();-- > returns 0.

MinStack.min ();-- > returns-2.

Tip:

The total number of calls to each function does not exceed 20000

Ideas for solving the problem:

1. Note that this question is the stack, which needs to be distinguished from the queue.

2. Maintain a minimum stack

3Gore push discards if the current element is smaller than the element at the top of the minimum stack, otherwise insert

4 if the top element of the stack is equal to that of the minimum stack, then the stack will be released at the same time.

5. Pay attention to the details. The element is equal to the element at the top of the minimum stack.

Review the title of the queue.

1, a minimum double-ended queue needs to be maintained

2. Every time you join the queue, look from back to front, find the element smaller (larger) than the inserted element, discard the element behind the queue, and insert the current element.

Code implementation

Type MinStack struct {data [] int minData [] int}

/ * initialize your data structure here. * / func Constructor () MinStack {return MinStack {}}

Func (this * MinStack) Push (x int) {this.data=append (this.data,x) if len (this.data) = = 1 {this.minData=append (this.minData,x) return} l:=len (this.minData) if x