Detailed introduction of stack in Python

Catalog 1, Problem Description 2, Solution 3, Conclusion

This article is transferred from WeChat official account: "The Beauty of Algorithm and Programming"

1. Problem description

Python The data types in are list, tuple, dictionary, queue, stack, tree and so on. python built-in data structures such as lists and tuples; Stack and queue need to be defined by ourselves.

A stack is a data structure that only allows insertion and retrieval at one end, which is usually called the top of the stack, the other end is called the bottom of the stack, and the one without data is called the empty stack. Because this data type is defined by ourselves, there are many functions that need to be written by ourselves to realize. So let's look at the function here.

2. Solutions

The basic operations of the stack are: generating the stack, entering the stack, leaving the stack, returning the top element of the stack, judging whether it is an empty stack, and returning the number of elements in the stack.

First, we need to create a stack:

class stack(object):

    def  __init__(self):

         self.__list =  []

What is created here is an empty stack. If you want to detect it, we can also detect whether it is an empty stack through a function:

def is_empty(self):

    return  self.__list == []

    #  return not self.__list

These are two kinds return The detection method can be completed by choosing 1.
Next, the stack is created, and it is known whether the detection stack is empty or not. As the definition says, because the stack is a data structure defined by ourselves and satisfies a last-in-first-out rule, the saving and fetching of elements are naturally different. We call it on-stack and off-stack. The first is to enter the stack. We only need to define one push function:

def push(self,item):

     self.__list.append(item)

Then define a function pop to unstack:

def pop(self):

     self.__list.pop()

The peek function returns the top element of the stack:

def peek(self):

    if  self.__list:

         return self.__list[-1]

    else:

         return None

The size function returns the number of elements in the stack:

def size(self):

    return  len(self.__list)

3. Conclusion

The above is the general usage of this data structure of stack, which is very convenient by defining various functions and then calling them directly when using them.

When defining the functions of the stack, special attention should be paid to the use of keywords inside, such as __list,__init__， The use of the underline, these are the system default, can not be easily changed, otherwise it is easy to make the system error.