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

This article mainly introduces the C language programming data structure stack and queue example analysis, the article is very detailed, has a certain reference value, interested friends must read it!

1. The representation and implementation of stack 1 the concept and structure of stack

Stack: a special linear table (logically connected data) that allows inserts and deletions only at a fixed end. One end of the data insertion and deletion operation is called the top of the stack and the other end is called the bottom of the stack. The data elements in the stack follow the last-in-first-out principle.

Stack pressing: the insertion operation of the stack is called stack / line pressing / line entry, and the input data is at the top of the stack.

Out-of-stack: the delete operation of the stack is called off-stack. The output data is also at the top of the stack.

(picture from bit Employment course)

First in and out is similar to loading a pistol clip, the bullet you put first will be at the bottom of the clip, and the last bullet will be at the top of the clip. When you open a pistol, you shoot the bullet at the top of the clip first.

Let's define a stack type here:

Typedef int STDataType;// facilitates that if you need other types of data in the future, you can directly modify the type of int typedef struct Stack {STDataType*a;// stack bottom pointer int top;// stack top label int capacity;// capacity} ST

This paper introduces the implementation of stack by sequential table (array). Therefore, the so-called stacking is only the last insertion and deletion of sequential table. If the reader wants to implement it with linked list, the method is not unique.

2 initialization of stack

About the initialization of the stack: here we take the stack with capacity size 4 as an example. At first, because there is no data in the stack, we use top=0 to mark it. It should be noted that the pointer at the bottom of the stack cannot be empty, and should be discarded if a null pointer is not returned successfully when opening up space.

# include#include//malloc function header file void StackInit (ST*ps) / / stack initialization {assert (ps); / / prevent the passed pointer from being null pointer ps- > a = (STDataType) malloc (sizeof (STDataType) * 4) / / malloc opens up a space to be managed by STDataType type / / malloc. For more information on realloc and free functions that appear later, please see the author's dynamic memory management article if (ps- > a = = NULL) {printf ("realloc fail\ n"); exit (- 1); / / Terminator} ps- > capacity=4 / / take opening a stack with 4 data capacity as an example, and you can also write other numbers / / if there is not enough memory when pressing the stack, you can expand the capacity in the stack function mentioned later, ps- > top = 0. / / when there is no value in the stack at first, mark it with top=0. Every time you put a top++ / / for more details on the usage of top, please read down the stack section} 3 stack (insert a data at the top of the stack)

As shown in the figure above, we have now opened up a space with both an and top at the top of the stack. Let's put a data 1 into it.

1 after entering the stack, 1 is the top element of the stack, so if I want to continue to enter the stack, I want to put a data in the location of the top to make the newly placed data become the new top element of the stack, and so on, each time I enter an element, top++,top does not represent the position of the top element of the stack, but the next position of the top element of the stack.

# include//assert function header file # include//realloc function header file void StackPush (ST*ps, STDataType x) / / insert data on top of stack (stack) {assert (ps); if (ps- > top = = ps- > capacity) {STDataType*tmp = realloc (ps- > a, ps- > capacity * 2 * sizeof (STDataType)) / / realloc is to continue to open up a space in the space previously opened up. For more information, see the author's dynamic memory article / / generally double if (tmp = = NULL) / / failure to expand capacity (for example, memory is not enough for you to open up more space) will return a null pointer {printf ("realloc fail\ n") Exit (- 1); / / termination program} else {ps- > a = tmp; ps- > capacity * = 2;}} ps- > a [PS-> top] = x / / an is a pointer, a [x] = * (axix) ps- > top++;} 4 out of the stack (delete a data at the top of the stack)

Taking out the stack is very simple. Let's take the following figure as an example:

In the picture, we have stored 4 pieces of data 1, 2, 3, 4 in the stack, so what if we want to unstack, that is, delete 4? Just top- directly.

