当前位置：网站首页>Basic introduction of stack and queue and C language implementation of functions such as creation, destruction, entry and exit, counting the number of elements, viewing elements, etc., as well as stac
Basic introduction of stack and queue and C language implementation of functions such as creation, destruction, entry and exit, counting the number of elements, viewing elements, etc., as well as stac
2022-08-05 07:26:00 【kennan_pro】
一、栈和队列介绍
栈和队列是两种重要的线性结构,从数据结构来看,They are also linear tables,Their peculiarity is that their basic operations are subsets of linear tables,also inLinear table with limited functionality,Also known as a restricted data structure.
But from a data type perspective,They are not quite the same as linear tables,Sometimes they are used as rules for managing data.
二、栈结构
1、Introduction to stack structure
栈（stack) Is limited to insert or delete operations and linear tables only at the end of the table（Only one port can enter and exit data）,Footer and header have special meaning to stack,The footer is called栈顶,The header is called栈底,An empty table with no elements is called空栈,The number of elements reaches the stack capacity满栈,Data is added to the stack called入栈、压栈,Data is removed from the stack called出栈、弹栈,Due to the rules for special addition and removal of stack elements,Therefore, the elements of the stack will be first in, last out,简称为LIFO（Last in first out）.
2、The functions of the stack structure
1、创建栈
2、销毁栈
3、栈是否为空
4、栈是否为满
5、入栈
6、出栈
8、查看栈顶元素
9、栈元素数量
注：Only the sequential stack structure needs to determine whether the stack is full.
3、The sequential representation and implementation of the stack structure
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define TYPE int
typedef struct StackArray
{
TYPE* base;
int top;
size_t cap;
}StackArray;
// 创建栈
StackArray* create_stack(size_t cap)
{
// The reason why the member pointer is used is to take into account the written test questions
StackArray* stack = malloc(sizeof(StackArray));
stack->base = malloc(sizeof(TYPE)*cap);
stack->cap = cap;
// The stack determined by the initial value is empty、栈满、入栈、When looking at the top of the stacktop的操作,
stack->top = -1;
return stack;
}
// 销毁栈
void destroy_stack(StackArray* stack)
{
free(stack->base);
free(stack);
}
// 判断栈是否为空
bool empty_stack(StackArray* stack)
{
// 因为top的初始值是-1
return 0 > stack->top;
}
// 判断栈是否为满
bool full_stack(StackArray* stack)
{
// 同上
return stack->cap == stack->top+1;
}
// 入栈
bool push_stack(StackArray* stack,TYPE val)
{
if(full_stack(stack))
return false;
// 同上
stack->base[++stack->top] = val;
return true;
}
// 出栈
bool pop_stack(StackArray* stack)
{
if(empty_stack(stack))
return false;
stack->top--;
return true;
}
// Count the number of stack elements
size_t size_stack(StackArray* stack)
{
return stack->top+1;
}
// 查看栈顶
bool top_stack(StackArray* stack,TYPE* ptr)
{
if(empty_stack(stack))
return false;
*ptr = stack->base[stack->top];
return true;
}
int main(int argc,const char* argv[])
{
int num;
StackArray* stack = create_stack(10);
for(int i=0; i<10; i++)
{
push_stack(stack,i);
if(top_stack(stack,&num))
printf("top %d\n",num);
}
printf("----------------------\n");
while(!empty_stack(stack))
{
top_stack(stack,&num);
printf("top %d\n",num);
pop_stack(stack);
}
}Frequently asked questions：
栈的压入、Pop-up sequence judgment,入栈顺序：1 2 3 4 5 Can the pop order be yes：1 2 3 5 4
bool push_pop_order(int* arr1,int* arr2,size_t len)
{
StackArray* stack = create_stack(len);
int num;
for(int i=0,j=0; i<len; i++)
{
push_stack(stack,arr1[i]);
while(top_stack(stack,&num) && num == arr2[j] && pop_stack(stack))
j++;
}
return empty_stack(stack);
}
bool IsPopOrder(int* pushV, int pushVLen, int* popV, int popVLen )
{
if(pushVLen != popVLen)
return false;
int stack[popVLen] , top = -1;
for(int i=0,j=0; i<pushVLen; i++)
{
stack[++top] = pushV[i];
while(top>=0 && stack[top] == popV[j])
{
top--;
j++;
}
}
return 0 > top;
}
bool IsPopOrder(vector<int> pushV,vector<int> popV)
{
stack<int> s;
for(int i=0,j=0; i<pushV.size(); i++)
{
s.push(pushV[i]);
while(!s.empty() && s.top()==popV[j])
{
s.pop();
j++;
}
}
return s.empty();
}4、Chain representation and implementation of stack structure
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define TYPE int
typedef struct Node
{
TYPE data;
struct Node* next;
}Node;
Node* create_node(TYPE data)
{
Node* node = malloc(sizeof(Node));
node->data = data;
node->next = NULL;
return node;
}
typedef struct StackList
{
Node* top;
size_t cnt;
}StackList;
// 创建栈
StackList* create_stack(void)
{
StackList* stack = malloc(sizeof(StackList));
stack->top = NULL;
stack->cnt = 0;
return stack;
}
// 销毁栈
void destroy_stack(StackList* stack)
{
while(NULL!=stack->top)
{
Node* node = stack->top;
stack->top = node->next;
free(node);
}
free(stack);
}
// 栈空
bool empty_stack(StackList* stack)
{
return NULL == stack->top;
}
// 入栈
void push_stack(StackList* stack,TYPE data)
{
Node* node = create_node(data);
node->next = stack->top;
stack->top = node;
stack->cnt++;
}
// 出栈
bool pop_stack(StackList* stack)
{
if(empty_stack(stack))
return false;
Node* node = stack->top;
stack->top = node->next;
free(node);
stack->cnt--;
return true;
}
// 查看栈顶
TYPE top_stack(StackList* stack)
{
return stack->top->data;
}
// 元素数量
size_t size_stack(StackList* stack)
{
return stack->cnt;
}
int main(int argc,const char* argv[])
{
StackList* stack = create_stack();
for(int i=0; i<10; i++)
{
push_stack(stack,i);
if(!empty_stack(stack))
printf("top %d\n",top_stack(stack));
}
printf("-------------------\n");
while(!empty_stack(stack))
{
printf("top %d\n",top_stack(stack));
pop_stack(stack);
}
}5、栈的应用
1、内存管理,such as stack memory,It is called stack memory because it follows the LIFO rule of stack,It supports function calls,When passing parameters, the function pushes the parameters into the stack memory first,After the jump, the parameters are popped from the stack memory.
2、特殊的算法,例如：进制转换、表达式解析、迷宫求解.
三、队列
1、队列介绍
It is the exact opposite of stack,是一种先进先出的线性表,It has two ports added、删除元素,A port can only add elements,is called enqueuing,This port is called the tail of the queue,Another port can only be deleted,is called dequeuing,This port is called the head of the line.
2、The functions of the queue structure
1、创建队列
2、销毁队列
3、队列是否为空
4、队列是否为满
5、入队
6、出队
8、查看队头元素
9、查看队尾元素
10、队列元素数量
注：Only the sequential stack structure needs to determine whether the queue is full.
3、Chain representation and implementation of queue structures
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define TYPE int
typedef struct Node
{
TYPE data;
struct Node* next;
}Node;
Node* create_node(TYPE data)
{
Node* node = malloc(sizeof(Node));
node->data = data;
node->next = NULL;
return node;
}
typedef struct QueueList
{
Node* front;
Node* rear;
}QueueList;
// 创建队列
QueueList* create_queue(void)
{
QueueList* queue = malloc(sizeof(QueueList));
queue->front = NULL;
queue->rear = NULL;
return queue;
}
// 销毁队列
void destroy_queue(QueueList* queue)
{
while(NULL != queue->front)
{
Node* node = queue->front;
queue->front = node->next;
free(node);
}
free(queue);
}
// 判断队列是否为空
bool empty_queue(QueueList* queue)
{
return NULL == queue->front;
}
// 入队
void push_queue(QueueList* queue,TYPE data)
{
Node* node = create_node(data);
if(empty_queue(queue))
{
queue->front = node;
queue->rear = node;
return;
}
queue->rear->next = node;
queue->rear = node;
}
// 出队
bool pop_queue(QueueList* queue)
{
if(empty_queue(queue))
return false;
Node* node = queue->front;
queue->front = node->next;
free(node);
}
// 查看队头元素,Before calling this function, check whether the queue is empty,Otherwise, a null pointer will be used
TYPE front_queue(QueueList* queue)
{
return queue->front->data;
}
// 查看队尾元素,Before calling this function, check whether the queue is empty,Otherwise, wild pointers will be used
TYPE rear_queue(QueueList* queue)
{
return queue->rear->data;
}
// 队列元素数量
size_t size_queue(QueueList* queue)
{
size_t size = 0;
for(Node* n=queue->front; NULL!=n; n=n->next)
{
size++;
}
return size;
}
int main(int argc,const char* argv[])
{
QueueList* queue = create_queue();
for(int i=0; i<10; i++)
{
push_queue(queue,i);
printf("front:%d rear:%d\n",
front_queue(queue),
rear_queue(queue));
}
printf("---------------------\n");
while(!empty_queue(queue))
{
printf("front:%d rear:%d\n",
front_queue(queue),
rear_queue(queue));
pop_queue(queue);
}
}4、顺序队列的表示与实现
The top index of the sequential stack will increase as elements are pushed onto the stack,Element popping is reduced,This allows space to be reused,The head pointer and tail pointer of the sequential queue,It will increase as elements are enqueued and dequeued,无法重复使用,And form a one-time data structure.
为了避免这种情况,When the trailing subscript of the queue head subscript reaches the end of the storage space,Find a way to subscript the tail of the team that is subscripted by the head of the team"回头",It is to treat the storage space of the sequential queue as one"环形",循环使用,So a sequential queue is also called a circular queue.
Circular queue with counter version：
1、Solved the problem of counting the number of elements
2、Solved the judgment that the queue is empty、full state problem
3、The downside is the addition of a member,在创建、入队、Operate it when leaving the queue.
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define TYPE int
typedef struct QueueArray
{
TYPE* base;
int front;
int rear;
size_t cnt;
size_t cap;
}QueueArray;
// 创建队列
QueueArray* create_queue(size_t cap)
{
QueueArray* queue = malloc(sizeof(QueueArray));
queue->base = malloc(sizeof(TYPE)*cap);
queue->cap = cap;
queue->front = 0;
queue->rear = -1;
queue->cnt = 0;
return queue;
}
// 销毁队列
void destroy_queue(QueueArray* queue)
{
free(queue->base);
free(queue);
}
// 判断队列是否为空
bool empty_queue(QueueArray* queue)
{
return 0 == queue->cnt;
}
// 判断队列是否为满
bool full_queue(QueueArray* queue)
{
return queue->cnt == queue->cap;
}
// 入队
bool push_queue(QueueArray* queue,TYPE data)
{
if(full_queue(queue))
return false;
queue->rear = (queue->rear+1)%queue->cap;
queue->base[queue->rear] = data;
queue->cnt++;
return true;
}
// 出队
bool pop_queue(QueueArray* queue)
{
if(empty_queue(queue))
return false;
queue->front = (queue->front+1)%queue->cap;
queue->cnt--;
return true;
}
// 查看队头元素,判断队列是否为空
TYPE front_queue(QueueArray* queue)
{
return queue->base[queue->front];
}
// 查看队尾元素
TYPE rear_queue(QueueArray* queue)
{
return queue->base[queue->rear];
}
// 队列元素数量
size_t size_queue(QueueArray* queue)
{
return queue->cnt;
}
int main(int argc,const char* argv[])
{
QueueArray* queue = create_queue(10);
for(int i=0; i<10; i++)
{
push_queue(queue,i);
printf("front:%d rear:%d\n",
front_queue(queue),
rear_queue(queue));
}
printf("---------------------\n");
while(!empty_queue(queue))
{
printf("front:%d rear:%d\n",
front_queue(queue),
rear_queue(queue));
pop_queue(queue);
}
printf("---------------------\n");
for(int i=0; i<10; i++)
{
push_queue(queue,i);
printf("front:%d rear:%d\n",
front_queue(queue),
rear_queue(queue));
}
printf("---------------------\n");
while(!empty_queue(queue))
{
printf("front:%d rear:%d\n",
front_queue(queue),
rear_queue(queue));
pop_queue(queue);
}
destroy_queue(queue);
return 0;
} Circular queue without counter version：
1、How to judge the queue is empty、状态?
Initialize the line header subscript to front=0,The trailing subscript is also initializedrear=0,The judgment condition when the queue is empty isfront == rear,But the use of random queues,The same is true for the judgment when the queue is fullfront == rear.
The solution is to leave the last position of the queue empty and unused,This way the queue is fullfront == rear+1;
2、How to count the number of queue elements?
(rear-front+cap)%cap
3、查看队尾元素
base[(read-1+cap)%cap]
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define TYPE int
typedef struct QueueArray
{
TYPE* base;
int front;
int rear;
size_t cap;
}QueueArray;
// 创建队列
QueueArray* create_queue(size_t cap)
{
QueueArray* queue = malloc(sizeof(QueueArray));
queue->base = malloc(sizeof(TYPE)*cap+1);
queue->cap = cap+1;
queue->front = 0;
queue->rear = 0;
return queue;
}
// 销毁队列
void destroy_queue(QueueArray* queue)
{
free(queue->base);
free(queue);
}
// 判断队列是否为空
bool empty_queue(QueueArray* queue)
{
return queue->front == queue->rear;
}
// 判断队列是否为满
bool full_queue(QueueArray* queue)
{
return queue->front == (queue->rear+1)%queue->cap;
}
// 入队
bool push_queue(QueueArray* queue,TYPE data)
{
if(full_queue(queue))
return false;
queue->base[queue->rear] = data;
queue->rear = (queue->rear+1)%queue->cap;
return true;
}
// 出队
bool pop_queue(QueueArray* queue)
{
if(empty_queue(queue))
return false;
queue->front = (queue->front+1)%queue->cap;
return true;
}
// 查看队头元素,判断队列是否为空
TYPE front_queue(QueueArray* queue)
{
return queue->base[queue->front];
}
// 查看队尾元素
TYPE rear_queue(QueueArray* queue)
{
return queue->base[(queue->rear - 1 + queue->cap) % queue->cap];
}
// 队列元素数量
size_t size_queue(QueueArray* queue)
{
return (queue->rear - queue->front + queue->cap) % queue->cap;
}
int main(int argc,const char* argv[])
{
QueueArray* queue = create_queue(10);
for(int i=0; i<10; i++)
{
push_queue(queue,i);
printf("front:%d rear:%d\n",
front_queue(queue),
rear_queue(queue));
}
printf("---------------------\n");
while(!empty_queue(queue))
{
printf("front:%d rear:%d\n",
front_queue(queue),
rear_queue(queue));
pop_queue(queue);
}
printf("---------------------\n");
for(int i=0; i<10; i++)
{
push_queue(queue,i);
printf("front:%d rear:%d\n",
front_queue(queue),
rear_queue(queue));
}
printf("---------------------\n");
while(!empty_queue(queue))
{
printf("front:%d rear:%d\n",
front_queue(queue),
rear_queue(queue));
pop_queue(queue);
}
destroy_queue(queue);
}4、队列的应用
The queue structure is generally used in business processing,例如：银行叫号系统,12306购票系统,E-commerce order processing, etc.
边栏推荐
- 2006年星座运势全解-射手
- 学习机赛道加速：请“卷”产品，不要“卷”营销
- 文本特征化方法总结
- After the firewall iptable rule is enabled, the system network becomes slow
- ARM Cortex-M上的Trace跟踪方案
- 【深度学习实践（一）】安装TensorFlow
- Hash these knowledge you should also know
- Unity—物理引擎+“武器模块”
- GAN generates anime avatar Pytorch
- After working for 3 years, I recalled the comparison between the past and the present when I first started, and joked about my testing career
猜你喜欢
随机推荐
binary search tree problem
Vulnhub靶机：HA_ NARAK
Unity—物理引擎+“武器模块”
browserslist 选项的目的是什么？
常用的遍历map的方法
MobileNetV1架构解析
MAYA大炮建模
Vulnhub target drone: HA_ NARAK
TCP sticky packet unpacking problem + solution
TRACE32——Go.direct
Chapter3、色调映射
请问my sql如何把两个表的内容集合在一起啊？
［上海］招聘.Net高级软件工程师＆BI数据仓库工程师（急）
protobuf根据有关联的.proto文件进行编译
Flink学习12：DataStreaming API
In the anaconda Promat interface, import torch is passed, and the error is reported in the jupyter notebook (only provide ideas and understanding!)
An IP conflict is reported after installing the software on a dedicated computer terminal
How to avoid online memory leaks
It turns out that Maya Arnold can also render high-quality works!Awesome Tips
MySQL: order by sorting query, group by grouping query