24/07/18数据结构(7.1220)队列实现
双向链表:带头的双向循环链表
插入,删除:O(1)
头插:insert(header -> next)
尾插:insert(header)
头删:erase(header -> next)
尾删:erase(header -> prev)
栈:线性表,后进后出
实现:顺序表,链表
常用实现:顺序表 pushBack --> 入栈 popBack --> 出栈
队列
队列:只允许在一端插入数据操作,在另一端进行删除数据操作的线性表,队列具有先进先出FIFO(first in first out)
入队列:进行插入操作的一端称为队尾
出队列:进行删除操作的一端称为队头
入队:尾插
出队:头删
实现:顺序表, 链表
顺序表:尾插O(1) 头删O(N)
链表:单链表尾插O(N) 头删O(1)
含有尾指针的单链表,尾插O(1) 头删O(1)
常用实现:含有尾指针的单链表
实现一下队列:做三个文件,一个头文件一个接口文件一个测试文件
queue.h
#pragma once
#include <stdlib.h>
typedef int QDataType;
typedef struct QNode{
struct QNode* _next;
QDataType _data;
}QNode;
typedef struct Queue{
QNode* _front;
QNode* _rear;
int _size;
}Queue;
void queueInit(Queue* q);
QNode* creatNode(QDataType data);
void queuePush(Queue* q, QDataType data);
void queuePop(Queue* q);
QDataType queueFront(Queue* q);
QDataType queueBack(Queue* q);
int queueSize(Queue* q);
int queueEmpty(Queue* q);
void queueDestory(Queue* q);
Queue.c
#include"queue.h"
#include<stdio.h>
#include<stdlib.h>
//队列初始化
void queueInit(Queue* q){
//初始化空队列
q->_front = q->_rear = NULL;
q->_size = 0;
}
//创建节点
QNode* creatNode(QDataType data){
QNode* node = (QNode*)malloc(sizeof(QNode));
node->_data = data;
node->_next = NULL;
return node;
}
//入队,从队尾入队
void queuePush(Queue* q, QDataType data){
QNode* node = creatNode(data);
//空队列
if (q->_front == NULL)
q->_front = q->_rear = node;
else{
q->_rear->_next = node;
q->_rear = node;
}
++q->_size;
}
//队头出队 头删
void queuePop(Queue* q){
if (q->_front){
QNode* next = q->_front->_next;
free(q->_front);
q->_front = next;
//删除之后是否为空表
if (q->_front == NULL)
q->_rear = NULL;
--q->_size;
}
}
//获取队头元素
QDataType queueFront(Queue* q){
return q->_front->_data;
}
//获取队尾元素
QDataType queueBack(Queue* q){
return q->_rear->_data;
}
int queueSize(Queue* q){
//int num = 0;
//QNode* cur = q->_front;
//while (cur){
// ++num;
// cur = cur->_next;
//}
//return num;
return q->_size;
}
//队列是否为空
int queueEmpty(Queue* q){
if (q->_front == NULL)
return 1;
return 0;
}
//销毁
void queueDestory(Queue* q){
//从头开始进行释放
QNode* cur = q->_front;
while (cur){
QNode* next = cur->_next;
free(cur);
cur = next;
}
q->_front = q->_rear = NULL;
q->_size = 0;
}
text.c
#include"queue.h"
#include<stdio.h>
#include<stdlib.h>
void test(){
Queue q;
queueInit(&q);
queuePush(&q, 1);
queuePush(&q, 2);
queuePush(&q, 3);
queuePush(&q, 4);
queuePop(&q);
queuePop(&q);
queuePop(&q);
queuePop(&q);
queuePush(&q, 1);
queuePush(&q, 2);
queuePush(&q, 3);
queuePush(&q, 4);
}
void test2(){
Queue q;
queueInit(&q);
queuePush(&q, 1);
queuePush(&q, 2);
queuePush(&q, 3);
queuePush(&q, 4);
while (queueEmpty(&q) != 1){
printf("%d ", queueFront(&q));
queuePop(&q);
}
printf("\n");
}
int main(){
test();
system("pause");
return 0;
}
顺序表 链表
栈 队列:元素的操作和访问顺序有一定的规则(所以它们不提供遍历操作,否则和上面两个没啥区别了)
原文地址:https://blog.csdn.net/2401_84919695/article/details/140351112
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!