current position:Home>[Python data structure series] "stack (sequential stack and chain stack)" -- Explanation of knowledge points + code implementation

[Python data structure series] "stack (sequential stack and chain stack)" -- Explanation of knowledge points + code implementation

2022-01-30 05:33:18 Vax_ Loves_ one thousand three hundred and fourteen

Soul torture : Why study data structure ?

data structure , Understand directly , It's about studying how data is stored . Data storage has only one purpose , In order to facilitate the later reuse of data . therefore , The storage of data in computer storage space , It's not random , This requires us to choose a good way to store data , And that's the core of data structure . so to speak , Data structure is the basis of all programming . Learning data structures is learning an idea : How to transform the real problem into the representation of computer language . For friends who study computer , Learning data structure is the basic skill . For non computer majors , But in the future, I want to go to data analysis 、 Big data 、 Or in Python For friends who can make a big leap in the use of , Learning data structure is a very important exercise of logical thinking ability , Looking for a job 、 Occupation development 、 Problem solving and other aspects can be of great help .

@TOC

data structure —— Stack ( Sequence stack and chain stack )

Chapter one The basics of stack

  Stacks and queues , Strictly speaking , Also belong to The linear table , Because they are also used to store logical relationships as " one-on-one " The data of . Use Stack Structure stores data , Stress “ First in, then out ”, That is, the data that goes into the stack first , Finally, the stack ; Use queue Store the data , Stress " fifo ", That is, the data of the most advanced queue , Also first out of the queue . Since both stacks and queues belong to linear tables , According to the characteristics of linear list, it is divided into sequential list and linked list , Stacks can also be divided into Order of the stack and Chain stack , Queues are also divided into Sequential queue and Chain queue , These contents will be explained in detail in this chapter .

1. Stack storage structure

1.1 The basic introduction of stack

   Same as The order sheet and Linked list equally , Stacks are also used to store logical relationships for " one-on-one " Linear storage structure of data , Pictured 1 Shown .

Image Name      From the picture 1 We see , The stack storage structure is different from the linear storage structure , This is due to stack versus data " save " and " take " The process has special requirements :

  (1) The stack can only access data from one end of the table , The other end is closed , Pictured 1 Shown ;

  (2) In the stack , Whether it's storing data or fetching data , All of them must be followed " First in, then out " Principles , That is, the first element to stack and the last one to stack . Take a picture 1 In terms of stack , From the storage state of the data in the figure, we can judge , Elements 1 It's the most advanced stack . therefore , When you need to take elements out of the stack 1 when , according to " First in, then out " Principles , Elements need to be added in advance 3 And elements 2 Take it out of the stack , Then we can extract the elements successfully 1.    therefore , We can define the stack , That is, stack is a method that can only access data from one end of the table and follow " First in, then out " Principle of linear storage structure .

   Usually , The open end of the stack is called To the top of the stack ; Accordingly , The sealing end is called At the bottom of the stack . therefore , Top element of stack It refers to the element closest to the top of the stack , Take a picture 2 Come on , The top element of the stack is the element 4; Empathy , Stack bottom element Refers to the element at the bottom of the stack , chart 2 The bottom element in the stack is the element 1.

Image Name

1.2 In and out of the stack

  Based on the characteristics of stack structure , in application , Usually only two operations are performed on the stack :

  (1) Add elements to the stack , This process is called " Into the stack "( Push or push );

  (2) Extract the specified element from the stack , This process is called " Out of the stack "( Or play the stack );

1.3 The specific implementation of stack

Is a kind of the stack " special " Linear storage structure of , Therefore, there are two ways to implement the stack :

  (1) Order of the stack : Using sequential storage structure can simulate the characteristics of stack data storage , So as to realize the stack storage structure ;

  (2) Chain stack : Using chain storage structure to realize stack structure ;        The difference between the two implementations , Only the relative location of data elements in the actual physical space , Array is used at the bottom of sequence stack , Chain list is used at the bottom of chain stack . The specific implementation of sequence stack and chain stack will be explained in detail in subsequent chapters .

