Table of Contents
1. Stack
1. The concept of stack
1.2 Stack structure
2. Stack creation and initialization
3. Stack operation
4. Pop operation
5. Display the top element of the stack
6. Display the total number of elements in the stack space
7. Release stack space
8. Test stack
2. Queue
1. The concept of queue
1.2 Queue structure
2. Queue creation and initialization
3. Join the team
4. Leave the team
5. Display the head and tail data of the team
5.1 Display queue head data
5.2 Display the tail data of the queue
6. Display the number of data in the queue
7. Release the queue
8. Test queue
Conclusion:
Foreword:
Stacks and queues are both special linear tables, and linear tables are a widely used data structure. The reason why it is called a linear table is that it is logically continuous. You can think of it as a line connecting the data, but it is not necessarily physically continuous. When using linear tables to store data, data is usually stored in the form of linked structures and arrays. The stacks and queues introduced in this article are implemented using arrays and linked lists.
一、Stack
1. The concept of stack
The characteristic of the stack is that data can only be input and output from a fixed end, which is usually called stack pushing and popping. The data must meet the first-in-last-out status. The input and output ports of the data are called the top of the stack, and the other end is called the bottom of the stack. As the stack operation continues, the elements on the original top of the stack will be pushed to the bottom of the stack. When popping off the stack, the element at the bottom of the stack must wait until all the top elements above it are popped off the stack.
1.2 Stack Structure
Data input and output in the stack always follow the first-in-last-out rule.
Next, use code to implement the stack and analyze the various functions of the stack: push the stack, pop the stack, display the top element of the stack, display the number of stack space elements, and release the stack space.
2. Stack creation and initialization
The stack is implemented here in the form of an array, because the advantage of the array is that the efficiency of the array is still very high when inserting and deleting the tail. Of course, if an array is used for head plug deletion, each insertion and deletion requires the entire array. Moving is very inefficient. However, the characteristic of a stack is that only one end can input and output data, so we treat the end of the array as the top of the stack, so we do not need the function of deleting the array head plug.
First create the stack structure:
typedef int STDataType;//int type redefinition
typedef struct Stack
{
STDataType* arr;//arr can be understood as the first address of the array, and this pointer will be used to open up space later.
int top;//Represents the element at the top of the stack, that is, the last element of the array
int capacity;//Stack capacity
}ST
Stack initialization:
void STInit(ST* pst)//Initialization stack
{
assert(pst);
pst->arr = NULL;//When initializing, set it to empty first, and then open up space when inserting data later.
pst->top = 0;//There is no element at the beginning so the top of the stack is 0
pst->capacity = 0;//Initialization capacity can also be set to 0
}
There is a point to note here: the position of top is the next position of the top element of the stack, as shown in the following figure:
3. Push operation
Pushing the stack is to put the data at the end of the array, because the end of the array corresponds to the top position of the stack, and pushing the stack is to put elements from the top of the stack. After stack pushing is completed top++, the code is as follows:
void STPush(ST* pst, STDataType x)//Push onto the stack
{
assert(pst);
if (pst->capacity == pst->top)//Create an array and achieve capacity expansion at the same time
{
int newcapacity = pst->capacity == 0 ? 4 : 2 * pst->capacity;//Ternary operation
STDataType* temp = (STDataType*)realloc(pst->arr,sizeof(STDataType*) * newcapacity);//When the arr pointer points to null, realloc also has the effect of malloc
if (temp == NULL)//Check whether the space opening is successful
{
perror("STPush");
return;
}
pst->arr = temp;//If the allocation is successful, the allocated space will be given to the arr pointer
pst->capacity = newcapacity;//Update array size
}
pst->arr[pst->top] = x;//Push operation, push the array into the array (stack)
pst->top + + ;//Update top to the next position
}
4. Pop operation
The popping operation is very simple, because popping means moving the element out of the array, and the stack follows first-in-first-out. The first element in the array must be the last element, so just “delete” the last element directly. But we know that there is no way to delete an element in an array, so we use the top– method to move top one position forward. When the new element is pushed onto the stack next time, it will overwrite the element that was popped out, achieving the effect of popping out the stack.
Here is a detail: when performing a pop operation, you must pay attention to the fact that the stack cannot be empty at this time, so a function is specially written to determine whether the stack is empty. The empty detection function is as follows:
bool Empty(ST* pst)
{
assert(pst);
return pst->top == 0;//Return true if the stack is empty
}
The pop code is as follows:
void STPop(ST* pst)//Pop from the stack
{
assert(pst);
//If the Empty function is empty and returns true, negating the result here can achieve the effect of checking whether the stack is empty.
assert(!Empty(pst));//Assert uses the return value of function Empty to make an empty judgment
pst->top--;//After top--, the next time new data is pushed onto the stack, it will overwrite the original data.
}
5. Display the top element of the stack
Displaying the top element of the stack is very simple, just return the element at the end of the array, because the end of the array is equal to the top of the stack. It should also be noted here that if this function is called, the stack cannot be empty, because if the stack is empty, there will be no top element.
The code to display the top element of the stack is as follows:
STDataType STtop(ST* pst)//Display the top element of the stack
{
assert(pst);
assert(!Empty(pst));//Empty test
return pst->arr[pst->top - 1];//The end of the array, that is, the position of top minus 1
}
6. Display the total number of elements in the stack space
The advantage of letting top point to the last digit of the top element of the stack: at this time, the value of top is the sum of the elements in the stack space, so just return the value of top directly.
The code for the sum of stack elements is as follows:
STDataType STsize(ST* pst)//Display the number of all elements in the stack
{
assert(pst);
return pst->top;
}
This is different from the previous situation. An empty stack means that there is no element in the stack, which is 0, so there is no need to empty the stack.
7. Release stack space
Stack space is applied for on the heap, so it should be released manually after use.
The code to release stack space is as follows:
void STDestroy(ST* pst)//release space
{
assert(pst);
free(pst->arr);//Release arr, which is the stack space
pst->arr = NULL;
pst->capacity = 0;
pst->top = 0;
}
8. Test stack
After preparing each function of the stack, test these functions next.
The test code is as follows:
#include"stack.h"
test1()
{
ST st;//Create a structure variable st. In fact, the operation stack is implemented by operating the pointer arr in the structure st.
STInit(&st);//Initialization, pass the address of st, so that the members in st can be operated through its address
STPush( & amp;st, 1);//Push onto the stack
STPush( &st, 2);
STPush( &st, 3);
STPush( &st, 4);
printf("size:%d\\
", STsize( & amp;st));//Print the number of elements in the stack space
while (!Empty( & amp;st))
{
printf("%d ", STtop( & amp;st));//Print the top element of the stack
STPop( & amp;st);//Pop from the stack
}
STDestroy( & amp;st);//Release the stack
}
int main()
{
test1();
return 0;
}
operation result:
Judging from the running results, the order of popping out of the stack is 4 3 2 1, and the order in which we push into the stack is 1 2 3 4. The order corresponds to the characteristics of the stack: first in, last out.
2. Queue
1. The concept of queue
The stack has only one port that can input and output data, while the queue has two ports that can operate. One of the ports is used to input data, which is also called enqueuing. Another port outputs data (delete data) and calls out of the queue. The queue satisfies the first-in-first-out principle, that is, data enters from the end of the queue and is then output from the head of the queue.
1.2 Queue Structure
For example: if the order of entering the queue is 1 2 3 4, then the order of dequeuing is also 1 2 3 4, which is opposite to the characteristics of the stack.
Next, use code to implement the queue and analyze the various functions of the queue: entering the queue, dequeuing, displaying the head data, displaying the tail data, displaying the queue size and other functions.
2. Queue creation and initialization
First of all, because the queue involves the operation of two ports, implementing the queue with an array will encounter such a problem: changing the array header data. We all know that the cost of operating the head data of the array is very high, because moving the elements of the entire array is very inefficient.
So we choose to use a singly linked list structure to implement the queue, but this singly linked list is maintained by two pointers, one is the head pointer and the other is the tail pointer, which just corresponds to the two ports of the queue. The head pointer implements the dequeuing operation, and the tail pointer implements the enqueuing operation.
The queue creation code is as follows:
typedef int QueueDataType;//int type redefinition
typedef struct QNode//node structure
{
struct QNode* next; //Pointer in node
QueueDataType data;//data
}QNode;
typedef struct Queue//queue structure
{
struct QNode* head;//queue head pointer
struct QNode* tail;//queue tail pointer
int size;//Number of queue data
}Queue;
Why are there two structures? The first structure is the structure of the nodes that make up the linked list. The second structure is to record the head and tail pointers of the queue and the size of the queue. Therefore, it is convenient to put these three variables in one structure and it is also convenient to call, so another structure is created.
Queue initialization code:
void QueueInit(Queue* pq)//Initialization
{
assert(pq);
pq->head = NULL;//There is no node at the beginning, so the head pointer is empty
pq->tail = NULL;//The same is true for the tail pointer
pq->size = 0; //There are no nodes at the beginning, so the number of queue data is 0
}
3. Join the team
The end of the linked list is regarded as the end of the queue, so the enqueue operation starts from the end of the queue, that is, the concept of tail insertion.
The enqueue code is as follows:
QNode* BuyNode(QueueDataType x)//Create node function
{
QNode* newnode = (QNode*)malloc(sizeof(QNode));
if (newnode == NULL)
{
perror("BuyNode");
return NULL;
}
newnode->next = NULL;
newnode->data = x;
return newnode;
}
void QueuePush(Queue* pq, QueueDataType x)//Enter the queue
{
assert(pq);
QNode* newnode = BuyNode(x);//Create a node
//Judge two situations
if (pq->head == NULL)//1 is when the linked list is empty, the first data inserted at the end will also change the pointing of the head pointer
{
assert(pq->tail==NULL);
pq->head = pq->tail = newnode;//Both head and tail point to the newnode node
}
else//2 is that there is a node in the linked list, just change the pointing of the tail pointer directly.
{
pq->tail->next = newnode;
pq->tail = newnode;
}
pq->size + + ;//After successfully joining the queue, the number of queue data + 1
}
4. Dequeue
Since enqueueing is implemented at the end of the linked list, dequeuing is implemented at the other port of the linked list, that is, the head pointer of the linked list is responsible for implementing dequeuing, and the concept of head deletion is used. Since it is the concept of head deletion, you need to pay attention to the situation when the linked list is empty, so you need to make an empty judgment on the linked list. The logic of empty judgment is the same as the stack empty judgment logic above.
The dequeue code is as follows:
bool Empty(Queue* pq)//empty function
{
assert(pq);
return pq->head == NULL
|| pq->tail==NULL;//If the head and tail pointers are both empty, return true
}
void QueuePop(Queue* pq)//dequeue
{
assert(pq);
assert(!Empty(pq));//The return value of function Empty is true, and if the non-trigger assertion effect is applied to it, an error will be reported.
//Two situations
if (pq->head == pq->tail)//1 is when the linked list has only one node, and tail needs to be left blank.
{
free(pq->head);
pq->head = pq->tail = NULL;
}
else//2 is the case of multiple nodes. There is no need to leave the tail empty, only the head pointer needs to be updated.
{
QNode* poi = pq->head;
pq->head = pq->head->next;
free(poi);
}
pq->size--;//The number of data in the linked list after deletion is completed-1
}
5. Display the data of the head and tail of the team
5.1 Display team head data
The head of the queue is the node pointed by the head pointer, that is, the value of the node pointed by the head pointer is returned.
code show as below:
QueueDataType QueueFront(Queue* pq)//Display queue head data
{
assert(pq);
assert(!Empty(pq));//The linked list is empty. If the linked list is empty, the queue head data cannot be displayed.
return pq->head->data;//Return the value of the node pointed by the head pointer
}
5.2 Display the tail data
The tail of the queue is the node pointed by the tail pointer, so just return the value of the node pointed by the tail pointer directly.
code show as below:
QueueDataType QueueBack(Queue* pq)//Display the tail data of the queue
{
assert(pq);
assert(!Empty(pq));//The linked list is empty. If the linked list is empty, the tail data cannot be displayed.
return pq->tail->data;//Return the value of the tail node
}
6. Display the number of data in the queue
This reflects the role of size, just return size directly.
code show as below:
int QueueSize(Queue* pq)//Display queue size
{
assert(pq);
return pq->size;
}
7. Release queue
Because the queue is a space requested by malloc on the heap, it must be released manually after use.
The release code is as follows:
void QueueDestroy(Queue* pq)//Release the queue
{
assert(pq);
QNode* cur = pq->head;//The cur pointer replaces head to traverse the linked list
while (cur)
{
QNode* poi = cur->next;//poi marks the position of the next node
free(cur);//Release the node pointed by the cur pointer
cur = poi;//update cur pointer
}
pq->head = pq->tail = NULL;//Finally, both head and tail need to be left blank manually
pq->size = 0;//reset size to 0
}
8. Test Queue
Test each function of the written queue. The test code is as follows:
#include"Queue.h"
int main()
{
Queue p;//Create structure p
QueueInit( & amp;p);//Initialization of structure p
QueuePush( & amp;p, 1);//Enter the queue
QueuePush( & amp;p, 2);
QueuePush( & amp;p, 3);
printf("%d ", QueueFront( & amp;p));//View the current queue head data
QueuePop( & amp;p); // Dequeue
\t
QueuePush( & amp;p, 4);
printf("size:%d\\
", QueueSize( & amp;p));//View the number of data in the current queue
while (!Empty( & amp;p))//Loop to print the data at the head of the queue
{
printf("%d ", QueueFront( & amp;p));
QueuePop( & amp;p);
}
QueueDestroy( & amp;p);//Release the queue
return 0;
}
operation result:
The order of joining the team is 1 2 3 4. Judging from the results, even if a piece of data is dequeued midway, the overall dequeuing order has not changed. The dequeuing order is still 1 2 3 4, which is in line with the characteristics of the queue: first in, first out.
Conclusion:
The above is about the implementation and analysis of stacks and queues. I hope this article can bring you more gains. If this article is helpful to you, I hope you can move your little finger to help like it + follow + collect!! If there are any omissions or errors, please feel free to add them in the comment area~! ! thank you all! ! (?′?`?)