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

This article mainly introduces the relevant knowledge of "stack case analysis of Python data structure". The editor shows you the operation process through the actual case. The operation method is simple, fast and practical. I hope this article "stack case analysis of Python data structure" can help you solve the problem.

1. The basic concept of stack 1.1 the basic concept of stack

Stack is a linear table that only performs insert and delete operations at one end of the sequence. For the stack, one end that can be operated is called the top of the stack (top), and the other end is called the bottom of the stack (bottom). A stack is called an empty stack if it does not contain any elements.

The stack provides a way to sort based on time in the collection, with the most recently added element near the top and the old element near the bottom. The newly added elements are removed first, and this sorting principle is also known as last-in, first-out (last in first out, LIFO) or first-in, first-out (fast in last out, FILO).

Real-world examples of stacks can be seen everywhere. As shown in the following illustration, the balls in the bucket form a stack that can only be taken out of the top at a time and placed on top when put back. Suppose the stack is S = (a0, A1, … , en) is the top element of the stack, and the elements in the stack are push in the order in which the top element is the first element to pop

By observing the order in which elements are added and removed, you can quickly understand the ideas contained in the stack. The following figure shows the process of entering and unloading the stack, and the order of insertion and removal of elements in the stack is exactly the opposite.

1.2 Stack Abstract data Type

In addition to the main operations (in and out of the stack), the stack also has auxiliary operations such as initialization, emptying, and fetching top elements. Specifically, the abstract data type of the stack is defined as follows:

Basic operations:

1. _ _ itit__ (): initialize the stack

Create an empty stack

2. Size (): gets and returns the number of elements in the stack n

If the stack is empty, the integer 0 is returned.

3. Isempty (): determine whether the stack is empty

Determine whether elements are stored in the stack

4. Push (data): enter the stack

Insert the element data into the top of the stack

5. Pop (): out of stack

Delete and return the top element of the stack

4. Peek (): take the top element of the stack

Returns the element value at the top of the stack, but does not delete the element

1.3 Application scenarios of Stack

Stack has a wide range of application scenarios, such as:

Symbol matching. For a specific description, please refer to Section 3.3.

Function call, each function that is not called has a data area in the function stack, which stores the important information of the function, including the local variables and parameters of the function.

The suffix expression is evaluated, and the suffix expression needs only one stack to store the numeric value. If the traversal expression encounters a numerical value, it goes into the stack, when it encounters an operator, it calculates two values out of the stack, and puts the calculation result into the stack. The only value retained in the stack is the expression result.

The back button in web browsing, when we jump between pages, these URLs are stored in a stack

The undo sequence in the editor is similar to the back button in web browsing, and the stack saves the editing operation of each step.

In addition to the above applications, we will see that the stack is used as an auxiliary data structure for many algorithms in later learning.

two。 Implementation of stack

Like linear tables, stacks have two storage representations.

2.1 implementation of sequential stack

The sequential stack is the sequential storage structure of the stack, which is stored sequentially from the bottom of the stack to the top of the stack by using a set of consecutive address memory cells. At the same time, the pointer top is used to indicate the index of the elements at the top of the stack in the sequential stack. Similarly, the sequential stack can be of fixed length and dynamic length. When the stack is full, the fixed-length sequential stack will throw a stack full exception, and the dynamic sequential stack will dynamically apply for free space.

2.1.1 initialization of stack

The initialization of the sequential stack requires three pieces of information: the stack list is used to store the data elements, the max_size is used to store the maximum length of the stack list, and the index used by top to record the elements at the top of the stack:

Class Stack: def _ _ init__ (self, max_size=10): self.max_size = max_size self.stack = self.max_size * [None] self.top =-1

2.1.2 find the stack length

Because top represents the index of the elements at the top of the stack, we can easily calculate the number of data elements in the sequential stack, that is, the stack length:

Def size (self): return self.top + 1

2.1.3 the stack is empty

According to the length of the stack, it is easy to judge whether the stack is empty or not.

Def isempty (self): if self.size () = = 0: return True else: return False