1.4 The application of the stack

Data access is based on stack structure " First in, then out " The characteristics of the principle , It can be used to achieve many functions .       for example , We often use browsers to find information on various websites . Suppose you browse the page first A, Then close the page A Jump to page B, Then close the page B Jump to the page C. And then , If we want to go back to the page A, There are two choices :

  (1) Re search found page A;

  (2) Using the browser " Back off " function . The browser will first go back to the page B, Then go back to the page A.      browser " Back off " Function realization , The bottom layer uses the stack storage structure . When you close the page A when , The browser will the page A Push ; Again , When you close the page B when , The browser will also B Push . therefore , When you perform a fallback operation , The first thing you see is the page B, Then the page A, This is the effect of data in the stack coming out of the stack in turn .

   More Than This , Stack storage structure can also help us detect bracket matching problems in code . Most programming languages use parentheses ( parentheses 、 Brackets and braces ), Incorrect use of parentheses ( Usually lose the right parenthesis ) Will cause program compilation errors , Many development tools have the function of detecting whether the code has editing errors , This includes detecting the matching of parentheses in the code , The underlying implementation of this function uses the stack structure .

   meanwhile , The stack structure can also realize the hexadecimal conversion of values . for example , Write a program to realize the automatic conversion from decimal number to binary number , You can use the stack storage structure to realize .

2. Sequence stack and basic operation ( Including in stack and out stack )

2.1 The basic introduction of sequence stack

   Order of the stack , The box The order sheet Implement stack storage structure . We know from the previous study that , Using stack storage structure to manipulate data elements must comply with " First in, then out " Principles , This section is about " How to use the sequence table to simulate the stack and realize the basic operation of the data in the stack ( Out of stack and in stack )" Give you a detailed introduction .

   If you look closely at the sequence table ( The underlying implementation is Array ) And stack structure will find , They store data in a highly similar way , However, the stack has special restrictions on the access process of data , The sequence table does not .

   for example , Let's start with a sequence table (a Array ) Storage {1,2,3,4}, The storage status is shown in the figure 1 Shown :

Image Name

   Again , Use the stack storage structure to store {1,2,3,4}, The storage status is shown in the figure 2 Shown :

Image Name

   Pass diagram 1 Sum graph 2 It is not difficult to see the comparison between , Using the sequence table to simulate the stack structure is very simple , Just take the data from a The array index is zero 0 The locations of the are stored in turn .

   Subscript from array to 0 It is a common method to store data in the simulation stack , It is also possible to store data from other array subscripts , This is just for beginners to understand .

   After understanding the data stored in the sequence table simulation stack , Next, let's look at how to simulate the out of stack operation of elements in the stack . Because the stack has a certain influence on the order of storage elements out of the stack " First in, then out " The requirements of , If you want to put the figure 1 The elements stored in 1 Take it out of the stack , You need to add the element first 4、 Elements 3 And elements 2 Take them out of the stack in turn .

   Here is a common implementation idea of using sequence table to simulate stack storage structure , That is, set a real-time variable pointing to the top element of the stack in the sequence table ( It is generally named top),top The initial value is -1, Indicates that no data elements are stored in the stack , And stack is " Empty stack ". Once there are data elements on the stack , be top Just do it +1 operation ; conversely , If the data element is out of the stack ,top Just do it -1 operation .

2.2 Sequential stack elements " Push "

   such as , Or simulate stack storage {1,2,3,4} The process of . first , The stack is " Empty stack ", That is, the array is empty ,top The value is the initial value -1, Pictured 3 Shown :

Image Name

   First, add elements to the stack 1, Our default array subscript is 0 One end represents the bottom of the stack , therefore , Elements 1 Stored in an array a[1] It's about , meanwhile top value +1, Pictured 4 Shown :

Image Name

   In the above way , Store the elements in turn 2、3 and 4, Final ,top Value to 3, Pictured 5 Shown :

Image Name

