Shulou(Shulou.com)06/03 Report--

This article mainly introduces "how to use PHP to solve a stack". In daily operation, I believe many people have doubts about how to use PHP to solve a stack problem. Xiaobian consulted all kinds of data and sorted out a simple and easy-to-use method of operation. I hope it will be helpful for you to answer the doubt of "how to solve a stack with PHP". Next, please follow the editor to study!

Preface

Come across an interview question, the general meaning of the question is as follows:

Two ordinary stacks are used to implement a special stack, so that the operations of the three functions pop, push and min are all O (1), and the min function is to get the minimum value of the current stack.

Preliminary idea

1. To implement the min function for operation (1), the first idea was to calculate the current minimum in advance, so you would think of using a value to hold the minimum value element in the current stack, and then maintaining that value during the push and pop operations. So min,push is O (1), but pop is not. If the current pop-up is the minimum value, you need to find the minimum value of the current element again, this is not o (1).

two。 And the above method does not use another stack, so it comes to mind that the ordered elements are stored in one stack, and the ordered stack is also maintained in push and pop operations, as shown in the figure:

But in this case, the min operation is O (1), but the push and pop operations can never think of a method with O (1) complexity because they want to maintain this ordered stack.

At that time, I thought I must be caching the minimum information in another stack, but I don't know if it was because I didn't eat or something, so my mind froze.

Correct solution

When I encountered a problem that could not be solved, I felt very uncomfortable, so when I ate, I began to think about how to fully reason the characteristics of the stack and effectively cache the minimum information so that the min operation could use it.

The biggest feature of stack operations is that you can only manipulate the elements at the top of the stack, so it's not just right to think of the minimum value of each stack operation with an auxiliary stack cache. In this way, each pop operation, both sides pop up together; because the stack top element of the auxiliary stack is the minimum value in the current stack, the push operation only needs to compare the stack element and the auxiliary stack top element. In this way, push, pop and min are all O (1) operations. As shown in the figure:

The text may not be clear, the code below is the implementation of PHP, which simulates the stack through an array.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.