There are bound to be friends here who have doubts, why you top- is out of the stack, you 4 did not delete ah? The explanation is as follows: we said in the 1.3stack section that "top is not the position of the top element of the stack, but the next position of the top element of the stack". Now I top here in 4, indicating that 3 is the real top element of the stack, 4 is no longer within the jurisdiction of the stack.

Void StackPop (ST*ps) / / delete data at the top of the stack (out of stack) {assert (ps); assert (ps- > top > 0); / / if the stack is empty, call Pop to directly abort the program to report an error ps- > top--;}

About ps- > top > 0, it goes like this: suppose you don't have an element in the stack.

Your top- is just going down to uncharted territory, which is a very serious problem, so let's assert with assert here to prevent any elements in the stack from being marked into unknown territory by top. (again: top does not represent the position of the element at the top of the stack, but the next position of the element at the top of the stack)

5 take the top element STDataType StackTop (ST*ps) / / fetch the top data {assert (ps); assert (ps- > top > 0); / / when the stack is empty, adjust StackTop, and directly abort the program to report an error return ps- > a [PS-> top-1]; / / top is the next position of the top element, and top-1 is the top element / / a [m] = = * (aqm)}

The idea here is almost the same as 1.4. you should also prevent the situation where there is nothing in the stack, and then return to the top element normally, because top is the next position of the top element of the stack, top-1 is the top element of the stack, and then you can write normally.

A [PS-> top-1] you can also write as * (a + (ps- > top-1)). Readers can participate in the author's previous pointers, which I won't repeat here.

6. Fetch the number of data of the top element int StackSize (ST*ps) / / stack {assert (ps); return ps- > top;}

This is even easier. Just return the value of top directly. Why? let's just look at two pictures.

Figure 1:

Figure 2:

Figure 1 is before the stack, there is no element, top=0, figure 2 is after the stack, top++,top=1. And so on, for every element we add, every element top++, minus one element, top-. The number of elements is always equal to the top value, so our function here can simply return the top value.

7 determine whether the stack is empty int StackEmpty (ST*ps) / / determine whether the stack is empty {assert (ps); return ps- > top = = 0;}

From 1.6, we know that our top value is the same as the number of elements in the stack, so we directly return ps- > top = = 0; that is, if the expression ps- > top = = 0 holds, the expression value is 1, and vice versa.

Second, the representation and implementation of queues 1 the concept and structure of queues

Queue: a special linear table that only allows data operations to be inserted at one end and deleted at the other end. Queues are of first-in, first-out nature.

Queuing: the end of the insertion operation is called the end of the queue

Out of queue: the end of the deletion operation is called the head of the line.

(picture from bit Employment course)

Just like you take the artificial passage, you are at the front of the line, you go out first.

Implementation of 2 queues

Since the head of the queue leaves the queue and enters the queue at the end of the queue, which is very similar to the head deletion and tail insertion of a single linked list, we introduce how to implement a queue with a single linked list. As shown in the figure below, there is a single linked list of three nodes:

For example, now, I want one at the head of the line, that is, to delete the first node of the single-linked list node (header deletion).

Or one at the end of the line, that is, the end of a single linked list.

The code is as follows (example):

Typedef int QDataType;typedef struct QueueNode {struct QueueNode*next; QDataType data;} QNode;// here is the same as the definition of single linked list. If you need to take a look at the author's previous article on single linked list, typedef struct Queue// defines a structure storage header node address and tail node address to facilitate header deletion and tail insertion {QNode*head; QNode*tail;} Queue;3 queue initialization.

The code is as follows (example):

Void QueueInit (Queue*pq) queue initialization, pq is a structural pointer {assert (pq); / / determine whether pq is a null pointer pq- > head = NULL; pq- > tail = NULL;} 4 (insert a data at the end of the queue) void QueuePush (Queue*pq, QDataType x) / / join the queue (tail-in) {assert (pq); QNode*newnode = (QNode*) malloc (sizeof (QNode)) / / make a space for newnode if (newnode = = NULL) / / it is possible that there is not enough memory left to open up space. If malloc fails to open up, it will return a null pointer {printf ("failed to open space\ n"); exit (- 1); / / exit program} newnode- > data = x; newnode- > next = NULL If (pq- > tail = = NULL) / / there was no data in the queue. The header and tail pointers point to NULL {pq- > head = pq- > tail = newnode;} else {pq- > tail- > next = newnode; pq- > tail = newnode;}}.