2.3 Sequential stack elements " Out of the stack "

   Actually ,top The effect of variable setting on analog data " Push " There is no practical help , It is for the realization of data " Out of the stack " Prepare for operation .

   such as , Map 5 The elements in 2 Out of the stack , You need to put the element 4 And elements 3 Stack one by one . It should be noted that , When there is data out of the stack , To put top do -1 operation . therefore , Elements 4 And elements 3 The process of getting out of the stack is shown in the figure 6a) and 6b) Shown :

Image Name

   Be careful , chart 6 The disappearance of elements in the array is only for the convenience of beginners , Actually , All we need here is top Values do -1 Just operate , because top The value itself represents the top position of the stack , therefore top-1 It is equivalent to the stack top element out of the stack . And when you add elements to the stack later , The new element will be stored in similar elements 4 Such old elements are located , Overwrite old elements .

About sequential stack Python Programming code can refer to ↓( Personal writing , For reference only , We welcome valuable suggestions )

Task a : Representation and implementation of sequential stack ( difficulty :*)

Realize basic functions :( Including but not limited to , You can continue to expand according to your ability )

  (1) initialization Empty stack

  (2) Judgment stack Is it empty

  (3) return Top element of stack

  (4) Returns the of the stack length

  (5) Into the stack ( Also known as pressure stack 、 Push )

  (6) Out of the stack

  (7) Empty stack

Code implementation :

#!/usr/bin/env python
# -*- coding: utf-8 -*- 
# @Time : 2021/7/27 13:52 
# @Author : vaxtiandao
# @File : sqStack_21.py

# -*-coding:utf-8-*-

#  Define the order stack 
class sqStack:
    #  Initialization stack 
    def __init__(self, MAXSIZE):
        self.MAXSIZE = MAXSIZE
        self.data = [None] * self.MAXSIZE
        self.top = -1

    #  Judge whether the current stack is empty 
    def is_empty(self):
        return self.top == -1

    def gettop(self):
        if self.is_empty():
            print(" The current sequence stack is empty ")
            return None
        else:
            return self.data[self.top]

    #  Push 
    def Push(self, item):
        #  Determine whether the stack is full 
        if self.top == self.MAXSIZE - 1:
            return "sqStack is full."
        self.data[self.top+1] = item
        self.top += 1

    #  List stack 
    def ListPush(self, x):
        #  Determine whether the stack is full 
        if self.top == self.MAXSIZE - 1:
            return "sqStack is full."
        for i in range((len(x))):
            self.Push(x[i])

    #  Out of the stack 
    def Pop(self):
        #  Judge whether the stack is empty 
        if self.is_empty():
            return "sqStack is empty"
        rs = self.data[self.top]
        self.top -= 1
        return rs

    #  The length of the output stack 
    def size(self):
        return self.top + 1

    #  Output stack elements 
    def display(self):
        #  Judge whether the stack is empty 
        if self.is_empty():
            print(" The current sequence stack is empty ", end=" ")
        else:
            print(" The current linked list element is :", end="")
        for i in range(self.top+1):
            print(self.data[i], end=" ")
        print()

    #  Empty stack 
    def clear(self):
        self.data = [None] * self.MAXSIZE
        self.top = -1


if __name__ == '__main__':
    print('---------------------------------')
    #  Initializes a length of 20 Sequential stack 
    s = sqStack(20)
    print(" Initialization stack :", s)
    print('---------------------------------')
    #  Judge whether the current stack is empty 
    print(" Whether the current stack is empty :", s.is_empty())
    print('---------------------------------')
    #  Output stack elements 
    s.display()
    print('---------------------------------')
    print(" Before entering the stack, the elements in the stack :", end="")
    s.display()
    #  Push 
    s.Push(1)
    s.Push(10)
    s.Push(100)
    #  Output the elements in the current stack 
    print(" After entering the stack, the elements in the stack :", end="")
    s.display()
    print('---------------------------------')
    print(" The current stack length is :", s.size())
    print('---------------------------------')
    print(" Before the queue is put on the stack, the elements in the stack :", end="")
    s.display()
    s.ListPush([1, 2, 3, 4])
    print(" After the queue is stacked, the elements in the stack :", end="")
    s.display()
    print('---------------------------------')
    print(" The current stack top element is :", s.gettop())
    print('---------------------------------')
    #  Top element out of stack 
    print(" Before leaving the stack, the elements in the stack :", end="")
    s.display()
    print(" The out of stack element is :", s.Pop())
    print(" After leaving the stack, the elements in the stack :", end="")
    s.display()
    print('---------------------------------')
    #  Output the elements in the current stack 
    s.display()
    print('---------------------------------')
    s.clear()
    s.display()
    print('---------------------------------')

 Copy code 

