- 栈
- 栈的概念和结构
- 栈的实现
- 栈的结构声明
- 栈的初始化
- 栈的销毁
- 栈的插入元素(入栈)
- 栈的删除元素(出栈)
- 获取栈顶元素
- 判断栈为空
- 获取栈中元素的数量
- 队列
- 队列的概念和结构
- 队列的实现
- 队列的结构声明
- 队列的初始化
- 队列的销毁
- 队列的插入元素(入队)
- 队列的删除元素(出队)
- 获取队头元素
- 获取队尾元素
- 判断队列为空
- 获取队列中元素的数量
栈:只允许在固定的一端进行插入和删除元素的操作。进行数据的插入和删除的一端称为栈顶,另一端称为栈底。栈中的数据元素遵循LIFO(Last in First out)原则。
入栈:栈的插入操作叫做进栈/压栈/入栈。
出栈:栈的删除操作叫做出栈。
栈的实现栈的思想及其结构就像上图所描述的一样,能够实现以上操作就叫做栈,方法有挺多,但是一般使用数组或者链表实现,而其中数组又是最常见的,因为相比链表,数组在尾插和尾删上更有优势。
顺序表就是用数组实现的,所以这里用数组实现的栈与顺序表有很多的相似之处。
栈的结构声明typedef int StackDateType; typedef struct Stack { StackDateType* array; int top; int capacity; }Stack;
top下标始终为栈顶元素的下一个,同时top又代表了栈中元素的数量;
capacity是栈的总容量,当top与capacity相等时,需要扩容。
栈的初始化void StackInit(Stack* p){ assert(p); p->array = NULL; p->top = p->capacity = 0; }
栈的初始化给空间也可以,不给空间也可以(在插入元素的时候给空间)。
栈的销毁void StackDestroy(Stack* p){ assert(p); free(p->array); p->array = NULL; p->top = p->capacity = 0; }栈的插入元素(入栈)
void StackPush(Stack* p, StackDateType data){ assert(p); //扩容 if(p->top == p->capacity){ //当初次使用栈,栈为空时,先给栈4个元素的大小,以后每次扩容时,增为二倍 int NewCapacity = p->capacity == 0 ? 4 : p->capacity * 2; StackDateType* NewArray = (StackDateType*)realloc(p->array, sizeof(StackDateType) * NewCapacity); if(NewArray == NULL){ perror("realloc fail"); exit(-1); } p->array = NewArray; p->capacity = NewCapacity; } //将元素插入到栈中,并且top自增 p->array[p->top++] = data; }栈的删除元素(出栈)
void StackPop(Stack* p){ assert(p); //断言一下栈为空时,无法出栈 assert(!StackEmpty(p)); //由于栈是由数组实现的,而访问数组用的是下标,所以数组尾删时,只需要将下标自减一下就ok p->top--; }获取栈顶元素
StackDateType StackTop(Stack* p){ assert(p); //断言一下栈为空时,无法获取栈顶元素 assert(!StackEmpty(p)); //由于top是栈顶元素的下一个元素的下标,所以获取栈顶元素时,需要top - 1 return p->array[p->top - 1]; }判断栈为空
int StackEmpty(Stack* p){ assert(p); //top代表栈中元素的数量,所以当top为0时,栈为空 return p->top == 0; }获取栈中元素的数量
int StackSize(Stack* p){ assert(p); //top代表栈中元素的数量 return p->top; }队列 队列的概念和结构
队列:只允许在一端进行插入元素的操作,在另一段进行删除元素的操作,进行数据的插入的一端称为队尾,进行数据的删除的一端称为队头。队列中的数据元素遵循FIFO(First in First out)原则。
入队:插入元素称为入队。
出队:删除元素称为出队。
队列的实现队列由于具有先入先出的特性,所以需要进行尾插和头删,而头删则是链表比较擅长的,所以使用链表实现队列是最常见的。
队列的结构声明typedef int QueueDateType; typedef struct QueueNode{ struct QueueNode* next; QueueDateType val; }QueueNode; typedef struct Queue{ QueueNode* front;//指向链表的头 QueueNode* back;//指向链表的尾 int size;//代表链表的结点数量 }Queue;
这里是两个结构体,第一个用来形成链表,第二个用来控制链表。
队列的初始化void QueueInit(Queue* p){ assert(p); p->front = p->back = NULL; p->size = 0; }队列的销毁
void QueueDestroy(Queue* p){ assert(p); //销毁链表的经典操作 QueueNode* curr = p->front; while(curr){ QueueNode* next = curr->next; free(curr); curr = next; } p->front = p->back = NULL; p->size = 0; }队列的插入元素(入队)
void QueuePush(Queue* p, QueueDateType val){ assert(p); //创建结点 QueueNode* node = (QueueNode*)malloc(sizeof(QueueNode)); if(node == NULL){ perror("malloc fail"); exit(-1); } node->next = NULL; node->val = val; //将结点与头尾两个指针建立联系 //若back为空,则队列此时无结点,为空,所以将front和back都指向该结点 if(p->back == NULL){ p->front = p->back = node; } //此时,队列不为空,front会一直指向第一个结点,而back则需要链接新结点,并且更新back的指向 else{ p->back->next = node;//链接新结点 p->back = node;//更新back的指向 } p->size++;//队列元素数量加1 }队列的删除元素(出队)
void QueuePop(Queue* p){ assert(p); //断言一下,当队列为空时,无法出队 assert(!QueueEmpty(p)); //当队列只有一个元素时 if(p->front->next == NULL){ free(p->front); p->front = p->back = NULL; } //当队列有多个元素时,头删 else{ QueueNode* next = p->front->next; free(p->front); p->front = next; } p->size--;//队列元素数量减1 }获取队头元素
QueueDateType QueueFront(Queue* p){ assert(p); assert(!QueueEmpty(p)); return p->front->val; }获取队尾元素
QueueDateType QueueBack(Queue* p){ assert(p); assert(!QueueEmpty(p)); return p->back->val; }判断队列为空
int QueueEmpty(Queue* p){ assert(p); return p->size == 0; }获取队列中元素的数量
int QueueSize(Queue* p){ assert(p); return p->size; }