Foreword [must read]
Anyone who has learned stacks and queues is welcome to visit. . . [Baozi who has not learned it may not understand it well, because there are few comments and many implementations. [Mainly because of laziness (roll 0)
1. Implementation of stack
Let’s build a stack
Because the stack only operates on the top, it is OK to use the form of a sequence list. If you use a linked list, it will be traversed from beginning to end. [It’s too tiring. Why use a dynamic array? Because we don’t have enough space, we will open it up. If it is static, then It’s too inconvenient
1. Create a stack in the form of a dynamic array
typedef int STDataType;//Use STDataType to represent the int type, mainly to facilitate global replacement of types
typedef struct Stack
{<!-- -->
STDataType* a;//array
int top; // top of stack
int capacity; // capacity
}Stack;
2. A series of stack operation functions
Don’t be scared, it’s actually quite easy.
//Initialize stack void StackInit(Stack* ps); //Determine if the stack is full and expand it void JugdeFull(Stack* ps); //Push to stack void StackPush(Stack* ps, STDataType data); // pop off the stack void StackPop(Stack* ps); // Get the top element of the stack STDataType StackTop(Stack* ps); // Get the number of valid elements in the stack int StackSize(Stack* ps); // Check whether the stack is empty. If it is empty, return a non-zero result. If it is not empty, return 0. int StackEmpty(Stack* ps); // Destroy the stack void StackDestroy(Stack* ps);
3. Implementation of stack related functions
1.Initialization stack
The so-called initialization is to give a clear value to each member variable in the stack (structure). Initialization is very important. After creating a stack variable, if you start an operation without initializing it, then you will be waiting to change the code while eating instant noodles~
//Initialize stack
void StackInit(Stack* ps)
{<!-- -->
ps->a = NULL;
ps->capacity = ps->top = 0;
}
2. Determine if the stack is full
The function to determine if the stack is full is not a function for basic stack operations. However, since many functions need to determine whether the stack is full when calling, a separate function is usually encapsulated to improve the reusability of the code.
//Judge that the stack is full and expand it
void JugdeFull(Stack* ps)
{<!-- -->
if (ps->top == ps->capacity)
{<!-- -->
//Expansion: If the capacity is 0 at the beginning, then give it a capacity of 4. If it is not 0 capacity at the beginning, expand it to 2 times the original capacity.
int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
//Why do we need to create a new pointer variable here to receive the newly expanded space instead of using the original pointer variable? Because the realloc function may fail to expand, which will cause the original pointer to be empty and the original space cannot be found. Just steal the chicken but lose the rice
STDataType* temp = (STDataType*)realloc(ps->a,sizeof(STDataType) * newcapacity);
if (temp == NULL)
{<!-- -->
perror("realloc fail:");
exit(-1);
}
//Only when the expansion is successful can the address of the new space be handed over to the original pointer.
ps->a = temp;
ps->capacity = newcapacity;
}
}
3.Push into the stack
Assert function assert remember to quote the header file
//Push to stack
void StackPush(Stack* ps, STDataType data)
{<!-- -->
assert(ps);
// Determine if the stack is full, expand the stack if it is full
JugdeFull(ps);
ps->a[ps->top] = data;
ps->top + + ;
}
4.Push
//Pop from the stack
void StackPop(Stack* ps)
{<!-- -->
assert(ps);
assert(ps->top > 0);//Determine the stack is not empty
ps->top--;//Pop;
}
5. Get the top element of the stack
//Get the top element of the stack
STDataType StackTop(Stack* ps)
{<!-- -->
assert(ps);//Determine whether the pointer is empty
assert(ps->top > 0);//Determine the stack is not empty
STDataType ret = ps->a[ps->top-1];
return ret;
}
6. Get the number of valid elements in the stack
//Get the number of valid elements in the stack
int StackSize(Stack* ps)
{<!-- -->
assert(ps);
return ps->top;
}
7. Determine if the stack is empty
//Check whether the stack is empty. If it is empty, return a non-zero result. If it is not empty, return 0.
int StackEmpty(Stack* ps)
{<!-- -->
assert(ps);
if (ps->top == 0)
{<!-- -->
return -1;
}
return 0;
}
8. Destroy the stack
//Destroy the stack
void StackDestroy(Stack* ps)
{<!-- -->
assert(ps);
ps->top = ps->capacity = 0;
free(ps->a);
ps->a = NULL;
}
3. Briefly test your stack
void test1()
{<!-- -->
Stackst;
StackInit(&st);
StackPush( &st, 1);
StackPush( &st, 2);
StackPush( &st, 3);
while (st.top)
{<!-- -->
printf("%d->", StackTop( & amp;st));
StackPop(&st);//After obtaining the top element of the stack during the test, it must be popped out of the stack, otherwise the while loop will become an infinite loop.
}
printf("\
");
StackDestroy(&st);
}
int main()
{<!-- -->
test1();
return 0;
}
2. Implementation of Queue
1. Create a queue in the form of a singly linked list
You can think of the first structure as a node, which is a person in the queue. The second structure is an entire queue. From a macro perspective, we know who its head is, who its tail is, and how many people it consists of. [Data structure is an abstract concept. If you still can’t understand it, it must be because you are not abstract enough~
typedef int QDataType;
//Chain structure: represents the queue
typedef struct QListNode
{<!-- -->
struct QListNode* next;
QDataType data;
}QNode;
//Queue structure
typedef struct Queue
{<!-- -->
QNode* front;
QNode* rear;
int size;
}Queue;
2. A series of queue-related operation functions
In fact, every data structure has its own characteristics. There are only a few main operations. Don’t worry about not remembering them. Just write whichever function you use.
//Initialize queue void QueueInit(Queue* q); //Enter the end of the queue into the queue void QueuePush(Queue* q, QDataType data); //The head of the queue is dequeued void QueuePop(Queue* q); // Get the head element of the queue QDataType QueueFront(Queue* q); // Get the tail element of the queue QDataType QueueBack(Queue* q); // Get the number of valid elements in the queue int QueueSize(Queue* q); // Check whether the queue is empty. If it is empty, return a non-zero result. If it is not empty, return 0. bool QueueEmpty(Queue* q); // Destroy the queue void QueueDestroy(Queue* q);
3. Implementation of queue-related functions
1.Initialize queue
Note here: What we initialize is the structure representing the queue! ! ! It is not a structure representing nodes. We will create and initialize nodes one by one. You can also write a separate initialization node, and then call it every time a node is opened.
//Initialize queue
void QueueInit(Queue* q)
{<!-- -->
assert(q);
q->front = q->rear = NULL;
q->size = 0;
}
2. The end of the queue enters the queue
//Enter the end of the queue into the queue
void QueuePush(Queue* q, QDataType data)
{<!-- -->
QNode* newnode = (QNode*)malloc(sizeof(QNode));//Create a new node
//Initialize node
newnode->data = data;
newnode->next = NULL;
//Determine whether the queue is empty. If the queue is empty, the enqueue node will be regarded as the head node.
if (q->front == NULL & amp; & amp; q->rear == NULL)
{<!-- -->
q->front = newnode;
q->rear = newnode;
}
else
{<!-- -->
q->rear->next = newnode;
q->rear = newnode;
}
q->size + + ;
}
3. The head of the queue dequeues
Note: You may need to modify the tail pointer when dequeuing. When reaching the last node, set both the head and tail pointers to empty.
//The head of the queue dequeues
void QueuePop(Queue* q)
{<!-- -->
assert(q);
assert(!QueueEmpty(q));//Judge that the queue is not empty
if (q->front->next == NULL)//There is only one node
{<!-- -->
free(q->front);
q->front = NULL;
q->rear = NULL;
}
else
{<!-- -->
QNode* next = q->front->next;
free(q->front);
q->front = next;
}
q->size--;
}
4. Get the head element
//Get the head element of the queue
QDataType QueueFront(Queue* q)
{<!-- -->
assert(q);
assert(!QueueEmpty(q));//Judge that the queue is not empty
\t
return q->front->data;
}
5. Get the tail element
//Get the tail element of the queue
QDataType QueueBack(Queue* q)
{<!-- -->
assert(q);
assert(!QueueEmpty(q));//Judge that the queue is not empty
\t
return q->rear->data;
}
6. Get the number of valid elements in the queue
//Get the number of valid elements in the queue
int QueueSize(Queue* q)
{<!-- -->
assert(q);
return q->size;
}
7. Determine whether the queue is empty
//Check whether the queue is empty, return a non-zero result if it is empty, return 0 if it is not empty
bool QueueEmpty(Queue* q)
{<!-- -->
assert(q);
return q->front == NULL;
}
8. Destroy the queue
//Destroy the queue
void QueueDestroy(Queue* q)
{<!-- -->
assert(q);
QNode* cur = q->front;
while (cur)
{<!-- -->
QNode* next = cur->next;
free(cur);
cur = next;
}
q->front = q->rear = NULL;
q->size = 0;
}
3. Stack implementation queue
1.Principle
The stack implements the queue, which is to implement queue-related operations, such as entering the queue, dequeuing, obtaining the head element, etc., while complying with the first-in-first-out rule of the queue.
1. Prepare two stacks
2. One stack is used specifically for push, and one stack is used for pop.
The order of pushing onto the stack is 1234, which is equivalent to the order of entering into the queue, because all entries and exits at this time are for the queue. Then there is the order of popping out. Direct popping out of stack 1 means last in first out (4321), which does not meet the requirements of the queue. Therefore, we need to import the data from stack 1 into stack 2 first. At this time, popping out of stack 2 is the order that the queue wants. 1234. If there is something newly added to the stack, let it enter stack 1. When stack 2 is popped out and is empty, the data of stack 1 is imported into stack 2.
2. Code implementation
1. Stack creation and basic operation code
//Support dynamically growing stack
typedef int STDataType;
typedef struct Stack
{
STDataType* a;
int top; // top of stack
int capacity; // capacity
}Stack;
//Initialize stack
void StackInit(Stack* ps);
//Determine if the stack is full and expand it
void JugdeFull(Stack* ps);
// push to stack
void StackPush(Stack* ps, STDataType data);
// pop off the stack
void StackPop(Stack* ps);
// Get the top element of the stack
STDataType StackTop(Stack* ps);
// Get the number of valid elements in the stack
int StackSize(Stack* ps);
// Check whether the stack is empty. If it is empty, return a non-zero result. If it is not empty, return 0.
int StackEmpty(Stack* ps);
// Destroy the stack
void StackDestroy(Stack* ps);
//Initialize stack
void StackInit(Stack* ps)
{<!-- -->
ps->a = NULL;
ps->capacity = ps->top = 0;
}
//Determine if the stack is full and expand it
void JugdeFull(Stack* ps)
{
if (ps->top == ps->capacity)
{
//Expansion
int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
STDataType* temp = (STDataType*)realloc(ps->a,sizeof(STDataType) * newcapacity);
if (temp == NULL)
{
perror("realloc fail:");
exit(-1);
}
ps->a = temp;
ps->capacity = newcapacity;
}
}
//Push to stack
void StackPush(Stack* ps, STDataType data)
{<!-- -->
assert(ps);
// Determine if the stack is full, expand the stack if it is full
JugdeFull(ps);
ps->a[ps->top] = data;
ps->top + + ;
}
// pop off the stack
void StackPop(Stack* ps)
{
assert(ps);
assert(ps->top > 0);//Determine the stack is not empty
ps->top--;//Pop;
}
// Get the top element of the stack
STDataType StackTop(Stack* ps)
{
assert(ps);//Determine whether the pointer is empty
assert(ps->top > 0);//Determine the stack is not empty
STDataType ret = ps->a[ps->top-1];
return ret;
}
// Get the number of valid elements in the stack
int StackSize(Stack* ps)
{
assert(ps);
return ps->top;
}
// Check whether the stack is empty. If it is empty, return a non-zero result. If it is not empty, return 0.
int StackEmpty(Stack* ps)
{
assert(ps);
if (ps->top == 0)
{
return -1;
}
return 0;
}
// Destroy the stack
void StackDestroy(Stack* ps)
{
assert(ps);
ps->top = ps->capacity = 0;
free(ps->a);
ps->a = NULL;
}
2. Encapsulate into a queue
typedef struct {<!-- -->
Stack PushST;
Stack PopST;
}MyQueue;
3. Create a queue
MyQueue* myQueueCreate() {<!-- -->
MyQueue* Qu = (MyQueue*)malloc(sizeof(MyQueue));
StackInit( & amp;Qu->PushST);
StackInit( & amp;Qu->PopST);
return Qu;
}
4. Function implementation of queue-related operations
void myQueuePush(MyQueue* obj, int x) {<!-- -->
StackPush( & amp;obj->PushST,x);
}
int myQueuePeek(MyQueue* obj) {<!-- -->
//Determine whether PopST is empty. If it is empty, go to the data. If it is not empty, return directly.
if(StackEmpty( & amp;obj->PopST))
{<!-- -->
while(StackSize( & amp;obj->PushST))
{<!-- -->
//Pour the data in the PushST stack into the PopST stack
StackPush( & amp;obj->PopST,StackTop( & amp;obj->PushST));
StackPop( & amp;obj->PushST);
}
}
//Get the top element of the PopST stack, which is the first element of the queue
return StackTop( & amp;obj->PopST);
}
int myQueuePop(MyQueue* obj) {<!-- -->
//Get the first element of the queue
int ret = myQueuePeek(obj);
//Pop the first element from the stack
StackPop( & amp;obj->PopST);
return ret;
}
bool myQueueEmpty(MyQueue* obj) {<!-- -->
return StackEmpty( & amp;obj->PopST) & amp; & amp;StackEmpty( & amp;obj->PushST);
}
void myQueueFree(MyQueue* obj) {<!-- -->
StackDestroy( & amp;obj->PopST);
StackDestroy( & amp;obj->PushST);
free(obj);
}
4. Queue implementation stack
1.Principle
In the same way, a stack is implemented through two queues.
Enter the queue from queue 1, and then import n-1 data into queue 2. The last remaining data that is not imported into queue 2 is the tail element of the queue, which is the top element of the stack.
When entering the queue, put data into the queue that is not empty. Dequeuing is to add data to the empty queue, and then pop the last remaining data directly from the stack. Leetcode original title
2. Code implementation
1. Queue function implementation
typedef int QDataType;
//Chain structure: represents queue
typedef struct QListNode
{<!-- -->
struct QListNode* next;
QDataType data;
}QNode;
//Queue structure
typedef struct Queue
{<!-- -->
QNode* front;
QNode* rear;
int size;
}Queue;
//Initialize the queue
void QueueInit(Queue* q);
//Enter the end of the queue into the queue
void QueuePush(Queue* q, QDataType data);
//The head of the queue is dequeued
void QueuePop(Queue* q);
// Get the head element of the queue
QDataType QueueFront(Queue* q);
// Get the tail element of the queue
QDataType QueueBack(Queue* q);
// Get the number of valid elements in the queue
int QueueSize(Queue* q);
// Check whether the queue is empty. If it is empty, return a non-zero result. If it is not empty, return 0.
bool QueueEmpty(Queue* q);
// Destroy the queue
void QueueDestroy(Queue* q);
//Initialize the queue
void QueueInit(Queue* q)
{<!-- -->
assert(q);
q->front = q->rear = NULL;
q->size = 0;
}
//Enter the end of the queue into the queue
void QueuePush(Queue* q, QDataType data)
{<!-- -->
QNode* newnode = (QNode*)malloc(sizeof(QNode));
newnode->data = data;
newnode->next = NULL;
if (q->front == NULL & amp; & amp; q->rear == NULL)
{<!-- -->
q->front = newnode;
q->rear = newnode;
}
else
{<!-- -->
q->rear->next = newnode;
q->rear = newnode;
}
q->size + + ;
}
//The head of the queue is dequeued
void QueuePop(Queue* q)
{<!-- -->
assert(q);
assert(!QueueEmpty(q));
if (q->front->next == NULL)
{<!-- -->
free(q->front);
q->front = NULL;
q->rear = NULL;
}
else
{<!-- -->
QNode* next = q->front->next;
free(q->front);
q->front = next;
}
q->size--;
}
// Get the head element of the queue
QDataType QueueFront(Queue* q)
{<!-- -->
assert(q);
assert(!QueueEmpty(q));
return q->front->data;
}
// Get the tail element of the queue
QDataType QueueBack(Queue* q)
{<!-- -->
assert(q);
assert(!QueueEmpty(q));
return q->rear->data;
}
// Get the number of valid elements in the queue
int QueueSize(Queue* q)
{<!-- -->
assert(q);
return q->size;
}
// Check whether the queue is empty. If it is empty, return a non-zero result. If it is not empty, return 0.
bool QueueEmpty(Queue* q)
{<!-- -->
assert(q);
return q->front == NULL;
}
// Destroy the queue
void QueueDestroy(Queue* q)
{<!-- -->
assert(q);
QNode* cur = q->front;
while (cur)
{<!-- -->
QNode* next = cur->next;
free(cur);
cur = next;
}
q->front = q->rear = NULL;
q->size = 0;
}
2. Construct a stack using a queue
typedef struct {<!-- -->
Queue q1;
Queue q2;
} MyStack;
``
3. Function implementation of stack
```c
int myStackPop(MyStack* obj) {<!-- -->
Queue* empty = & amp;obj->q1;
Queue* nonempty = & amp;obj->q2;
if (!QueueEmpty( & amp;obj->q1))
{<!-- -->
empty = & amp;obj->q2;
nonempty = & amp;obj->q1;
}
while (QueueSize(nonempty) > 1)
{<!-- -->
QueuePush(empty, QueueFront(nonempty));
QueuePop(nonempty);
}
int top = QueueFront(nonempty);//Get the last data, which is the data on the top of the stack (the end of the queue), and return
QueuePop(nonempty);//Dequeue the last data
return top;
}
int myStackTop(MyStack* obj) {<!-- -->
if (!QueueEmpty( & amp;obj->q1))
{<!-- -->
return QueueBack( & amp;obj->q1);
}
else
{<!-- -->
return QueueBack( & amp;obj->q2);
}
}
bool myStackEmpty(MyStack* obj) {<!-- -->
return QueueEmpty( & amp;obj->q1) & amp; & amp; QueueEmpty( & amp;obj->q2);
}
void myStackFree(MyStack* obj) {<!-- -->
QueueDestroy( & amp;obj->q1);
QueueDestroy( & amp;obj->q2);
free(obj);
}
This is a Leetcode question, and you only need to implement the corresponding function. Queue implementation stack
5. Circular queue
1. Characteristics of circular queue
1. The allocated space is fixed
2. After the element is deleted, the space will not be released and will be recycled.
3. The tail pointer and head pointer will return to 1 when they reach the end.
2. Implementation of circular queue
Circular queues are implemented through arrays. The circular queue includes three parameters, the head of the queue, the tail of the queue, and the number of valid elements.
typedef struct {<!-- -->
int* a;//array
int front;//head
int rear;//tail
int k; //Number of valid data
} MyCircularQueue;
3. Circular queue is empty
4. Insert data into circular queue
5. Delete data from circular queue
6. The circular queue goes to the end and returns to the origin (the same goes for the head and front)
Back to the beginning: rear = (rear + 1)%(k + 1) . k is the number of nodes that can be stored. The node that applies for more is used to determine whether the queue is full.
6. The circular queue is full
7. Find the tail element of circular queue
8. Circular queue code implementation
typedef struct {<!-- -->
int* a;//array
int front;//head
int rear;//tail
int k; //Number of valid data
} MyCircularQueue;
MyCircularQueue* myCircularQueueCreate(int k) {
//Initialize the circular queue
MyCircularQueue* mCQ = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
mCQ->a = (int*)malloc(sizeof(int)*(k + 1));//Create k + 1 space for the array, one of which does not store data
mCQ->front = 0;
mCQ->rear = 0;
mCQ->k = k;
return mCQ;
}
bool myCircularQueueIsFull(MyCircularQueue* obj) {
//Judge stack full
if((obj->rear + 1)%(obj->k + 1)==obj->front)
{
return true;
}
return false;
}
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
//Enter the queue and determine if the stack is full
if(!myCircularQueueIsFull(obj))
{
obj->a[obj->rear] = value;
obj->rear = (obj->rear + 1)%(obj->k + 1);
return true;
}
return false;
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
//Judge that the queue is empty
if(obj->rear==obj->front)
{
return true;
}
return false;
}
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
//Dequeue. Determine if the stack is empty
if(!myCircularQueueIsEmpty(obj))
{
obj->front = (obj->front + 1)%(obj->k + 1);
return true;
}
return false;
}
int myCircularQueueFront(MyCircularQueue* obj) {
if(myCircularQueueIsEmpty(obj))
{
return -1;
}
return obj->a[obj->front];
}
int myCircularQueueRear(MyCircularQueue* obj) {
if(myCircularQueueIsEmpty(obj))
{
return -1;
}
return obj->a[(obj->rear + obj->k)%(obj->k + 1)];
}
void myCircularQueueFree(MyCircularQueue* obj) {
free(obj->a);//Release the dynamically opened array
free(obj);//Release the dynamically opened circular queue
}
Please see the original question Leetcode Circular Queue
Friends who like it please click and follow~