Realization effect :  Insert picture description here

3. Chain stack and basic operation ( Including in stack and out stack ) Detailed explanation

3.1 Basic introduction of chain stack

   Chain stack , The box Linked list Realization Stack storage structure .

   The implementation idea of chain stack is similar to that of sequential stack , The sequential stack is to count The order sheet ( Array ) One end is the bottom of the stack , The other end is the top of the stack ; So is the chain stack , Usually we use the head of the list as the top of the stack , Tail as bottom of stack , Pictured 1 Shown : Image Name    Take the head of the list as one end of the top of the stack , Avoid implementing data " Push " and " Out of the stack " Do a lot of time-consuming operations to traverse the linked list during operation .

The head of the list serves as the top of the stack , signify :

  (1) Implementing data " Push " In operation , Data needs to be inserted from the head of the linked list ;

  (2) Implementing data " Out of the stack " In operation , You need to delete the first element node of the linked list header ;   therefore , In fact, a chain stack is a chain list that can only insert or delete data by using the head insertion method .

3.2 Chain stack elements into the stack

   for example , Put the element 1、2、3、4 Stack in turn , It is equivalent to adding each element to the linked list by header insertion , The addition process of each data element is shown in Figure 2 Shown :

Image Name

3.3 Chain stack element out of stack

   for example , chart 2e) In the chain stack shown in , To add an element 3 Out of the stack , according to " First in, then out " Principles , You have to put the element 4 Out of the stack , That is to remove from the linked list , And then the elements 3 To get out of the stack , The whole operation process is shown in Figure 3 Shown :

Image Name About chain stack Python Programming code can refer to ↓( Personal writing , For reference only , We welcome valuable suggestions )

Task 2 : Representation and implementation of chain stack ( difficulty :**)

Realize basic functions :( Just like the sequence stack )

  (1) initialization Empty stack

  (2) Judgment stack Is it empty

  (3) return Top element of stack

  (4) Returns the of the stack length

  (5) Into the stack ( Also known as pressure stack 、 Push )

  (6) Out of the stack

  (7) Empty stack

#!/usr/bin/env python
# -*- coding: utf-8 -*- 
# @Time : 2021/7/27 14:47 
# @Author : vaxtiandao
# @File : liStack.py

#  Define the chain stack node 
class Node(object):
    #  Initializing the chain stack 
    def __init__(self, data):
        self.data = data
        self.next = None


#  Define chain stack 
class linkstack(object):

    #  Initializing the chain stack 
    def __init__(self):
        self.top = None

    #  Judge whether the chain stack is empty 
    def is_empty(self):
        return self.top == None

    #  Empty the chain stack 
    def clear(self):
        self.top = None

    #  Returns the length of the current stack 
    def size(self):
        i = 0
        tempnode = self.top
        while tempnode is not None:
            tempnode = tempnode.next
            i += 1
        return i

    #  Element stack 
    def push(self, item):
        node = Node(item)
        node.next = self.top
        self.top = node

    #  Stack top element out of stack 
    def pop(self):
        x = self.top.data
        self.top = self.top.next
        return x

    #  Get stack top element 
    def gettop(self):
        return self.top.data

    #  Output the elements in the current stack 
    def display(self):
        if self.top == None:
            print(" The element in the current stack is empty ", end="")
        else:
            print(" The current stack element is :", end="")
        tempnode = self.top
        while tempnode is not None:
            print(tempnode.data, end=" ")
            tempnode = tempnode.next
        print()


