Foreword
About the author: Come on, Xu Xing, currently a sophomore, currently learning C++, Data Structure, etc.
Author’s homepage: Come on, Xu Xing’s homepage?This article is included in: Re-recognizing the advanced column of C
Code Warehouse: Rising Sun 1
Everyone is welcome to like Collect ? Follow!
Learning objectives:
This blog will learn about stacks and queues. Stack and Queue are two basic data structures. You must lay a good foundation now and learn later. In my career, I often encounter, for example: Depth First Search (DFS) Breadth First Search (BFS)… Today we are going to learn the simulation implementation of stacks and queues: Use array simulation to implement stack, use singly linked list simulation to implement queue, and use array simulation to implement queue.
Learning content:
With the learning objectives above, we can list what we want to learn:
- Using array simulation to implement stack
- Using array simulation to implement queue
- Simulate queue using singly linked list
1. Stack related knowledge
1.1 Concept and structure of stack
Let’s start with a piece of vernacular, which will appear in articles introducing stacks.
The stack is a special linear list that only allows insertion and deletion of elements at a fixed end (similar to tail insertion and tail deletion). Let’s first introduce two concepts – the top of the stack and the bottom of the stack: the end where data insertion and deletion operations are performed is the top of the stack, and the other end is the bottom of the stack. A taller way of saying it is: the elements in the stack follow the LIFO (Last In First Out) principle.
Next, we will introduce two operations-pressure stack and push:
- Push on the stack: The insertion operation of the stack is push/push/push, and the inserted data is on the top of the stack;
- Pop: The deletion operation of the stack is to pop the data out of the stack at the top of the stack.
1.2 Implementation of stack
Now, we have learned two data structures: sequence list and linked list. Which data structure is better to use to implement the stack? Here we choose to use an array to simulate the stack.
Why would it be better for us to use an array simulation to implement a stack?
The two operations of the stack are undoubtedly tail insertion and tail deletion. These two operations are relatively easy to implement in an array (compared to a linked list). Moreover, the data content stored in the array is relatively concentrated, and the CPU cache hit rate is high. It is as small as possible. It does not pollute the cache area, so it is better to use array simulation to implement it.
In real life, we generally need to implement a stack that can grow dynamically, rather than a static stack (which is relatively rigid and not common in practical applications). Although static stacks are not common in real life, they can still be used in algorithm questions, and in algorithm questions, we do not need to consider memory leaks hh. Let’s make it happen!
Code 1: Implement dynamic stack
The first step is to define the header file to be used:
#include <stdio.h> //Header files that must be included #include <assert.h> //Use assert to assert to prevent bad situations from happening. #include <stdbool.h> //In C language, bool variables are not provided #include <stdlib.h> //Use some functions to apply for memory space
In the second step, we want to introduce the protagonist and construct the stack structure:
typedef int StDatatype; // In order to facilitate changing the data type in the array later typedef struct stack { StDatatype* a; // a dynamic space int top; // represents the top of the stack int capacity; // Indicates how much space the stack currently has }ST;
The third step is to define some functions that we want to implement the stack function: stack initialization (define a structure, member variables must be initialized), stack destruction, stack insertion operation, stack deletion operation, stack viewing operation Top element, check the size of the stack, check whether the stack is empty
//Initialization of stack void stackinit(ST* stk); //stack insertion operation void stackpush(ST* stk, StDatatype x); //Stack deletion operation void stackpop(ST* stk); //Return the top element of the stack StDatatype stacktop(ST* stk); //Determine whether the stack is empty bool stackempty(ST* stk); //return stack size int stacksize(ST* stk); //Destroy the stack void stackdestroy(ST* stk);
Stack initialization operation:
void stackinit(ST* stk) { assert(stk); //Prevent passing null pointer //There are two ways to initialize //Method 1 stk->a = NULL; stk->capacity = 0; stk->top = 0; //If this points to 0, top represents the size of the stack } //Method 2 void stackinit(ST* stk) { assert(stk); stk->a = NULL; stk->capacity = 0; stk->top = -1; //If this points to -1, top represents the subscript of the top element of the stack }
Stack destruction operation:
void stackdestroy(ST* stk) { assert(stk); free(stk->a); stk->a = NULL; // Don't forget to leave it blank to prevent wild pointers from appearing. free(stk); stk = NULL; } // Because the stack uses an array, it can be destroyed directly
Stack insertion operation:
void stackpush(ST* stk, StDatatype x) { assert(stk); //Because the stack space we have here has not been created. if (stk->capacity == stk->top) { int newcapacity = stk->capacity == 0 ? 4 : stk->capacity * 2; StDatatype* tmp = (StDatatype*)realloc(stk->a, newcapacity * sizeof(StDatatype)); if (tmp == NULL) { perror(tmp); return; } stk->a = tmp; stk->capacity = newcapacity; } //Insertion operation is equivalent to tail insertion stk->a[stk->top] = x; stk->top + + ; // Don't forget to add 1 to the top of the stack }
Stack deletion operation:
void stackpop(ST* stk) { assert(stk); assert(stk->top > 0); stk->top--; }
Return the top element of the stack:
StDatatype stacktop(ST* stk) { assert(stk); assert(stk->top > 0); return stk->a[stk->top - 1]; // top == 0 //return stk->a[stk->top]; // top == -1 }
Determine whether the stack is empty:
bool stackempty(ST* stk) { //The first way to write: assert(stk); if (stk->top == 0) { return true; } return false; //The second way of writing: //return stk->top == 0; }
Return stack size:
int stacksize(ST* stk) { assert(stk); return stk->top; // top == 0 //return stk->top + 1; // top == -1 }
Code 2: Implementing a static stack
struct my_stack
{
int a[10];
int size;
int capacity;
}
2. Knowledge about queues
2.1 The concept and structure of queue
Queues are ubiquitous in daily life, and queuing is a typical queue. In this regard, we can roughly know that the queue is a special linear table that only allows data insertion operations at one end and deletion data operations at the other end. The queue has a first-in, first-out nature. Like a stack, a queue has two basic operations – enqueue and dequeue:
Entering the queue: The end where the insertion operation is performed is called the tail of the queue;
Dequeue: The end that performs the deletion operation is called the head of the queue.
2.2 Queue implementation
Similar to implementing a stack, let’s first discuss which data structure is more convenient to use? Should we use a sequence list or a linked list? Should I use a singly linked list or a doubly linked list?
Analyzing the insertion and deletion operations of the queue, we found that the insertion operation is tail insertion, while the deletion operation is head deletion. When implementing sequential lists and linked lists, linked lists are simpler for head deletion operations, while sequential lists require moving data, which is less efficient. Therefore, we use linked lists to implement operations.
Code 1: Linked list implementation queue
The first step is to add the header file:
#include <stdio.h> #include <stdlib.h> #include <stdbool.h> #include <assert.h>
In the second step, let’s establish the data structure of the queue:
typedef int QueDatatype; typedef struct queue { QueDatatype x; struct queue* next; }Queue; //Since we need to use a secondary pointer and we have multiple members, //Then use the structure typedef struct Qnode { Queue*phead; Queue* ptail; //Storage the tail node of the linked list to facilitate tail insertion int size; }Qnode;
The third step is to define the functions of the queue: queue initialization, queue destruction, queue insertion operation, queue deletion operation, returning the head element of the queue, returning the size of the queue, and checking whether the queue is empty.
//Queue initialization void queueinit(Qnode* qnd); //Queue destroyed void queuedestroy(Qnode* qnd); //Queue insertion operation void queuepush(Qnode* qnd, QueDatatype x); //Queue deletion operation void queuepop(Qnode* qnd); //Opposite element of the queue QueDatatype queuefront(Qnode* qnd); //The size of the queue int queuesize(Qnode* qnd); //Check if the queue is empty bool queueueempty(Qnode* qnd);
Queue initialization operation:
void queueinit(Qnode* qnd) { assert(qnd); qnd->phead = qnd->ptail = NULL; qnd->size = 0; }
Queue destruction operation:
void queuedestroy(Qnode* qnd) { assert(qnd); //Destruction must be done from beginning to end Queue* cur = qnd->phead; while (cur) { Queue* del = cur->next; free(cur); cur = del; } // When there is only one node, a wild pointer will appear qnd->phead = qnd->ptail = NULL; qnd->size = 0; }
Queue insertion operation:
void queuepush(Qnode* qnd, QueDatatype x) { assert(qnd); //Create the structure and then operate it Queue* tmp = (Queue*)malloc(sizeof(Queue)); //Prevent creation failure if (tmp == NULL) { perror(tmp); return; } tmp->x = x; tmp->next = NULL; //Link this new node to the linked list if (qnd->phead == NULL) { qnd->phead = qnd->ptail = tmp; } else { qnd->ptail->next = tmp; qnd->ptail = tmp; } qnd->size + + ; }
Queue deletion operation:
void queuepop(Qnode* qnd) { assert(qnd); //The head node cannot be empty assert(qnd->phead); //Secondly, in a process with only one node, wild pointers will appear. Queue* del = qnd->phead; qnd->phead = del->next; free(del); del = NULL; if (qnd->phead == NULL) { qnd->ptail = NULL; } qnd->size--; }
Return the head element of the queue:
QueDatatype queuefront(Qnode* qnd) { assert(qnd); //The queue cannot be empty assert(qnd->phead); return qnd->phead->x; }
Return the size of the queue:
int queuesize(Qnode* qnd) { assert(qnd); return qnd->size; }
Check if the queue is empty:
bool queueueempty(Qnode* qnd) { assert(qnd); //if (qnd->phead ==NULL) //{ // return true; //} //return false; return qnd->phead == NULL; }
Code 2: Array implementation queue
int q[N], hh, tt = -1;
Learning output:
- Using array simulation to implement stack
- Using array simulation to implement queue
- Simulate a queue using a singly linked list