栈、队列增删改查
一、栈的增删改查
#define StackSize 100 //栈大小
#define DataType int //栈数据类型
typedef struct Stack{
DataType array[StackSize];
int top;
}Stack;
1、栈初始化
/** @funcation:
* StackInit：栈初始化
* @param：
* none
* @return：
* 返回创建的栈的起始地址
*/
Stack * StackInit(){
Stack * stack = (Stack*)malloc(sizeof(Stack));
if(stack == NULL)
return -1;
stack->top = -1;//初始化栈只需要将size的值设为0就可以了，不用像链表那样麻烦
return stack;
}
2、栈销毁
/** @funcation:
* StackDestroy：栈销毁
* @param：
* stack：需要销毁的栈
* @return：
* none
*/
void StackDestroy(Stack* stack){
stack->top = 0;//销毁栈也同样只需要一步就可以了，将size的值给清零，因为栈使用的是一个静态空间来存储数据，所以没有什么创建内存和释放内存的步骤
}
3、压栈
/** @funcation:
* PushStack：压栈
* @param：
* stack：传入栈指针
* @return：
* 成功返回true，失败返回false
*/
bool PushStack(Stack * stack){
DataType data = 0;
if(stack->top == StackSize-1)
return false;//栈满不能再压栈
scanf("%d",data);
stack->top++;
stack->array[stack->top] = data;
return true;//压栈成功
}
4、弹栈
/** @funcation:
* PopStack：弹栈
* @param：
* stack：传入栈指针
* @return：
* 成功返回true，失败返回false
*/
bool PopStack(Stack * stack，DataType* data){
if(stack->top == -1)
return false;
*data = stack->array[stack->top];
stack->top--;
return true;
}
5、返回栈顶的元素
/** @funcation:
* topStack：读出栈顶的元素
* @param：
* stack：传入栈指针
* data：存储读出的数据
* @return：
* none
*/
bool topStack(Stack * stack，DataType* data){
if(stack->top == -1)
return false;
*data = stack->array[stack->top];
return true;
}
6、返回栈内数据个数
/** @funcation:
* StackNun：返回栈内数据个数
* @param：
* stack：传入栈指针
* @return：
* 返回栈内数据个数
*/
int StackNum(Stack * stack){
int Number = 0;
if(stack->top == -1)
return 0;
Number = stack->top;
return Number;
}
7、判断栈是否为空
/** @funcation:
* StackEmpty：判断栈是否为空
* @param：
* stack：传入栈指针
* @return：
* 栈为空返回true，栈不为空返回false
*/
int StackEmpty(Stack * stack){
if(stack->top == -1)
return true;
return false;
}
二、队列的增删改查
队列是在队尾进行插入，对头进行删除。。
下面都是在以链式队列进行介绍
首先在结构体中定义链式队列的队头和队尾，前提是得先定义一个和链表的节点一样的结构体，包含数据域和指针域。
#define DataType int
typedef struct QNode
{
QElemType Data; //数据域
struct QNode * Next;//指针域
}QNode;
typedef struct LQueue
{
QNode *Front; //队头指针
QNode *Rear; //队尾指针
}LQueue;
1、创建新节点
首先申请一块动态内存，强制转换为QNode类型的结构体指针。然后把传入的数据进行赋值，Next先赋值为NULL。因为每次都是在队尾插入所以队尾后面没有可以指向的元素，就先赋值为NULL。
/** @funcation:
* CreateLQNode：创建一个节点，将节点的地址返回
* @param：
* data：节点的数据域
* @return：
* 返回节点的地址
*/
static QNode *CreateLQNode(DataType data){
QNode *LQNode = (QNode *)malloc(sizeof(QNode));
if(LQNode == NULL){
printf("Create a Node failed\n");
assert(LQNode);
}
LQNode->Data = data;
LQNode->Next = NULL;
return LQNode;
}
2、初始化队列
让队列的队头和队尾指向空。
/** @funcation:
* LQueueInit：队列初始化，将队头队尾节点指向头节点，头节点的数据域不存储数据，指针域指向NULL
* @param：
* Queue：需要初始化的队列指针
* @return：
* none
*/
void LQueueInit(LQueue *Queue){
assert(Queue);
QNode* QHead = CreateLQNode(0); //创建一个头节点
Queue->Front = Queue->Rear = QHead;//队头和队尾指针指向头节点
Queue->Front->Next = NULL;
}
3、判断队列是否为空
int IsEmpty(LQueue *Queue)
{
if(Queue->Front->Next == NULL)
{
return 1;
}
return 0;
}
4、入队列
void EnterLinkQueue(LQueue *Queue,DataType data){
//首先创建一个节点
QNode *Node = CreateLQNode(data); //利用创建新节点的函数返回一个节点的地址
Queue->Rear->Next = Node; //将节点加到队尾的Next后
Queue->Rear = Node; //然后将队尾指向刚刚添加进去的新节点
}
5、出队列
void DeleteLinkQueue(LQueue *Queue,DataType *data){
if(IsEmpty(Queue)){
printf("队列为空\n");
return;
}
QNode*Del_Node = Queue->Front->Next;//让Del_Node指向待删除的节点，应该指向头节点的下一个节点，因为头节点是不存储数据的
*data = Del_Node->Data;//将待删除的节点存储的数据预留下来
Queue->Front->Next = Del_Node->Next;//然后将队头指向的头节点的Next指向待删除节点中的Next位置
//如果待删除的节点是最后剩下的一个节点，那么这个节点的指针域应该存储的是NULL
//所以如果是这种情况，那应该将Rear也改变一下，让Rear队尾也指向剩下的唯一的头节点
if(Queue->Rear == Del_Node)
Queue->Rear = Queue->Front;
free(Del_Node);//释放Del_Node指向的空间
}
6、取队头元素
int GetHead(LQueue *Queue,DataType *data){
if(IsEmpty(Queue)){
printf("队列为空\n");
return;
}
QNode *Node; //临时存储队头节点的地址
Node = Queue->Front->Next; //将队头节点的地址赋给Node
*data = Node->Data; //将当前节点的数据域读取出来
return *data; //返回读取到的数据
}
7、清空队列
void ClearQueue(LQueue *Queue){
LQueue *p,*q;
Queue->Rear = Queue->Front;//队尾指针指向队头指针
p = Queue->Front->Next;
q = p;
while(p != NULL){
free(p); //释放队头指向的空间
p = q->Next;
q = p;
}
}
8、打印队列中的元素
void PrintQueue(LQueue*Queue){
assert(Queue);
QNode * Node = Queue->Front->Next;//存储队头节点指向的头节点的Next位置，因为头节点没有存储数据
while(Node){
printf("%3d",Node->Data);
Node = Node->Next;
}
printf("\n");
}