if __name__ == "__main__":
    print("-----------------------")
    s1 = linkstack()
    print(" The initialized stack is :", s1)
    print("-----------------------")
    print(" The chain stack elements before entering the stack are :", end="")
    s1.display()
    s1.push(1)
    s1.push(2)
    s1.push(3)
    s1.push(4)
    s1.push(5)
    s1.push(6)
    print(" The chain stack element after stacking is :", end="")
    s1.display()
    print("-----------------------")
    print(" The current stack top element is :", s1.gettop())
    print("-----------------------")
    print(" The length of the current chain stack is :", s1.size())
    print("-----------------------")
    print(" The chain stack element before the stack is :", end="")
    s1.display()
    print(" The out of stack element is :", s1.pop())
    print(" The chain stack element after the stack is :", end="")
    s1.display()
    print("-----------------------")
    print(" The chain stack element before emptying is :", end="")
    s1.display()
    s1.clear()
    print(" The empty chain stack element is :", end="")
    s1.display()
    print("-----------------------")
    print(" Whether the current chain stack is empty :", s1.is_empty())
    print("-----------------------")

 Copy code 

Realization effect :  Insert picture description here

4. The application of the stack ( difficulty :**)

application 1: Bracket matching problem

   The verification algorithm uses a stack , Whenever you read in an open parenthesis , Then push directly , Wait for matching similar closing parentheses ; Whenever you read in a closing parenthesis , If the type is the same as the left bracket at the top of the current stack , Then the two match , Take the left bracket at the top of the stack out of the stack , Until the expression is scanned .

   During processing , Also consider the case of mismatched parentheses and errors . for example , When there is a (()[]) In this case , Since the left parenthesis in front of the stack are known to match the right parenthesis in the back , Stack empty , Therefore, the last scanned right parenthesis cannot be matched ; appear [([]) Such mistake , When the expression scan ends , There is also an open bracket in the stack that does not match ; appear (()] This error is obviously that the left bracket at the top of the stack does not match the last right bracket .

Test cases :( Partners need to take the following three cases to test their own code !)    Case study 1:{{([][])}()}    Case study 2:[[{{(())}}]]    Case study 3:[[(()(()))])]{}

Running results

Image Name About this problem, the programming code can refer to ↓( Personal writing , For reference only , We welcome valuable suggestions )

#!/usr/bin/env python
# -*- coding: utf-8 -*- 
# @Time : 2021/7/28 10:14 
# @Author : vaxtiandao
# @File : ds_parentMatching.py


#  Define the order stack 
class sqStack:
    #  Initialization stack 
    def __init__(self, MAXSIZE):
        self.MAXSIZE = MAXSIZE
        self.data = [None] * self.MAXSIZE
        self.top = -1

    #  Judge whether the current stack is empty 
    def is_empty(self):
        return self.top == -1

    def gettop(self):
        if self.is_empty():
            print(" The current sequence stack is empty ")
            return None
        else:
            return self.data[self.top]

    #  Push 
    def Push(self, item):
        #  Determine whether the stack is full 
        if self.top == self.MAXSIZE - 1:
            return "sqStack is full."
        self.data[self.top + 1] = item
        self.top += 1

    #  List stack 
    def ListPush(self, x):
        #  Determine whether the stack is full 
        if self.top == self.MAXSIZE - 1:
            return "sqStack is full."
        for i in range((len(x))):
            self.Push(x[i])

    #  Out of the stack 
    def Pop(self):
        #  Judge whether the stack is empty 
        if self.is_empty():
            return "sqStack is empty"
        rs = self.data[self.top]
        self.top -= 1
        return rs

    #  The length of the output stack 
    def size(self):
        return self.top + 1

    #  Output stack elements 
    def display(self):
        #  Judge whether the stack is empty 
        if self.is_empty():
            print(" The current sequence stack is empty ", end=" ")
        else:
            print(" The current linked list element is :", end="")
        for i in range(self.top + 1):
            print(self.data[i], end=" ")
        print()

    #  Empty stack 
    def clear(self):
        self.data = [None] * self.MAXSIZE
        self.top = -1


