Shulou(Shulou.com)05/31 Report--

This article mainly introduces "what is the difference between stack and stack in C++". In daily operation, I believe many people have doubts about the difference between stack and stack in C++. The editor consulted all kinds of materials and sorted out simple and easy-to-use methods of operation. I hope it will be helpful to answer the questions of "what is the difference between stack and stack in C++?" Next, please follow the editor to study!

1. Brief introduction of Stack 1.1 Stack in Program memory Partition

The stack is automatically allocated and released by the operating system, which is used to store the parameter values and local variables of the function, and its operation mode is similar to that of the stack in the data structure. Refer to the following code:

Int main () {int b; / Stack char s [] = "abc"; / / Stack char * p2; / / Stack}

Among them, the local variables defined in the function are pushed into the stack in the order defined successively, that is to say, there are no other variables between the addresses of the adjacent variables. The memory address of the stack grows in the opposite direction from the heap to the bottom, so the later defined variable address is lower than the previously defined variable, for example, the address of the variable s in the above code is less than the address of the variable b, and the p2 address is less than the address of s. The life cycle of the data stored in the stack ends with the completion of the function execution.

1.2 introduction to the heap

The heap is allocated and released by the developer, and if the developer does not release it, the program is reclaimed by OS at the end of the program, similar to a linked list. Refer to the following code:

Int main () {/ C uses the malloc () function to apply for char* p1 = (char*) malloc (10); couttop] = x; return 0;}} / / out of the stack, returning-1 failed, 0 successful int popSeqStack (SeqStack* s, DataType* x) {if (isEmptySeqStack (s)) {return-1 / / Stack empty cannot exit the stack} else {* x = s-> data [s-> top]; s-> top--; return 0;}} / / fetch the top element of the stack and return-1 failed. 0 successful int topSeqStack (SeqStack* sdata type * x) {if (isEmptySeqStack (s)) return-1 / / empty else {* xstores-> data [s-> top]; return 0;} / / print the elements in the stack int printSeqStack (SeqStack* s) {int i; printf ("elements in the current stack:\ n"); for (I = s-> top; I > = 0 Printf ("% 4d", s-> data [I]); printf ("\ n"); return 0;} / / testint main () {SeqStack* seqStack=initSeqStack (); if (seqStack) {/ / put 4, 5, 7 into stack pushSeqStack (seqStack,4); pushSeqStack (seqStack,5) PushSeqStack (seqStack,7); / / all the elements in the print stack printSeqStack (seqStack); / / get the top elements of the stack DataType xchang0; int ret=topSeqStack (seqStack,&x); if (0==ret) {printf ("top element is% d\ n", x) } / / remove the top elements from the stack ret=popSeqStack (seqStack,&x); if (0==ret) {printf ("pop top element is% d\ n", x);}} return 0;}

Run the above program and output the result:

Elements in the current stack: 7 5 4 top element is 7 pop top element is 7

2.2 introduction to the heap 2.2.1 Properties of the heap

Heap is a commonly used tree structure and a special complete binary tree if and only if it satisfies that the value of all nodes is not greater than or less than the value of its parent node is called heap. This property of the heap is called heap ordering. Therefore, in a heap, the root node is the largest (or smallest) node. If the root node is the smallest, it is called small top heap (or small root heap), and if the root node is the largest, it is called large top heap (or large root heap). The left and right children of the heap have no order of size.

Here is an example of a small top heap:

Heap storage generally uses an array to store the heap, and the parent subscript of the I node is (imur1) / 2 (iMel 1) / 2 (iMel 1) / 2. The subscripts of its left and right child nodes are 2 ∗ iF1 2 * iLife1 2 ∗ iNode 1 and 2 ∗ iB2 2 2 ∗ iNode 2, respectively. For example, the subscripts of the left and right child nodes of the 0th node are 1 and 2, respectively.

2.2.2 basic operation of the heap

(1) establish

Take the minimum heap as an example, if you store elements in an array, an array has a corresponding tree representation, but the tree does not meet the conditions of the heap, and the elements need to be rearranged to create a "stacked" tree.

(2) insert

When a new element is inserted into the end of the table, that is, at the end of the array, if the newly formed binary tree does not satisfy the nature of the heap, the elements need to be rearranged. The following figure shows the adjustment of inserting 15:00 into the heap.

(3) Delete.

In heap sorting, deleting an element always occurs at the top of the heap because the element at the top of the heap is the smallest (in the small top heap). The last element in the table is used to fill the gap, and the result tree is updated to meet the heap condition.

2.2.3 implementation of heap operation

(1) insert code implementation

Each insert places the new data at the end of the array. It can be found that there must be an ordered sequence from the parent node to the root node of the new data, and the task now is to insert the new data into the ordered data, which is similar to merging a data into the ordered interval in a direct insertion sort. This is the node "floating" adjustment. It is not difficult to write the adjustment code for the heap when inserting a new data:

/ / newly added I node, whose parent node is (iMur1) / 2max / parameter: a: array, I: subscript void minHeapFixUp (int a [], int I) {int j, temp; temp = a [I] of the newly inserted elements in the array; j = (iMul 1) / 2 / / parent node while (j > = 0 & & I! = 0) {if (a [j] (len/2-1)) / / index is a leaf node without adjusting return; int tmp=a [index]; lastIndex=index; while (index)

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.