本节继续数据结构的学习,看一看栈和队列的概念。
栈是一种特殊的线性表,只允许在一端进行插入和删除元素的操作。 栈顶:数据插入和删除操作的一端。 栈底 :和栈顶相对的一端。 栈中的元素遵守后进先出
Last In First Out
的规则。 压栈/进栈/入栈:在栈顶的插入操作。 出栈/弹栈:在栈顶的删除操作。
注意:
数据结构中的栈与内存中的栈
(由操作系统使用)
是两个不同的概念,二者相同的是遵守相同的数据插入与数据删除规则:后进先出Last In First Out
。
数据结构的栈就像按顺序放入箱子中的书本,先放进去的书被压在了底下;从箱子中拿书。先拿到的是最上面的后放进去的书,先放进去的书反而是最后拿到。
栈的结构只需要遵守先入后出的规则即可。栈顶与栈底的位置是相对的。 栈的实现既可以使用顺序表,也可以使用链表。 顺序表实现栈相比链表更有优势,顺序表实现方式更多,当然链表也可以实现栈。
顺序表实现栈,需要特别注意一下栈顶下标所在初始的位置,初始位置不同,出栈同一个元素操作也有差别。 栈顶下标初始为-1
栈顶下标初始为0
条件编译指令:
#ifndef __STACK__H__
#define __STACK__H__
//...
#endif
#pragma once
#include <stdio.h>
#include <assert.h>
#include <stdbool.h>
#include <stdlib.h>
对于顺序表,尾删、尾插操作效率很高。如果把顺序表起始出(0下标处)作为栈底,那么顺序表的尾插,尾删操作就对应于栈的入栈和出栈操作。
typedef int STDataType;
typedef struct Stack {
STDataType* data;
int top;
int capacity;
}ST;
栈中栈底一定在0下标处,只需要标记栈顶位置;对于动态顺序表,还需要一个通用数据类型的指针
STDataType*
用于开辟储存数据的空间,变量capacity
记录顺序表的容量。
函数接受外部栈的地址,产生其副本
pst
,因为并不需要改变外部栈本身,改变的是栈内部的成员。 由于定义的栈是一个结构体,所以栈的地址一定存在,所以需要对传入的栈的地址进行暴力断言判断是否为NULL
。初始化成员指针
pst->data
指向NULL
,栈顶下标和容量都为0
。
//初始化
void StackInit(ST* pst) {
assert(pst);
pst->data = NULL;
pst->top = pst->capacity = 0;
}
//入栈
void StackPush(ST* pst, STDataType val) {
assert(pst);
//扩容
if (pst->top == pst->capacity) {
int newCapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;
STDataType* tmp = (STDataType*)realloc(pst->data, sizeof(STDataType) * newCapacity);
if (!tmp) {
perror("StackPush");
}
pst->data = tmp;
pst->capacity = newCapacity;
}
pst->data[pst->top] = val;
++pst->top;
}
元素入栈之前,需要先判断栈的容量是否足够,如果不够就扩容。 我们初始化栈顶下标
pst->top
为0,注意数据在入栈时先放入pst->top
处,然后pst->top
加1。
//出栈
void StackPop(ST* pst) {
assert(pst);
assert(!StackEmpty(pst));
--pst->top;
}
出栈操作之前,需要先检查栈是否为空,这里用了暴力检查
assert()
;如果栈为空就不能继续删除数据。
//取出栈顶元素
STDataType StackTop(ST* pst) {
assert(pst);
return pst->data[pst->top -1];
}
注意栈的栈顶
pst->top
初始化是0
还是-1
:pst->top
初始化是0
,取出的是pst->top-1
位置的元素;pst->top
初始化是-1
,取出的是pst->top
位置的元素。
//判断栈是否是空
bool StackEmpty(ST* pst) {
assert(pst);
return pst->top == 0;
}
注意栈的栈顶
pst->top
初始化是0
还是-1
:pst->top
初始化是0
,那么pst->top
等于0栈就是空;pst->top
初始化是-1
,那么pst->top
等与-1就是空。
//返回栈的大小
int StackSize(ST* pst) {
assert(pst);
return pst->top;
}
注意栈的栈顶
pst->top
初始化是0
还是-1
:pst->top
初始化是0
,那么pst->top
的值就是栈元素的个数,也就是栈的大小;pst->top
初始化是-1
,那么pst->top + 1
的值才是栈元素的个数,也就是栈的大小。
//销毁栈
void StackDestroy(ST* pst) {
assert(pst);
free(pst->data);
pst->top = pst->capacity = 0;
}
手动释放栈内部指针成员
pst->data
动态申请的空间。
分文件实现 头文件
Stack.h
#pragma once
#include <stdio.h>
#include <assert.h>
#include <stdbool.h>
#include <stdlib.h>
typedef int STDataType;
typedef struct Stack {
STDataType* data;
int top;
int capacity;
}ST;
//初始化
void StackInit(ST* pst);
//销毁栈
void StackDestroy(ST* pst);
//入栈
void StackPush(ST* pst, STDataType val);
//出栈
void StackPop(ST* pst);
//取出栈顶元素
STDataType StackTop(ST* pst);
//判断栈是否是空
bool StackEmpty(ST* pst);
//返回栈的大小
int StackSize(ST* pst);
源文件
Stack.c
//初始化
void StackInit(ST* pst) {
assert(pst);
pst->data = NULL;
pst->top = pst->capacity = 0;
}
//销毁栈
void StackDestroy(ST* pst) {
assert(pst);
free(pst->data);
pst->top = pst->capacity = 0;
}
//入栈
void StackPush(ST* pst, STDataType val) {
assert(pst);
//扩容
if (pst->top == pst->capacity) {
int newCapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;
STDataType* tmp = (STDataType*)realloc(pst->data, sizeof(STDataType) * newCapacity);
if (!tmp) {
perror("StackPush");
}
pst->data = tmp;
pst->capacity = newCapacity;
}
pst->data[pst->top] = val;
++pst->top;
}
//出栈
void StackPop(ST* pst) {
assert(pst);
assert(!StackEmpty(pst));
--pst->top;
}
//取出栈顶元素
STDataType StackTop(ST* pst) {
assert(pst);
return pst->data[pst->top -1];
}
//判断栈是否是空
bool StackEmpty(ST* pst) {
assert(pst);
return pst->top == 0;
}
//返回栈的大小
int StackSize(ST* pst) {
assert(pst);
return pst->top;
}
队列是只允许在一端进行插入数据的操作,在另一端进行删除数据的操作的线性表。 队列遵守先进先出
First In First Out
的规则。 队头:进行删除操作的一端。 队尾:进行插入操作的一端。 入队列:在队尾的插入数据的操作。 出队列:在对头的删除数据的操作。
队列就像是穿过隧道的火车,火车从一端的隧道口驶入,一般只能从另一端的隧道口驶出,火车头先于火车尾从另一端隧道出来。 也像是去银行办理业务时拿到的叫号单,先去银行的人叫号单上的数字靠前,后去银行的人的叫号单上的数字靠后;也就是先去的先办理业务先离开,后去的后办理业务后离开。
一端放入数据,一端拿出数据。 就像单向通行。
队列只需要遵守先入先出
First In First Out
的规则即可,具体的实现方式也不做限制。 不过相比顺序表,链表更加适合队列的实现:链表的头删操作契合队列的出队列操作,链表的尾插操作契合入队列操作。队列中有两个节点指针,一个指向队头。一个指向队尾。
条件编译指令:
#ifndef __STACK__H__
#define __STACK__H__
//...
#endif
#pragma once
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>
先封装节点结构体类型,并对结构体类型
struct QueueNode
进行类型重命名为QNode
,便于书写。
//封装为节点
typedef int QDataType;
typedef struct QueueNode {
QDataType val;
struct QueueNode* next;
}QNode;
在封装队列类型,包含指向队列的两个节点指针,一个指针
head
指向队头,一个指针tail
指向队尾。 把新封装的队列类型重命名为Queue
,便于书写。
//封装节点指针为
typedef struct Queue {
QNode* head;
QNode* tail;
int size;
}Queue;
//初始化
void QueueInit(Queue* pq) {
assert(pq);
pq->head = pq->tail = NULL;
pq->size = 0;
}
我们需要修改队列(结构体),所以需要传入队列的地址。 开始时队列为空,队头指针
pq->head
和队尾指针pq->tail
都指向NULL
; 队列的整型变量pq->size
初始化为0。
//入队列
void QueuePush(Queue* pq, QDataType val) {
assert(pq);
//申请新节点,申请失败就退出程序
QNode* newnode = (QNode*)malloc(sizeof(QNode));
if (!newnode) {
perror("QueuePush");
exit(-1);
}
newnode->val = val;
newnode->next = NULL;
//链表尾插分为两种情况:
//1.队头指针为空
if (pq->head == NULL) {
pq->head = pq->tail = newnode;
}
//2.队头指针不为空
else {
//先链接前后节点,在更新尾节点
pq->tail->next = newnode;
pq->tail = newnode;
}
++pq->size;
}
入队列,就是链表尾插数据。 先动态申请新节点,如果申请空间失败就退出程序; 在尾插单链表,分两种情况:
pq->size
加1
;
//出队列
void QueuePop(Queue* pq) {
assert(pq);
assert(!QueueEmpty(pq));
//删除最后一个节点时,需要防止tail野指针
if (pq->head == pq->tail) {
free(pq->head);
pq->head = pq->tail = NULL;
}
else {
//删除不是最后一个节点
QNode* del = pq->head;
pq->head = pq->head->next;
free(del);
del = NULL;
}
--pq->size;
}
出队列,就是头删数据。 在删除节点之前,需要先判断队列
assert()
是否为空,如果队列为空就报错。 删除节点时有两种情况:
del
记录队头节点的地址,然后更新队头指针pq->head
,再手动释放指针del
指向的空间,最后pq->size
减1。pq->tail
仍指向最后节点位置,pq->tail
就是一个空指针,所以这种情况需要单独处理,把尾节点pq->tail
也置NULL
。//取队头数据
QDataType QueueHead(Queue* pq) {
assert(pq);
return pq->head->val;
}
//取队尾数据
QDataType QueueTail(Queue* pq) {
assert(pq);
return pq->tail->val;
}
//判断队列是否为空
bool QueueEmpty(Queue* pq) {
assert(pq);
return pq->head == NULL && pq->tail == NULL;
}
两个队列内部指针都为空说明队列为空。
//计算队列长度
int QueueSize(Queue* pq) {
assert(pq);
//遍历法,效率较低
/*int n = 0;
QNode* cur = pq->head;
while (cur) {
++n;
cur = cur->next;
}
return n;*/
/*直接在队列结构体里定义一个size,每次入队列或出队列同时改变size,
使用时直接从结构体内返回即可*/
return pq->size;
}
两种方法:
pq->size
,每次入队列或出队列同时改变pq->size
,
使用时直接从队列返回即可。
//销毁队列
void QueueDestroy(Queue* pq) {
assert(pq);
QNode* cur = pq->head;
while (cur) {
QNode* del = cur;
cur = cur->next;
free(del);
}
/*while (cur) {
QNode* later = cur->next;
free(cur);
cur = later;
}*/
}
在程序结束前我们需要销毁队列,防止内存泄漏的现象发生。 对于链表实现的队列而言,只需要借助局部节点指针变量
cur
记录队列头pq->head
,然后依次遍历链表的每一个节点,先借助临时节点指针变量del
保存当前节点的地址,在更新cur
指向下一个节点,然后释放free()
指针del
指向节点的空间,直到cur
为NULL
停止。
分文件实现 头文件
Queue.h
#pragma once
//封装为节点
typedef int QDataType;
typedef struct QueueNode {
QDataType val;
struct QueueNode* next;
}QNode;
//封装节点指针为队列类型
typedef struct Queue {
QNode* head;
QNode* tail;
int size;
}Queue;
//初始化
void QueueInit(Queue* pq);
//销毁队列
void QueueDestroy(Queue* pq);
//入队列
void QueuePush(Queue* pq, QDataType val);
//出队列
void QueuePop(Queue* pq);
//取队头数据
QDataType QueueHead(Queue* pq);
//取队尾数据
QDataType QueueTail(Queue* pq);
//判断队列是否为空
bool QueueEmpty(Queue* pq);
//计算队列长度
int QueueSize(Queue* pq);
源文件
Queue.c
#include "Queue.h"
//初始化
void QueueInit(Queue* pq) {
assert(pq);
pq->head = pq->tail = NULL;
pq->size = 0;
}
//销毁队列
void QueueDestroy(Queue* pq) {
assert(pq);
QNode* cur = pq->head;
while (cur) {
QNode* del = cur;
cur = cur->next;
free(del);
}
/*while (cur) {
QNode* later = cur->next;
free(cur);
cur = later;
}*/
}
//入队列
void QueuePush(Queue* pq, QDataType val) {
assert(pq);
//申请新节点,申请失败就退出程序
QNode* newnode = (QNode*)malloc(sizeof(QNode));
if (!newnode) {
perror("QueuePush");
exit(-1);
}
newnode->val = val;
newnode->next = NULL;
//链表尾插分为两种情况:
//1.队头指针为空
if (pq->head == NULL) {
pq->head = pq->tail = newnode;
}
//2.队头指针不为空
else {
//先链接前后节点,在更新尾节点
pq->tail->next = newnode;
pq->tail = newnode;
}
++pq->size;
}
//出队列
void QueuePop(Queue* pq) {
assert(pq);
assert(!QueueEmpty(pq));
//防止tail野指针
if (pq->head == pq->tail) {
free(pq->head);
pq->head = pq->tail = NULL;
}
else {
QNode* del = pq->head;
pq->head = pq->head->next;
free(del);
del = NULL;
}
--pq->size;
}
//取队头数据
QDataType QueueHead(Queue* pq) {
assert(pq);
return pq->head->val;
}
//取队尾数据
QDataType QueueTail(Queue* pq) {
assert(pq);
return pq->tail->val;
}
//判断队列是否为空
bool QueueEmpty(Queue* pq) {
assert(pq);
return pq->head == NULL && pq->tail == NULL;
}
//计算队列长度
int QueueSize(Queue* pq) {
assert(pq);
//遍历法,效率较低
/*int n = 0;
QNode* cur = pq->head;
while (cur) {
++n;
cur = cur->next;
}
return n;*/
/*直接在队列结构体里定义一个size,每次入队列或出队列同时改变size,
使用时直接从结构体内返回即可*/
return pq->size;
}
栈和队列有着许多的应用场景,它们在其中扮演了重要的作用,我们今天只是了解了它们的基本结构,并没有实际应用场景给我们练习,需要注意区分栈与队列性质的相反关系。
栈和队列的概念与实现到这里就结束了,感谢看到这里的你!!!