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

This article mainly explains "how to build the stack in the Python data structure and algorithm". Interested friends may wish to have a look. The method introduced in this paper is simple, fast and practical. Let's let the editor take you to learn how to build the stack in Python data structures and algorithms.

What is a stack?

A stack is sometimes called a "push-down stack". It is an ordered collection, adding and removing operations always occur at the same end, that is, the "top" of the stack, and the other end of the stack is called the "bottom". So the newly added element will be removed first, and the closer the element in the stack is to the bottom, the longer it will be in the stack.

This sort principle is called LIFO (last-in first-out), that is, last in, first out. It provides a way to sort based on time in the collection. The most recently added element is near the top, and the old element is near the bottom.

Examples of stacks abound in daily life. Almost all cafes have a stack of trays or plates. You can take one from the top, and the next customer will take the tray or plate below.

Considering the reversal nature of the stack, we can think of some examples when using computers. For example, every browser has a back button. When we jump from one page to another, those pages-- actually URL-- are stored on a stack. The page you are currently browsing is at the top of the stack, while the first page is at the bottom. If you click the back button, you will start browsing these pages in reverse.

Build a stack

As mentioned earlier, a stack is an ordered collection of elements, and both add and remove operations occur on top of it. The operation order of the stack is LIFO, which supports the following operations:

Add an element to the top of the stack

Remove the elements at the top of the stack

Returns the element at the top of the stack

Returns the number of elements in the stack

Having identified the basic features of the stack, we began to build it in code. In object-oriented programming languages (take Python as an example), whenever you need to implement an abstract data type such as stack in Python, it can be implemented by creating a class, and the characteristics and operation methods of the data type can also be implemented by defining methods in the class.

Let's clarify the specific methods of this class:

Create an empty stack. It takes no parameters and returns an empty stack. Stack ()

Add an element to the top of the stack. It requires a parameter item and has no return value. Push (item)

Removes the element at the top of the stack. It takes no parameters, but returns the top element and modifies the contents of the stack. Pop ()

Returns the element at the top of the stack, but does not remove it. It does not require parameters, nor does it modify the contents of the stack. Peek ()

Returns the number of elements in the stack. It takes no arguments and returns an integer. Size ()

Check whether the stack is empty. It takes no parameters and returns a Boolean value. IsEmpty ()

Print the stack / list, which requires no parameters and outputs the contents of the stack. Look ()

Because the stack is a collection of elements, you can take advantage of the powerful, simple native collection provided by Python. Here, we will use the list. The leftmost end of the list will be used to represent the bottom of the stack, and the rightmost will be used to represent the top of the stack:

Class Stack: # define a list / construct a stack def _ _ init__ (self): self.items = [] print ("you created a stack!") Def isEmpty (self): return self.items = = [] def look (self): print (self.items) def push (self, item): self.items.append (item) print ("you added% s"% item) def pop (self): return self.items.pop () def peek (self): return self.items [len (self.items)-1] def size (self): return len (self.items)

The operation of the stack and its return result are shown below:

It is worth noting that you can also choose the head of the list (left) as the top of the stack. In this case, however, you cannot directly use the pop and append methods of the list. Instead, you must use the pop and insert methods of the list to explicitly access the element with the subscript 0, the first element in the list. The following code shows this approach:

Class Stack: def _ init__ (self): self.items = [] def isEmpty (self): return self.items = = [] def look (self): print (self.items) def push (self, item): self.items.insert (0, item) def pop (self): return self.items.pop (0) def peek (self): return self.items [0] def size (self): return len (self.items)

Although both implementations are feasible, there must be differences in performance. The time complexity of both the append and pop methods is o (1), which means that the push and pop operations in the first implementation are completed in a constant amount of time, no matter how many elements there are in the stack. The performance of the second implementation is limited by the number of elements in the stack, because both insert (0) and pop (0) have a time complexity of o (n), and the more elements, the slower.

Obviously, although the two implementations are logically equal, there is a big difference in the amount of time they spend on benchmarking.

At this point, I believe you have a deeper understanding of "how to build the stack in the Python data structure and algorithm". You might as well do it in practice. Here is the website, more related content can enter the relevant channels to inquire, follow us, continue to learn!

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.