了解并实现栈和队列-----C语言版
目录：
数据结构好难啊，要多学几遍，博客才能下得去笔。加油！
一、栈
栈:一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。
1.1栈的定义
进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO (Last In FirstOut)的原则。
1.2栈的实现
栈一般都是用数组和链表的方法去实现得，用数组去实现栈的方法更优一点，因为数组的尾删尾插更方便一点。
1.2.1 栈的相关接口
1.2.2栈结构的定义声明和栈的初始化
栈结构的声明：
typedef int STDataType;
typedef struct Stack
{
STDataType* a;
int top; // 栈顶
int capacity; // 容量
}Stack;
栈的初始化:
void StackInit(Stack* ps)
{
ps->a = NULL;
ps-> top =0 ; // 栈顶
ps->capacity=0; // 容量
}
1.2.3栈数据的处理
1.入栈
void StackPush(Stack* ps, STDataType data)
{
assert(ps);
if (ps->top == ps->capacity)//相等就扩容
{
Stackcapa(ps);//扩容
}
ps->a[ps->top] = data;//先赋值，在加加
ps->top++;
}
扩容的函数
void Stackcapa(Stack* ps)//扩容
{
int n = ps->capacity == 0 ? 4 : ps->capacity * 2;
STDataType* top = (STDataType*)realloc(ps->a, sizeof(STDataType) * n);
if (top == NULL)//判断是否为空
{
perror("realloc fail");
exit(-1);
}
ps->a = top;
ps->capacity = n;
}
2.出栈
获取栈顶元素
STDataType StackTop(Stack* ps)
{
assert(ps);//判断栈是否为空
assert(!StackEmpty(ps));
return ps->a[ps->top-1];
}
出栈
void StackPop(Stack* ps)
{
assert(ps);//判断栈是否为空
assert(ps->top>0);
--ps->top;//栈减一个就是出栈
}
1.2.4 栈判空和获取栈中元素个数以及栈销毁
1.栈判空
int StackEmpty(Stack* ps)
{
assert(ps);//判断栈是否为空
return ps->top == 0;
}
2.获取栈中元素个数
int StackSize(Stack* ps)
{
assert(ps);//判断栈是否为空
return ps->top;
}
3.栈销毁
void StackDestroy(Stack* ps)
{
assert(ps);//判断栈是否为空
free(ps->a);
ps->a = NULL;
ps->top = ps->capacity = 0;
}
1.2.5 栈的代码实现
用C语言实现一个支持动态增长的栈
.h头文件
#pragma once
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
typedef int STDataType;
typedef struct Stack
{
STDataType* a;
int top; // 栈顶
int capacity; // 容量
}Stack;
// 初始化栈
void StackInit(Stack* ps);
//扩容
void Stackcapa(Stack* ps);
// 入栈
void StackPush(Stack* ps, STDataType data);
// 出栈
void StackPop(Stack* ps);
// 获取栈顶元素
STDataType StackTop(Stack* ps);
// 获取栈中有效元素个数
int StackSize(Stack* ps);
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0
int StackEmpty(Stack* ps);
// 销毁栈
void StackDestroy(Stack* ps);
.c源文件
#pragma once
#include "stack.h"
// 初始化栈
void StackInit(Stack* ps)
{
ps->a = NULL;
ps-> top =0 ; // 栈顶
ps->capacity=0; // 容量
}
void Stackcapa(Stack* ps)//扩容
{
int n = ps->capacity == 0 ? 4 : ps->capacity * 2;
STDataType* top = (STDataType*)realloc(ps->a, sizeof(STDataType) * n);
if (top == NULL)//判断是否为空
{
perror("realloc fail");
exit(-1);
}
ps->a = top;
ps->capacity = n;
}
//入栈
void StackPush(Stack* ps, STDataType data)
{
assert(ps);
if (ps->top == ps->capacity)//相等就扩容
{
Stackcapa(ps);//扩容
}
ps->a[ps->top] = data;//先赋值，在加加
ps->top++;
}
// 出栈
void StackPop(Stack* ps)
{
assert(ps);//判断栈是否为空
assert(ps->top>0);
--ps->top;//栈减一个就是出栈
}
// 获取栈顶元素
STDataType StackTop(Stack* ps)
{
assert(ps);//判断栈是否为空
assert(!StackEmpty(ps));
return ps->a[ps->top-1];
}
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0
int StackEmpty(Stack* ps)
{
assert(ps);//判断栈是否为空
return ps->top == 0;
}
// 获取栈中有效元素个数
int StackSize(Stack* ps)
{
assert(ps);//判断栈是否为空
return ps->top;
}
// 销毁栈
void StackDestroy(Stack* ps)
{
assert(ps);//判断栈是否为空
free(ps->a);
ps->a = NULL;
ps->top = ps->capacity = 0;
}
.c源文件
#pragma once
#include "stack.h"
void test_1()
{
Stack ps;//定义一个栈
// 初始化栈
StackInit( &ps);
// 入栈
StackPush( &ps, 4);
// 入栈
StackPush(&ps, 5);
// 入栈
StackPush(&ps, 6);
printf("栈中有效元素个数：%d\n", StackSize(&ps));
// 获取栈顶元素
while (!StackEmpty(&ps))
{
printf("%d ", StackTop(&ps));
// 出栈
StackPop(&ps);
}
printf("\n");
StackDestroy(&ps);
}
int main()
{
test_1();
return 0;
}
二、队列
队列:只允许在一端进行插入数据操作，另一端进行刪除数据操作的特殊线性表。
2.1队列的定义
进行数据插入操作的一端叫做入队，进行数据删除操作的一端叫做出队，队列中的数据遵循先进先出FIFO（First In First Out）的原则。
2.2队列的实现
队列也可以用数组和链表的结构实现，使用链表的结构实现更优一些， 因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低。
2.2.1 队列的相关接口
2.2.2 队列结构的定义声明和队列初始化
队列结构的声明：
typedef int QDataType;
typedef struct QListNode
{
struct QListNode* next;
QDataType data;//用来存入队的数据
}QNode;
// 队列的结构
typedef struct Queue
{
QNode* front;//队头
QNode* rear;//队尾
QDataType size;//用来记录元素个数
}Queue;
队列初始化：
void QueueInit( Queue* q)
{
assert(q);
q->front = NULL;
q->rear = NULL;
q->size = 0;
}
2.2.3队列数据的处理
1.入队
// 队尾入队列
void QueuePush(Queue* q, QDataType x)
{
assert(q);
QNode* NewNode = (QNode*)malloc(sizeof(QNode));//新建一个节点
if (NewNode == NULL)
{
perror("NewNode");
exit(-1);
}
NewNode->data = x;
NewNode->next = NULL;
if (q->rear == NULL)//如果是空队列
{
q->front = q->rear = NewNode;
}
else//不是空队列
{
q->rear->next = NewNode;//尾插
q->rear = NewNode;
}
q->size++;
}
获取队列尾部元素
QDataType Queueback(Queue* q)
{
//判断为不为NULL
assert(q);
assert(!QueueEmpty(q));
return q->rear->data;
}
2.出队
// 队头出队列
void QueuePop(Queue* q)
{
assert(q);
assert(!QueueEmpty(q));
if(q->front->next==NULL)
{
free(q->front);
q->front = q->rear = NULL;
}
else
{
QNode* pwd = q->front->next;//把头指针指向的位置先存起来
free(q->front);
q->front = pwd;
}
q->size--;
}
获取队列头部元素
QDataType QueueFront(Queue* q)
{
//判断为不为NULL
assert(q);
assert(!QueueEmpty(q));
return q->front->data;
}
2.2.4队列判空和获取队列中元素的个数以及队列的销毁
1.队列判空
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0
bool QueueEmpty(Queue* q)
{
assert(q);
return q->front == NULL;
}
2.获取队列中元素的个数
// 获取队列中有效元素个数
int QueueSize(Queue* q)
{
assert(q);
return q->size;
}
3.队列的销毁
// 销毁队列
void QueueDestroy(Queue* q)
{
assert(q);
QNode* pwd = q->front;//指向头指针
while (pwd)//不是空指针就循环
{
QNode* next = pwd->next;
free(pwd);
pwd = next;
}
q->front = q->rear = NULL;
q->size = 0;
}
2.2.5队列代码的实现。
用c语言实现一个由链表结构实现的队列
.h头文件
#pragma once
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
// 链式结构：表示队列
typedef int QDataType;
typedef struct QListNode
{
struct QListNode* next;
QDataType data;
}QNode;
// 队列的结构
typedef struct Queue
{
QNode* front;
QNode* rear;
QDataType size;
}Queue;
// 初始化队列
void QueueInit(Queue* q);
// 队尾入队列
void QueuePush(Queue* q, QDataType data);
// 队头出队列
void QueuePop(Queue* q);
// 获取队列头部元素
QDataType QueueFront(Queue* q);
// 获取队列队尾元素
QDataType QueueBack(Queue* q);
// 获取队列中有效元素个数
int QueueSize(Queue* q);
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0
bool QueueEmpty(Queue* q);
// 销毁队列
void QueueDestroy(Queue* q);
.c源文件
#include "queue.h"
// 初始化队列
void QueueInit( Queue* q)
{
assert(q);
q->front = NULL;
q->rear = NULL;
q->size = 0;
}
// 队尾入队列
void QueuePush(Queue* q, QDataType x)
{
assert(q);
QNode* NewNode = (QNode*)malloc(sizeof(QNode));//新建一个节点
if (NewNode == NULL)
{
perror("NewNode");
exit(-1);
}
NewNode->data = x;
NewNode->next = NULL;
if (q->rear == NULL)//如果是空队列
{
q->front = q->rear = NewNode;
}
else//不是空队列
{
q->rear->next = NewNode;//尾插
q->rear = NewNode;
}
q->size++;
}
// 队头出队列
void QueuePop(Queue* q)
{
assert(q);
assert(!QueueEmpty(q));
if(q->front->next==NULL)
{
free(q->front);
q->front = q->rear = NULL;
}
else
{
QNode* pwd = q->front->next;//把头指针指向的位置先存起来
free(q->front);
q->front = pwd;
}
q->size--;
}
// 获取队列头部元素
QDataType QueueFront(Queue* q)
{
//判断为不为NULL
assert(q);
assert(!QueueEmpty(q));
return q->front->data;
}
// 获取队列尾部元素
QDataType Queueback(Queue* q)
{
//判断为不为NULL
assert(q);
assert(!QueueEmpty(q));
return q->rear->data;
}
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0
bool QueueEmpty(Queue* q)
{
assert(q);
return q->front == NULL;
}
// 获取队列中有效元素个数
int QueueSize(Queue* q)
{
assert(q);
return q->size;
}
// 销毁队列
void QueueDestroy(Queue* q)
{
assert(q);
QNode* pwd = q->front;//指向头指针
while (pwd)//不是空指针就循环
{
QNode* next = pwd->next;
free(pwd);
pwd = next;
}
q->front = q->rear = NULL;
q->size = 0;
}
.c源文件
#include "queue.h"
void test_1()
{
//定义一个指向队列的指针
Queue q;
// 初始化队列
QueueInit(&q);
// 队尾入队列
QueuePush(&q, 2);
// 队尾入队列
QueuePush(&q, 3);
// 队尾入队列
QueuePush(&q, 4);
// 队尾入队列
QueuePush(&q, 5);
// 队尾入队列
QueuePush(&q, 6);
// 获取队列中有效元素个数
printf("有效元素个数：%d\n", QueueSize(&q)) ;
while (!QueueEmpty(&q))
{
// 获取队列头部元素
printf("%d ", QueueFront(&q));
// 队头出队列
QueuePop(&q);
}
// 销毁队列
QueueDestroy(&q);
}
int main()
{
test_1();
return 0;
}