Data structure – stack and queue
- 1. stack
-
- 1.1 The concept and structure of the stack
- 1.2 Implementation of the stack
- 2. queue
-
- 2.1 The concept and structure of the queue
- 2.2 Implementation of the queue
- 3. Exercises on stacks and queues
1. Stack
1.1 The concept and structure of the stack
Stack: A special linear list that only allows insertion and deletion of elements at a fixed end. The end where data insertion and deletion operations are performed 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 principle of LIFO (Last In First Out).
Push stack: The insertion operation of the stack is called push/push/push, and the incoming data is at the top of the stack.
Popping: The deletion operation of the stack is called popping. The output data is also on the top of the stack.
The stack must follow the principle of LIFO (Last In First Out).
Only the top of the stack can be inserted, and the top of the stack can be popped
1.2 Implementation of the stack
A stack can be implemented with an array or a linked list
Linked list: Create a new element, use the next of the new element to point to the previous element, pop the stack to delete the element pointer to the next element, and free the first element. We generally do not use linked lists to implement stacks
Array implementation:
We only need to pay attention to the insertion and deletion at the top of the stack, the implementation of the stack is relatively simple compared to the implementation of the linked list
Header file Stack.h
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>
typedef int STDatatype;
typedef struct Stack
{<!-- -->
STDatatype* a;
int top;
int capacity;
}Stack;
//initialization
void STInit(Stack* ps);
// destroy
void STDestroy(Stack* ps);
//delete
void STPop(Stack* ps);
//insert
void STPush(Stack* ps, STDatatype x);
// calculate the number
int STSize(Stack* ps);
//Check if it is empty
bool STEmpty(Stack* ps);
// pop out
STDatatype STTop(Stack* ps);
Stack.c
#define _CRT_SECURE_NO_WARNINGS
#include "Stack.h"
//initialization
void STInit(Stack* ps)
{<!-- -->
assert(ps);
ps->a = (STDatatype*)malloc(sizeof(STDatatype) * 4);
if (ps->a == NULL)
{<!-- -->
printf("malloc fail");
return;
}
ps->capacity = 4;
ps->top = 0;
}
// destroy
void STDestroy(Stack* ps)
{<!-- -->
assert(ps);
free(ps->a);
ps->a = NULL;
ps->capacity = 0;
ps->top = 0;
}
//insert
void STPush(Stack* ps, STDatatype x)
{<!-- -->
assert(ps);
if (ps->top == ps->capacity)
{<!-- -->
STDatatype* tmp = (STDatatype*)realloc(ps->a,sizeof(STDatatype) * ps->capacity * 2);
if (tmp == NULL)
{<!-- -->
perror("malloc fail");
return;
}
ps->a = tmp;
ps->capacity *= 2;
}
ps->a[ps->top] = x;
ps->top ++ ;
}
//Check if it is empty
bool STEmpty(Stack* ps)
{<!-- -->
assert(ps);
return ps->top == 0;
}
//delete
void STPop(Stack* ps)
{<!-- -->
assert(ps);
assert(!STEmpty(ps));
ps->top--;
}
// calculate the number
int STSize(Stack* ps)
{<!-- -->
assert(ps);
return ps->top;
}
// pop out
STDatatype STTop(Stack* ps)
{<!-- -->
assert(ps);
assert(!STEmpty(ps));
return ps->a[ps->top - 1];
}
test.c
Here is the test case to check whether the code has bugs
#define _CRT_SECURE_NO_WARNINGS
#include "Stack.h"
void test1()
{<!-- -->
Stack st;
STInit( &st);
STPush( &st, 1);
printf("%d ", STTop( &st));
STPop( & st);
STPush( &st, 2);
STPush( &st, 3);
printf("%d ", STTop( &st));
STPop( & st);
STPush( &st, 4);
STPush( &st, 5);
printf("%d\
", STSize( &st));
while (!STEmpty( &st))
{<!-- -->
printf("%d ", STTop( &st));
STPop( & st);
}
STDestroy( &st);
}
int main()
{<!-- -->
test1();
return 0;
}
2. Queue
2.1 The concept and structure of the queue
Queue: A special linear table that only allows inserting data operations at one end and deleting data operations at the other end. The queue has a first-in-first-out FIFO (First In First Out). The end of the delete operation is called the head of the queue
2.2 Implementation of queue
Queues can also be implemented in the structure of arrays and linked lists. It is better to use the structure of linked lists, because if you use the structure of arrays, the efficiency will be relatively low when the data is output from the queue at the head of the array.
If we use a linked list to implement, then we have to write two pointers, one pointing to the head of the queue for leaving the queue, and one pointing to the end of the queue for entering the queue
Queue.h
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>
typedef int QDatatype;
typedef struct QueueNode
{<!-- -->
struct QueueNode* next;
QDatatype a;
}QNode;
typedef struct Queue
{<!-- -->
QNode* head;
QNode* tail;
int sz;
} Queue;
//initialization
void QueueInit(Queue* qp);
//destroy
void Queuedestroy(Queue* qp);
//insert
void QueuePush(Queue* qp, QDatatype x);
//delete
void QueuePop(Queue* qp);
//judgment empty
bool QueueEmpty(Queue* qp);
// calculate the number
int QueueSize(Queue* qp);
// first element
QDatatype QueueFront(Queue* qp);
// last element
QDatatype QueueBack(Queue* qp);
Queue.c
#define _CRT_SECURE_NO_WARNINGS
#include "Queue.h"
//initialization
void QueueInit(Queue* qp)
{<!-- -->
assert(qp);
qp->head = qp->tail = NULL;
qp->sz = 0;
}
//destroy
void Queuedestroy(Queue* qp)
{<!-- -->
assert(qp);
QNode* cur = qp->head;
while (cur)
{<!-- -->
QNode* next = cur->next;
free(cur);
cur = next;
}
qp->head = qp->tail = NULL;
qp->sz = 0;
}
//insert
void QueuePush(Queue* qp, QDatatype x)
{<!-- -->
QNode* newnode = (QNode*)malloc(sizeof(QNode));
if (newnode == NULL)
{<!-- -->
perror("malloc fail");
return;
}
newnode->next = NULL;
newnode->a = x;
if (qp->head == NULL)
{<!-- -->
assert(qp->tail == NULL);
qp->head = qp->tail = newnode;
}
else
{<!-- -->
qp->tail->next = newnode;
qp->tail = newnode;
}
qp->sz + + ;
}
//delete
void QueuePop(Queue* qp)
{<!-- -->
assert(qp);
assert(qp->head);
/*
QNode* next = qp->head->next;
free(qp->head);
qp->head = next;
qp->sz--;
if (qp->head == NULL)
qp->head = qp->tail = NULL;
*/
if (qp->head->next == NULL)
{<!-- -->
free(qp->head);
qp->tail = qp->head = NULL;
}
else
{<!-- -->
QNode* next = qp->head->next;
free(qp->head);
qp->head = next;
}
qp->sz--;
}
//judgment empty
bool QueueEmpty(Queue* qp)
{<!-- -->
assert(qp);
return qp->sz == 0;
}
// calculate the number
int QueueSize(Queue* qp)
{<!-- -->
assert(qp);
return qp->sz;
}
// first element
QDatatype QueueFront(Queue* qp)
{<!-- -->
assert(qp);
assert(!QueueEmpty(qp));
return qp->head->a;
}
// last element
QDatatype QueueBack(Queue* qp)
{<!-- -->
assert(qp);
assert(!QueueEmpty(qp));
return qp->tail->a;
}
test.c
Here is the test case to check whether the code has bugs
#define _CRT_SECURE_NO_WARNINGS
#include "Queue.h"
void test1()
{<!-- -->
Queue q1;
QueueInit( &q1);
QueuePush( &q1, 1);
QueuePush( &q1, 2);
QueuePush( &q1, 3);
QueuePush( &q1, 4);
QueuePush( &q1, 5);
printf("%d ", QueueBack( & amp;q1));
while (!QueueEmpty( &q1))
{<!-- -->
printf("%d ", QueueFront( & amp;q1));
QueuePop( &q1);
}
printf("%d ", QueueSize( &q1));
}
int main()
{<!-- -->
test1();
return 0;
}
3. Exercises on stacks and queues
Designing a Circular Queue Topic
Design circular queue explanation