个人主页：深情秋刀鱼@-CSDN博客

数据结构专栏：数据结构与算法

源码获取：数据结构: 上传我写的关于数据结构的代码 (gitee.com)

目录

一、栈

1.栈的定义

 2.栈的实现

 a.栈结构的定义

b.初始化

c.扩容

d.入栈

e.出栈

f.打印

g.取栈顶元素

 h.判空

i.获取栈中的元素个数

j.销毁

二、队列 

1.队列的定义

2.队列的实现

a.队列结构的定义

b.初始化

c.创建节点

d.入队

e.出队

f.队中的元素个数

g.队列判空

h.队列打印

i.取队头元素

 j.取队尾元素

 k.销毁

---

一、栈

1.栈的定义

        栈是一种特殊的线性表，其只允许在固定的一段进行插入和删除元素的操作。进行数据的插入和删除元素的操作的一端被称为栈顶，另一端被称为栈底。栈中的数据元素遵循后进先出LIFO（Last in First out）的原则。

 2.栈的实现

        栈的实现一般可以用数组和链表实现，一般情况下用数组实现更为合适，因为在数组尾部进行插入和删除操作的代价较小。

 a.栈结构的定义

typedef int STDataType;//定义栈结构（数组）
typedef struct Stack
{STDataType* a;  //数组栈int top;		//栈顶int capacity;   //容量
}Stack;

b.初始化

void STInit(Stack* pst)
{assert(pst);pst->a = NULL;pst->capacity = 0;pst->top = -1;
}

c.扩容

void STExpan(Stack* pst)
{if (pst->top + 1 == pst->capacity){int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;STDataType* tmp = (STDataType*)realloc(pst->a, newcapacity * sizeof(STDataType));if (tmp == NULL){perror("realloc fail!");return;}pst->a = tmp;pst->capacity = newcapacity;}
}

        在对栈中的数组进行扩容时，需要注意其他参数如容量（capacity）的变化，在一开始我们将capacity初始化为0，所以在这里要对capacity进行判空。

d.入栈

void STPush(Stack* pst, STDataType x)
{assert(pst);STExpan(pst);pst->top++;pst->a[pst->top] = x;
}

e.出栈

void STPop(Stack* pst)
{assert(pst && pst->top > -1);pst->top--;
}

f.打印

void STPrint(Stack* pst)
{while (!STEmpty(pst)){printf("%d ", STTop(pst));STPop(pst);}
}

g.取栈顶元素

STDataType STTop(Stack* pst)
{assert(pst && pst->top > -1);return pst->a[pst->top];
}

 h.判空

bool STEmpty(Stack* pst)
{assert(pst);return pst->top == -1;
}

i.获取栈中的元素个数

int STSize(Stack* pst)
{assert(pst);return pst->top + 1;
}

j.销毁

void STDestroy(Stack* pst)
{assert(pst);free(pst->a);pst->a = NULL;pst->capacity = 0;pst->top = 0;
}

---

二、队列 

1.队列的定义

        队列是只允许在一端进行插入，另一端进行删除数据操作的线性表。队列中的数据元素遵循先进先出FIFO（First in First out）的原则。进行插入操作的一端称为队尾，进行删除操作的一端成为队头。

2.队列的实现

         队列可以用数组和链表实现，使用链表的结构更优，因为如果使用数组，在执行出队列的操作时效率会比较低。

a.队列结构的定义

typedef int QDataType;//定义队列节点
typedef struct QueueNode
{struct QueueNode* next;		//后继指针QDataType val;			//数值
}QNode;//队列指针
typedef struct Queue
{QNode* head;			//队头指针QNode* tail;			//队尾指针int size;				//队列中的元素
}Queue;

        为了简化实现函数时参数的传递，我们额外定义一个包含一个头节点和尾节点的结构体，其中头节点和尾节点应分别指向一个链表的头和尾。

b.初始化

void QueueInit(Queue* pq)
{assert(pq);pq->head = NULL;pq->tail = NULL;pq->size = 0;
}

c.创建节点

QNode* QueueBuyNode(QDataType x)
{QNode* newNode = (QNode*)malloc(sizeof(QNode));if (newNode == NULL){perror("malloc fail!");exit(1);}newNode->next = NULL;newNode->val = x;return newNode;
}

d.入队

void QueuePush(Queue* pq, QDataType x)
{assert(pq);QNode* node = QueueBuyNode(x);if (pq->head == NULL)	// 判空{pq->head = pq->tail = node;pq->size++;}else{pq->tail->next = node;pq->tail = pq->tail->next;pq->size++;}
}

e.出队

void QueuePop(Queue* pq)
{assert(pq && pq->head);QNode* phead = pq->head;pq->head = pq->head->next;free(phead);phead = NULL;if (pq->head == NULL)				 //队列为空	pq->tail = NULL;pq->size--;
}

f.队中的元素个数

int QueueSize(Queue* pq)
{assert(pq);return pq->size;
}

g.队列判空

bool QueueEmpty(Queue* pq)
{assert(pq);return pq->size == 0;
}

h.队列打印

void QueuePrint(Queue* pq)
{assert(pq);if (pq->size == NULL){printf("NULL\n");return;}QNode* pcur = pq->head;while (pcur){printf("%d ", pcur->val);pcur = pcur->next;}printf("\n");
}

i.取队头元素

QDataType QueueFront(Queue* pq)
{assert(pq && pq->head);return pq->head->val;
}

 j.取队尾元素

QDataType QueueBack(Queue* pq)
{assert(pq && pq->tail);return pq->tail->val;
}

 k.销毁

void QueueDestroy(Queue* pq)
{assert(pq);QNode* pcur = pq->head;while (pcur){QNode* pnext = pcur->next;free(pcur);pcur = pcur->next;}pq->head = pq->tail = NULL;pq->size = 0;
}