def matching(strings):  #  The input is a string of characters 
    bktStack = sqStack(60)  #  Create class instances 
    flag = 1
    opens = "{[("
    closes = "}])"
    #  For each input character 
    for i in strings:
        #  Left parenthesis encountered , Just put it on the stack 
        if i in opens:
            bktStack.Push(i)
        #  Right parenthesis encountered 
        elif i in closes:
            #  If there is no left bracket to match 
            if bktStack.is_empty():
                #  Mismatch , end 
                return False
            #  In what order are the left parentheses entered , The right parentheses should be eliminated in reverse order .
            #  If the match , The closing bracket always eliminates the top bracket of the stack .
            #  Bomb stack bktStack.pop(), Judge whether the left bracket at the top of the stack matches the current right bracket 
            if closes.index(i) != opens.index(bktStack.Pop()):
                #  Mismatch , end 
                return False
    #  If you haven't return Instead, I went through it , And no extra left parentheses are left on the stack , It means match . And vice versa .
    return bktStack.is_empty()


#  The judgment returns True still False
def check(strings):
    if matching(strings):
        print("%s  The match is correct !" % strings)
    else:
        print("%s  Matching error !" % strings)

if __name__ == "__main__":
    #  Test functions 
    for i in range(4):
        stringa = input()
        check(stringa)

 Copy code 

Realization effect :  Insert picture description here

application 2: Decimal to binary

   When a decimal integer M When converting to binary numbers , During calculation , hold M And 2 The bits of the binary number obtained from the remainder are put on the stack in turn , After calculation, the binary numbers in the stack are output out of the stack in turn , The output result is the binary number to be obtained .

Test cases :   [200, 254, 153, 29, 108, 631, 892]

Running results

Image Name About this problem, the programming code can refer to ↓( Personal writing , For reference only , We welcome valuable suggestions )

#!/usr/bin/env python
# -*- coding: utf-8 -*- 
# @Time : 2021/7/28 10:31 
# @Author : vaxtiandao
# @File : ds_10to2.py


#  Define the order stack 
class sqStack:
    #  Initialization stack 
    def __init__(self, MAXSIZE):
        self.MAXSIZE = MAXSIZE
        self.data = [None] * self.MAXSIZE
        self.top = -1

    #  Judge whether the current stack is empty 
    def is_empty(self):
        return self.top == -1

    def gettop(self):
        if self.is_empty():
            print(" The current sequence stack is empty ")
            return None
        else:
            return self.data[self.top]

    #  Push 
    def Push(self, item):
        #  Determine whether the stack is full 
        if self.top == self.MAXSIZE - 1:
            return "sqStack is full."
        self.data[self.top + 1] = item
        self.top += 1

    #  List stack 
    def ListPush(self, x):
        #  Determine whether the stack is full 
        if self.top == self.MAXSIZE - 1:
            return "sqStack is full."
        for i in range((len(x))):
            self.Push(x[i])

    #  Out of the stack 
    def Pop(self):
        #  Judge whether the stack is empty 
        if self.is_empty():
            return "sqStack is empty"
        rs = self.data[self.top]
        self.top -= 1
        return rs

    #  The length of the output stack 
    def size(self):
        return self.top + 1

    #  Output stack elements 
    def display(self):
        #  Judge whether the stack is empty 
        if self.is_empty():
            print(" The current sequence stack is empty ", end=" ")
        else:
            print(" The current linked list element is :", end="")
        for i in range(self.top + 1):
            print(self.data[i], end=" ")
        print()

    #  Empty stack 
    def clear(self):
        self.data = [None] * self.MAXSIZE
        self.top = -1


