栈和队列的概念

1.栈的概念

只允许在固定的一端进行插入和删除，进行数据的插入和数据的删除操作的一端数栈顶，另一端称为栈底。 栈中数据元素遵循后进先出LIFO (Last In First Out)

压栈：栈的插入。

出栈：栈的删除。出入数据在栈顶。

 

那么下面我们用什么来实现栈呢？

我们来分析一下

这里我们更推荐数组，对于单链表和双向链表插入数据比较频繁，数组则会开辟成倍的空间，所以说数组比较适合栈

 下面我们就来实现一下栈

栈的初始化

 

 栈的销毁

 栈的入栈

 

  出栈

取栈顶元素

 

 出栈后的数据打印

由此可知 栈里面的数据不能被遍历，也不能被访问。

获取栈中的元素个数

 出栈前和出栈后的对比。

 2队列的概念

只允许在一段插入数据，在另一端删除数据，队列具有先进先出FIFO（fast In fast out）

入队列：进行插入数据的一段是队尾。

出队列：进行删除数据的一段是对头。

        

 队列的初始化

 

 下面表示初始化成功了

 队列的插入/入队列

 

 

出队列

所以就不能这么写

 所以代码是这样写的。

 出栈之前

 

 

 取头尾数据

 

队列有效个数元素

队列的销毁

下面是所有的代码

Queue.c

#define _CRT_SECURE_NO_WARNINGS
#include "Queue.h"
//初始化
void QueueInit(Queue* ps)
{assert(ps);ps->phead = ps->ptail = NULL;ps->size = 0;
}
//入队列
void QueuePush(Queue* ps, QDatatyp x)
{assert(ps);//申请新节点QueueNode* newnode = (QueueNode *)malloc(sizeof(QueueNode));if (newnode == NULL){perror(" malloc fail!");exit(1);}newnode->data = x;newnode->next = NULL;//队列为空if (ps->phead == NULL){ps->phead = ps->ptail = newnode;}else{ps->ptail->next = newnode;ps->ptail = newnode;}ps->size++;
}
//队列为空
bool QueueEmpty(Queue* ps)
{assert(ps);return  ps->phead == NULL && ps->ptail == NULL;
}//出队列，队头
void QueuePop(Queue* ps)
{assert(ps);assert(!QueueEmpty(ps));//删除队头元素//当队列为1的时候if (ps->phead == ps->ptail){free(ps->phead);ps->phead = ps->ptail = NULL;}else{QueueNode* newnode = ps->phead->next;free(ps->phead);ps->phead = newnode;}ps->size--;
}
//去队头数据
QDatatyp QueueFront(Queue* ps)
{assert(ps);assert(!QueueEmpty(ps));return  ps->phead->data;}//取队尾数据QDatatyp QueueBack(Queue* ps)
{assert(ps);assert(!QueueEmpty(ps));return  ps->ptail ->data;}//数据有效的元素个数int QueueSize(Queue* ps){assert(ps);return ps->size;}//销毁队列void QueueDestory(Queue* ps){assert(ps);assert(!QueueEmpty(ps));QueueNode* pcur  = ps->phead;while (pcur){QueueNode * next = pcur->next;free(pcur);pcur = next;}ps->phead = ps->ptail = NULL;ps->size = 0;}

Queue.h

#pragma once
#include <stdio.h>
#include <stdbool.h>
#include <assert.h>
#include <stdlib.h>
//定义队列
typedef int QDatatyp;
typedef struct QueueNode
{QDatatyp data;struct QueueNode* next;}QueueNode;typedef struct Queue
{QueueNode * phead;QueueNode * ptail;int size;
}Queue;
void QueueInit(Queue* ps);//入队列
void QueuePush(Queue* ps, QDatatyp x);
//出队列
void QueuePop(Queue* ps);
//队列为空
bool QueueEmpty(Queue* ps);
//取队头数据
QDatatyp   QueueFront(Queue* ps);
//取队尾数据
QDatatyp  QueueBack(Queue* ps);//有效的数据元素个数
int QueueSize(Queue* ps);
//队列的销毁
void QueueDestory(Queue* ps);

 text.c

#define _CRT_SECURE_NO_WARNINGS
#include "Queue.h"
void Queuetext()
{Queue s;//初始化QueueInit(&s);//入队列QueuePush(&s, 1);QueuePush(&s, 2);QueuePush(&s, 3);QueuePush(&s, 4);//出队列/*QueuePop(&s);QueuePop(&s);QueuePop(&s);QueuePop(&s);*/printf("head:%d\n", QueueFront(&s));printf("ptail:%d\n", QueueBack(&s));QueueDestory(&s);}int main()
{Queuetext();return 0;
}

今天写的有点自闭 ，调整心态慢慢写不急。