2.1.4 the stack is full.

Because we need to apply for stack space in advance, we need to be able to determine whether there is any free space on the stack:

Def isfully (self): if self.size () = = self.max_size: return True else: return False

2.1.5 Stack

When entering the stack, you need to first determine whether there is any free space in the stack, and then the stack operation is slightly different according to whether the stack is a fixed-length sequential stack or a dynamic sequential stack:

[stacking operation of a fixed-length sequential stack] if the stack is full, an exception is thrown:

Def push (self, data): if self.isfully (): raise IndexError ('Stack overflowing') Else: self.top + = 1 self.stack [self.top _ 1] = data

[dynamic sequential stack operation] if the stack is full, apply for new space first:

Def resize (self): new_size = 2 * self.max_size new_stack = [None] * new_size for i in range (self.num_items): new_ Stack [I] = self.items [I] self.stack = new_stack self.max_size = new_size def push (self Data): if self.isfully (): self.resize () else: self.top + = 1 self.stack [self.top _ 1] = data

The time complexity of entering the stack is O (1). It should be noted that although when the dynamic sequence stack is full, the elements in the original stack need to be copied to the new stack first, and then new elements need to be added, according to the introduction of sequence table append operation in "sequence table and its operation realization", because the total time T (n) of n stack operation is proportional to O (n), the amortization time complexity of stack can still be regarded as O (1).

2.1.6 out of stack

If the stack is not empty, delete and return the top element of the stack:

Def pop (self): if self.isempty (): raise IndexError ('Stack underflow') Else: result = self.stack [self.top] self.top-= 1 return result

2.1.7 find the top element of the stack

If the stack is not empty, simply return the element at the top of the stack:

Def peek (self): if self.isempty (): raise IndexError ('Stack underflow') Else: implementation of return self.stack [self.top] 2.2 chain stack

Another storage representation of a stack is to use a linked storage structure, so it is often called a linked stack, in which the push operation is achieved by inserting elements in the head of the linked list, and the pop operation is achieved by deleting the node from the header.

2.2.1 Stack node

The node implementation of the stack is no different from the linked list:

Class Node: def _ init__ (self, data): self.data = data self.next = None def _ str__ (self): return str (self.data)

2.2.2 initialization of stack

In the initialization function of the stack, point the pointer at the top of the stack to None and initialize the stack length:

Class Stack: def _ init__ (self): self.top = None # stack number of elements self.length = 0

2.2.3 find the stack length

The value that returns length is used to find the stack length. If there is no length attribute, you need to traverse the entire linked list to get the stack length:

Def size (self): return self.length

2.2.4 the stack is empty

According to the length of the stack, it is easy to judge whether the stack is empty or not.

Def isempty (self): if self.length = = 0: return True else: return False

2.2.5 Stack

When entering the stack, you can insert a new element at the top of the stack:

Def push (self, data): P = Node (data) p.next = self.top self.top = p self.length + = 1

Because the element is inserted at the head of the linked list, the time complexity of entering the stack is O (1), in which case the end of the chain serves as the bottom of the stack.

2.2.5 out of the stack

If the stack is not empty, delete and return the top element of the stack:

Def pop (self) if self.isempty (): raise IndexError ("Stack Underflow!") Ele = self.top.data self.top = self.top.next self.length-= 1 return ele

Since the delete element only needs to modify the header pointer to point to its next domain, the time complexity of de-stack is also O (1).

2.2.6 find the top element of the stack

If the stack is not empty, you can return to the top element of the stack, but the top element will not be deleted:

Def peek (self) if self.isempty (): raise IndexError ("Stack Underflow!") Comparison of different implementations of return self.top.data2.3 Stack

In this section, we will compare the similarities and differences between different implementations of the stack:

Sequential stack

The time complexity of the operation is O (1), and the tail of the list serves as the top of the stack.

When the stack is full, you need to dynamically expand and copy the original stack elements to the new stack.

Chain stack

The time complexity of the operation is O (1), and the head of the linked list serves as the top of the stack.