The following if code is explained as follows:

If (pq- > tail = = NULL) {pq- > head = pq- > tail = newnode;} else {pq- > tail- > next = newnode; pq- > tail = newnode;}

There was no data in the queue, and both the header and tail pointers pointed to NULL

When you put a data into the queue, the head and tail pointers point to the new data (the head and tail pointers still point to one)

If you want to add one more node, you first have to connect the two nodes, that is, pq- > tail- > next = newnode; (tail points to the first node before it is connected), and then the tail pointer points to the second node.

5 void QueuePop (Queue*pq) / / out (head of the team) {assert (pq); assert (pq- > head); / / if you want to leave the team, there must be data available in the team / / the original queue has only one data if (pq- > head- > next = = NULL) {free (pq- > head) Pq- > head = pq- > tail = NULL;} / / the original queue has multiple data else {QNode*next = pq- > head- > next; free (pq- > head); pq- > head = next;}}

With regard to team entry, there are two situations to discuss:

1. The original queue has only 1 data

When there is only one data, both the head and tail pointers point to the 1 node, and their next is a null pointer, so we judge on this condition. Because there is only one node, that is, the node is deleted, we use the free function to free up the space pointed to by head. After releasing, that space has been returned to memory, then your head and tail pointers can not point to that space, we use null pointers to assign values.

two。 The original queue has multiple data

Now we are going to go out of the queue (the head of the line deletes a data), that is, delete 1 node, we first create a variable next to find the location of 2 nodes, and then free the space of 1 node.

After the 1-node space free is dropped, assign the next (pointing to 2 nodes) to the head and let the header pointer point to 2 nodes.

6 fetch head data QDataType QueueFront (Queue*pq) / / fetch head data {assert (pq); assert (pq- > head); return pq- > head- > data;} 7 fetch tail data QDataType QueueBack (Queue*pq) / / fetch tail data {assert (pq); assert (pq- > head); return pq- > tail- > data } 8 calculate the number of data in the queue int QueueSize (Queue*pq) / / the number of data in the queue {assert (pq); int size = 0; QNode*cur = pq- > head; while (cur) / / curvilinear null to cycle. NULL is the {size++; cur = cur- > next;} return size that appears after traversing the tail. } 9 determine whether the queue is empty bool QueueEmpty (Queue*pq) {assert (pq); return pq- > head = = NULL;}

This is generally used as an auxiliary function. Bool is used to determine whether the data type is true or false. If the expression: pq- > head = = NULL holds true, it returns true, and vice versa.

10 destroy the queue void QueueDestory (Queue*pq) / / destroy the queue {assert (pq); QNode*cur = pq- > head; while (cur) / / cursive null to loop. NULL is the {QNode*next = cur- > next; free (cur) that appears after traversing the tail. / / free is the space to which the point is released, and the pointer is still in cur = next;} pq- > head = pq- > tail = NULL;}

As shown in the figure above, we create a variable cur and assign it with a head pointer. Then find the second node, mark it with cur- > next, mark that we have released the cur (the first node space released, the pointer is still there), and then cur begins to traverse the second node, which is the space we marked with next. The rest, and so on. NULL appears after traversing the tail. When the loop does not indicate that it has traversed the node pointed to by the tail pointer, the header and tail nodes are no longer needed, so we use null pointers to assign values.

The above is all the contents of the article "sample Analysis of C language programming data structure Stack and queue". Thank you for reading! Hope to share the content to help you, more related knowledge, welcome to follow the industry information channel!

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.