if __name__ == "__main__":
    s = sqStack(20)
    data = int(input(" Please enter a number to convert to binary : "))
    while data != 0:
        ys = data % 2
        s.Push(ys)
        data = data // 2

    while s.top != -1:
        print(s.Pop(), end='')

 Copy code 

Realization effect :  Insert picture description here

application 3

Decimal rotation N Base number ( application 2 Development of )    When a decimal integer M Convert to N Base number , During calculation , hold M And N The remainder is obtained N The bits of hexadecimal numbers are stacked in turn , After the calculation, the... In the stack will be N Hexadecimal numbers are output out of the stack in turn , The output is to be obtained N Hexadecimal number .

Test cases :    Test number :[200, 254, 153, 29, 108, 631, 892]    Base number :[4, 8, 16]

   Just match it freely , I mainly use random.choice() To access the hexadecimal random number to be converted from the test number , The test code is as follows , For reference only ;

Image Name

Running results :

Image Name About this problem, the programming code can refer to ↓( Personal writing , For reference only , We welcome valuable suggestions )

#!/usr/bin/env python
# -*- coding: utf-8 -*- 
# @Time : 2021/7/28 10:32 
# @Author : vaxtiandao
# @File : ds_10toN.py


#  Define the order stack 
class sqStack:
    #  Initialization stack 
    def __init__(self, MAXSIZE):
        self.MAXSIZE = MAXSIZE
        self.data = [None] * self.MAXSIZE
        self.top = -1

    #  Judge whether the current stack is empty 
    def is_empty(self):
        return self.top == -1

    def gettop(self):
        if self.is_empty():
            print(" The current sequence stack is empty ")
            return None
        else:
            return self.data[self.top]

    #  Push 
    def Push(self, item):
        #  Determine whether the stack is full 
        if self.top == self.MAXSIZE - 1:
            return "sqStack is full."
        self.data[self.top + 1] = item
        self.top += 1

    #  List stack 
    def ListPush(self, x):
        #  Determine whether the stack is full 
        if self.top == self.MAXSIZE - 1:
            return "sqStack is full."
        for i in range((len(x))):
            self.Push(x[i])

    #  Out of the stack 
    def Pop(self):
        #  Judge whether the stack is empty 
        if self.is_empty():
            return "sqStack is empty"
        rs = self.data[self.top]
        self.top -= 1
        return rs

    #  The length of the output stack 
    def size(self):
        return self.top + 1

    #  Output stack elements 
    def display(self):
        #  Judge whether the stack is empty 
        if self.is_empty():
            print(" The current sequence stack is empty ", end=" ")
        else:
            print(" The current linked list element is :", end="")
        for i in range(self.top + 1):
            print(self.data[i], end=" ")
        print()

    #  Empty stack 
    def clear(self):
        self.data = [None] * self.MAXSIZE
        self.top = -1


def divideByN(number, base):
    digits = "0123456789ABCDEF"
    remstack = sqStack(100)
    while number > 0:
        rem = number % base
        remstack.Push(rem)
        number = number // base
    newString = ""
    while not remstack.is_empty():
        newString = newString + digits[remstack.Pop()]
    return newString


import random

numbers = [200, 254, 153, 29, 108, 631, 892]
bases = [4, 8, 6]
for number in numbers:
    base = random.choice(bases)
    print("%d  Of  %d  The binary number is :%s" % (number, base, divideByN(number, base)))

 Copy code 

Realization effect :  Insert picture description here

Review the previous contents of the data structure column :【Python Data structure series 】《 The linear table 》—— Knowledge point explanation + Code implementation

Other column highlights : 【 Suggested collection 】 liver failure 3w The word takes you to understand what operation and maintenance is ~

10 Minutes to teach you how to automatically control the browser ——Selenium Testing tools

【 One week to master Flask Frame learning notes 】Flask Concept and basis

copyright notice
author[Vax_ Loves_ one thousand three hundred and fourteen],Please bring the original link to reprint, thank you.
https://en.pythonmana.com/2022/01/202201300533162554.html

Random recommended