Elegant expansion, no need to consider the stack is full, need extra space to store pointers

3. Stack application

Next, we first test the linked list of the above implementation to verify the effectiveness of the operation, and then use the basic operation of the implementation to solve the actual algorithm problem.

3.1 Application of sequential stack

First initialize a sequential stack stack, and then test the relevant operations:

# initialize a stack with a maximum length of 4 s = Stack (4) print ('stack empty?', s.isempty ()) for i in range (4): print ('stack element:', I) s.push (I) print ('stack full?', s.isfully ()) print ('stack top element:', s.peek ()) print ('stack length is:', s.size ()) while not s.isempty (): print ('stack element:' S.pop ()

The output of the test program is as follows:

Is the stack empty? True

Stack element: 0

Stack element: 1

Stack element: 2

Stack element: 3

Is the stack full? True

Top element of stack: 3

Stack length: 4

Off-stack element: 3

Off-stack element: 2

Off-stack element: 1

Out-stack element: 0

3.2 Application of chain stack

First initialize a chain stack stack, and then test the operation:

# initialize the new stack s = Stack () print ('stack empty?', s.isempty ()) for i in range (4): print ('stack element:', I) s.push (I) print ('stack top element:', s.peek ()) print ('stack length is:', s.size ()) while not s.isempty (): print ('stack element:', s.pop ())

The output of the test program is as follows:

Is the stack empty? True

Stack element: 0

Stack element: 1

Stack element: 2

Stack element: 3

Top element of stack: 3

Stack length: 4

Off-stack element: 3

Off-stack element: 2

Off-stack element: 1

Out-stack element: 0

3.3 implementation of complex algorithms using basic stack operations

Matching symbols refer to the correct matching of left and right corresponding symbols (symbols allow nesting). Not only each left symbol has a right symbol corresponding to it, but also the type of the two symbols is the same. The subscript shows the matching of some symbol strings:

Does the symbol string match [] () () match [() ()) mismatch {([] ())} match (()) []} mismatch

In order to check the matching of the symbol string, you need to traverse the symbol string and write it to the stack if the character is a start delimiter such as (, [, or {); when an end delimiter such as),], or} is encountered, the top element of the stack is off the stack and compared with the current traversal element, and if they match, continue to parse the symbol string, otherwise it indicates a mismatch. When the traversal is complete, if the stack is not empty, it also indicates a mismatch:

Def isvalid__expression (expression): stack = Stack () symbols = {')': (',']':'[' '}':'{'} for s in expression: if s in symbols: if stack: top_element = stack.pop () else: top_element ='#'if symbols [s]! = top_element: return False else: stack.push (s) return not stack

Because we only need to traverse one side of the symbol string, the time complexity of the algorithm is O (n), and the space complexity of the algorithm is also O (n).

Given a linked list (with header node) L: L0 → L1 → … → Ln, rearranging it as: L0 → Ln → L1 → Ln − 1 … .

For example, if the linked list contains 9 elements, the following figure shows the elements of the linked list before and after rearrangement:

Because of the principle of first in and then out of the stack, the cooperation of the stack and the original linked list can be used to rearrange the stack, traversing the linked list for the first time and putting each node into the stack; the unstack order of the elements in the stack is the reverse order of the nodes of the original linked list, and then alternately traverse the linked list and the stack to build a new linked list.

Def reorder_list (L): P = L.head.next if p = = None: return L stack = Stack () while packs = None: stack.push (p) p = p.next l = L.head.next from_head = L.head.next from_stack = True while (from_stack and l! = stack.peek () or (not from_stack and l! = from_head)): If from_stack: from_head = from_head.next l.next = stack.pop () from_stack = False else: l.next = from_head from_stack = True l = l.next l.next = None

The time complexity and space complexity of the algorithm are both O (n).

This is the end of the introduction to "Stack instance Analysis of Python data structures". Thank you for reading. If you want to know more about the industry, you can follow the industry information channel. The editor will update different knowledge points for you every day.

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.