Stack
Definition: a stack is a linear table whose insertion and deletion operations are limited to one end of the table. It is usually called the top of the stack and the bottom of the stack. When there are no elements in the table, it is called empty stack.
Example: suppose stack S=(a1, a2, a3,... an), then a1 is called the bottom element of stack and an is the top element of stack. The elements in the stack enter the stack in the order of a1, a2, a3,... An, and the first element out of the stack should be the top element of the stack. In other words, the stack is modified according to the principle of last in first out. Therefore, the stack is called a last in first out table (LIFO).
Example: a stack of books or a stack of plates.
The abstract data type of stack is defined as follows:
Sequential stack
Because the stack is a linear table with limited operation, the storage structure of the linear table is also suitable for the stack. The sequential storage structure of stack is called sequential stack for short. Therefore, arrays can be used to implement sequential stacks. Because the stack bottom position is fixed, you can set the stack bottom position at any endpoint at both ends of the array; The position of the top of the stack changes with the operation of entering and exiting the stack, so an integer variable top is needed to indicate the position of the current top of the stack, which is usually called top pointer. Therefore, for the type definition of sequence stack, you only need to change the length attribute in the type definition of sequence table to top. The types of sequential stacks are defined as follows:
typedef int datatype;
#define MyStacksize 10
typedef struct mystack
{
datatype data[MyStacksize] = { 0 };
int top;
}MyStack;
Initial state:
When the stack is full, the operation of entering the stack must produce space overflow, referred to as "overflow"; When the stack is empty, the back stack operation will also produce overflow, referred to as "underflow". Overflow is an error state that should be avoided; When the stack is empty, it is often used to control the overflow in the initial state or in the lower state of the program.
Complete code
include <stdio.h>
typedef int datatype;
#define MyStacksize 10
typedef struct mystack
{
datatype data[MyStacksize] = { 0 };
int top;
}MyStack;
void initstack(MyStack* sta)//Create empty stack
{
sta->top = -1;
}
bool stackempty(MyStack* sta)//Judge whether the stack is empty
{
return sta->top == -1;
}
bool stackfull(MyStack* sta)//Judge stack full
{
return sta->top == MyStacksize - 1;
}
void push(MyStack* sta,datatype element)//Stack pressing
{
if (stackfull(sta)) {
printf("Stack full, stack pressing failed!!!");
return;
}
else {
sta->top++;
sta->data[sta->top] = element;
}
}
datatype pop(MyStack* sta)//Out of stack
{
if (stackempty(sta)) {
printf("Stack empty, stack failed!!!");
return NULL;
}
else {
datatype element;
element = sta->data[sta->top]; //Get stack top element
sta->data[sta->top] = 0; //Delete stack top element
sta->top--; //Update stack top pointer
return element;
}
}
datatype stacktop(MyStack* sta)//Get stack top element
{
if (stackempty(sta)) {
printf("Stack empty, fetch failed!!!");
return NULL;
}
else {
return sta->data[sta->top];
}
}
int main()//The main function only gives initialization and some test codes. You can add specific test call functions to the main function yourself
{
MyStack* sta=(MyStack*)malloc(sizeof(MyStack));
initstack(sta); //Create empty stack
printf("%d\n", sta->top);
if (stackempty(sta)) //Determine whether the stack is empty
printf("Stack empty!!!\n");
else
printf("Stack is not empty!!!\n");
push(sta, 10); //Stack pressing
printf("%d\n", stacktop(sta));
if (stackfull(sta)) //Judge stack full
printf("Stack full!!!\n");
else
printf("Stack not full!!!\n");
printf("%d\n",pop(sta)); //Out of stack
for (int i = 0; i < 10; i++) {//Continuous stack pressing
push(sta, i);
}
printf("%d\n", pop(sta));
return 0;
}
Chain stack
Definition: the chain storage structure of stack is called chain stack. Its operation is a restricted single linked list, and the insertion and deletion operations are only limited to the header position. Because it can only be operated at the head of the linked list, it is not necessary to attach a head node like a single linked list. The stack top pointer is the head pointer of the linked list
Chain stack storage unit:
typedef int datatype;
typedef struct mystack
{
datatype data;//The stack top pointer stores the stack length and other element data
mystack* next;
}MyStack;
Example:
Chain stack features:
- Chained stack has no problem of full stack, and the space is expandable
- Insertion and deletion are performed only at the top of the stack
- The top of the chain stack is at the head of the chain
- Suitable for multi stack operation
Stack pressing algorithm:
In fact, it is the header insertion method of the single linked list mentioned in the previous article, which constantly updates the node pointed to by the pointer at the top of the stack.
void push(MyStack* top, datatype element)//Stack pressing
{
MyStack* sta = (MyStack*)malloc(sizeof(MyStack));//Allocate memory for new elements and create nodes
sta->data = element;
sta->next = NULL;
sta->next = top->next; //Connect the new node with the original stack top node
top->next = sta; //Update stack top node
top->data++; //Update stack length
}
Complete code
typedef int datatype;
typedef struct mystack
{
datatype data;
mystack* next;
}MyStack;
MyStack* initstack()//Create empty stack
{
MyStack* top = (MyStack*)malloc(sizeof(MyStack));
top->data = -1;
top->next = NULL;
return top;
}
bool stackempty(MyStack* top)//Judge whether the stack is empty
{
return top->data == -1;
}
void push(MyStack* top, datatype element)//Stack pressing
{
MyStack* sta = (MyStack*)malloc(sizeof(MyStack));
sta->data = element;
sta->next = NULL;
sta->next = top->next;
top->next = sta;
top->data++;
}
datatype pop(MyStack* top)//Out of stack
{
if (stackempty(top)) {
printf("Stack empty, stack failed!!!");
return NULL;
}
else {
datatype element;
MyStack* sta;
sta = top->next; //Stack top node
element = sta->data;
top->next = sta->next; //Delete stack top element
top->data--; //Update stack length
free(sta); //Free memory occupied by deleted nodes
return element;
}
}
datatype stacktop(MyStack* top)//Get stack top element
{
if (stackempty(top)) {
printf("Stack empty, fetch failed!!!");
return NULL;
}
else {
return top->next->data;
}
}
int main()//The main function only gives initialization and some test codes. You can add specific test call functions to the main function yourself
{
MyStack* top = initstack(); //Create empty chain stack
printf("%d\n",top->data);
if (stackempty(top)) //Judge whether the stack is empty
printf("Stack empty!!!\n");
else
printf("Stack is not empty!!!\n");
push(top, 10); //Stack 10
printf("%d\n", stacktop(top));
printf("%d\n", pop(top)); //Pop up the node element pointed to by the top of the stack
for (int i = 0; i < 10; i++) { //Continuous stack pressing
push(top, i);
}
printf("%d\n", stacktop(top));
return 0;
}
Summary: it's not too difficult to understand the stack data structure, but it's still difficult to skillfully use it. Practice more!
queue
Definition: a queue is a data structure that inserts only at one end of a table and deletes at the other end.
- The end of the front that allows deletion always points to the position before the first element.
- The end of the queue that allows insertion is always the end that points to the last element of the queue
- First in first out linear table, referred to as FIFO table
- Empty queue when there are no elements in the queue
Sequential queue
Definition: the sequential storage structure of queue is called sequential queue for short
Storage structure:
typedef int datatype;
#define MyQueuesize 10
typedef struct mystack
{
datatype data[MyQueuesize] = { 0 };
int front;
int rear;
}MyQueue;
Characteristics of sequential queue:
- There are also overflow and underflow in the queue.
- In addition, there is a phenomenon of "false overflow" in the sequential queue. Because in the operation of entering and leaving the queue, the head and tail pointers only increase but not decrease, so that the space of the deleted element can never be reused. Therefore, although the actual number of elements in the queue is much smaller than the scale of the vector space, it may also be that the tail pointer has exceeded the upper bound of the vector space and cannot be queued. This phenomenon is called false overflow.
The tail pointer is 5 and the head pointer is 1. At this time, the tail pointer has pointed to the last element of the sequence queue, but you can see 0 and 1
If it is not used, it is false overflow.
Some operation codes:
void initQueue(MyQueue* que)//Create an empty queue
{
que->front = -1;
que->rear = -1;
}
bool Queueempty(MyQueue* que)//Judge team empty
{
return que->front == que->rear;
}
bool Queuefull(MyQueue* que)//Judge whether the team is full
{
return que->rear == MyQueuesize - 1;
}
Circular queue
In order to solve the problem of false overflow, the circular queue is introduced, that is, the vector space is imagined as a ring with head and tail connected. When the out of line and in line operations are carried out in the circular queue, the head and tail pointer still needs to add 1 and move forward. However, when the head and tail pointer points to the upper bound of the vector (MAXNUM-1), the result of its plus 1 operation is to point to the lower bound 0 of the vector.
However, the introduced circular queue has new problems. See the figure:
That is, when the team is empty and full, both meet Q - > front = = q - > rear. We can't use this condition to judge whether the team is empty or full!!! How to solve this problem? There are two ways:
- Use one less data element space, and judge whether the team is full with the end of the team indicator plus l equal to the head of the team indicator, that is, the condition of full team is:
(q-> rear+l)％MAXNUM=q->front - A counter is used to record the total number of elements in the queue (actually the queue length).
Example code of the first method:
bool Queueempty(MyQueue* que)//Empty judgment team
{
return que->front == que->rear;
}
bool Queueempty(MyQueue* que)//Judge whether the team is full
{
return (que->rear + 1) % MyQueuesize == que->front;
}
Example code of the second method:
typedef int datatype;
#define MyQueuesize 10
typedef struct mystack //storage structure
{
datatype data[MyQueuesize] = { 0 };
int front;
int rear;
int count;
}MyQueue;
bool Queueempty(MyQueue* que)//Judge team empty
{
return que->count == 0;
}
bool Queuefull(MyQueue* que)//Judge whether the team is full
{
return que->count == MyQueuesize ;
}
Well, this problem is solved smoothly!
Other operation codes of circular queue:
void enterQueue(MyQueue* que, datatype element)//Join the team
{
if (Queuefull(que)) {
printf("The queue is full, failed to join!!!\n");
}
else {
que->rear = (que->rear + 1) % MyQueuesize;
que->count++;
que->data[que->rear] = element;
printf("Join the team successfully!\n");
}
}
datatype deletQueue(MyQueue* que) //Out of queue
{
if (Queueempty(que)) {
printf("The queue is empty, leaving the queue failed!!!\n");
return NULL;
}
else {
que->front = (que->front + 1) % MyQueuesize;
que->count--;
datatype element = que->data[que->front]; //Take the team head element
que->data[que->front] = 0; //Delete queue header element
printf("Team success!\n");
return element;
}
}
int main() //The main function only gives initialization and some test codes. You can add specific test call functions to the main function yourself
{
MyQueue* que = (MyQueue*)malloc(sizeof(MyQueue));
return 0;
}
Chain queue
Definition: the chained storage structure of a queue is called chained queue for short. It is a single chained table that restricts deletion at the header and insertion at the footer. Obviously, only the head pointer of the single linked list is not convenient for inserting at the end of the list. Therefore, a tail pointer is added to point to the last node of the linked list. Thus, a chain queue is uniquely determined by the head pointer and the tail pointer.
Storage structure:
The head pointer and tail pointer are encapsulated in a structure for easy operation.
typedef int datatype;
typedef struct myQueue //Element node
{
datatype data;
myQueue* next;
}MyQueue;
typedef struct queue //Head pointer tail pointer
{
myQueue* front;
myQueue* rear;
}myqueue;
Judge team empty
The empty condition of the chain team is that pointer - > front - > next = = null & & Pointer - > rear - > next = = null instead of pointer - > front = = pointer - > rear. This is because the values of pointer - > front and pointer - > rear are different when the team is empty.
Reason: as shown in the figure above, when creating an empty chain queue, the queue head pointer and tail pointer point to the black node in the figure above (this black node is equivalent to - 1 of the sequential queue and is an initial node). When the chain queue adds elements, the tail pointer will change the node it points to. In this case, the value of pointer - > rear is the address of the tail node it points to. When the queue deletes an element, the next pointer of the black node is changed (this is done to make the head pointer meet its characteristics. See the characteristics of the upper queue for details), so that the value of pointer - > front is always the address of the black node. Therefore, the values of pointer - > front and pointer - > rear are different, which can not be used as the condition for judging the team empty.
bool Queueempty(myqueue* pointer)//Judge team empty
{
return pointer->front->next == NULL && pointer->rear->next == NULL;
}
Out of queue:
This function should be noted that when there is only one element left in the queue, that is, pointer - > front - > next = = pointer - > rear, and you want to delete this element, you need to change the node pointed to by the tail pointer first, and then delete it to free the memory of the last element node. Because if you don't change it, the tail pointer points to the last element node. After you delete and release the memory of the last element node, pointer - > rear - > next is a wild pointer (I don't need to say the harm of wild pointer!!!), Will cause the program to not run normally!!!
datatype deletQueue(myqueue* pointer)
{
MyQueue* p;
if (Queueempty(pointer)) {
printf("The queue is empty, leaving the queue failed!!!\n");
return NULL;
}
else {
p = pointer->front->next;
if (p == pointer->rear) {
pointer->rear = pointer->front;
pointer->front->next = NULL;
}
datatype element = p->data;
pointer->front->next = p->next;
free(p);
printf("Team success!\n");
return element;
}
}
Other operation example codes
#include<stdio.h>
typedef int datatype;
typedef struct myQueue //Element node
{
datatype data;
myQueue* next;
}MyQueue;
typedef struct queue //Head pointer tail pointer
{
myQueue* front;
myQueue* rear;
}myqueue;
void initQueue(myqueue* pointer)//Create an empty queue
{
pointer->front = (MyQueue*)malloc(sizeof(MyQueue));
pointer->rear = pointer->front;
pointer->front->next = NULL;
}
void enterQueue(myqueue* pointer, datatype element)//Join the team
{
MyQueue* que = (MyQueue*)malloc(sizeof(MyQueue));
que->data = element;
que->next = NULL;
pointer->rear->next = que;
pointer->rear = que;
printf("Join the team successfully!\n");
}
int main() //The main function only gives initialization and some test codes. You can add specific test call functions to the main function yourself
{
myqueue* pointer = (myqueue*)malloc(sizeof(myqueue));
initQueue(pointer);
return 0;
}
That's the end of the stack and queue. It still needs more practice after understanding. I hope this blog can help you! At the same time, you are also welcome to comment and leave messages. The data structure series blog will be updated continuously. Come on! Rush, rush!!!