【数据结构】栈和队列(vs)
前言:
栈和队列是两种重要的线性结构。本章讨论栈和队列的定义、表示方法。这里栈和队列分别用数组实现和链表实现(这里所说是实现的底层逻辑分别是数组结构和链表结构)
一、栈
1.1概念与结构
栈是一种特殊的线性表,只允许在固定的一端进行插入和删除操作,进行数据插入和删除的一端称为栈顶和栈底。(可得出,栈是先进后出LIFO)
压栈:栈的插入操作,入数据在栈顶
出栈:栈的删除操作,出数据也在栈顶
1.2用数组的结构实现栈(vs):
头文件:stack.h
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>typedef int STDatatype;
typedef struct Stack
{STDatatype* arr;int top;//元素个数int capacity;
}ST;//初始化
void STInit(ST* ps);
//销毁
void STDestroy(ST* ps);//判空
bool STEmpty(ST*ps);//入栈&出栈
void STPush(ST* ps, STDatatype x);
void STpop(ST* ps);//取栈顶元素
STDatatype StackTop(ST* ps);//获取栈中有效元素个数
int STSize(ST* ps);
实现栈的基本功能:初始化栈、入栈和出栈、获取栈的元素、销毁栈等:
- 初始化:创建一个空栈,设置栈顶指针为初始化状态。
void STInit(ST* ps)
{assert(ps);ps-> arr = NULL;ps->top = ps->capacity = 0;
}
- 栈的销毁:将栈顶指针恢复到初始状态,释放栈中所有元素占用的空间。
void STDestroy(ST* ps)
{assert(ps);if (ps->arr){free(ps->arr);}ps->arr = NULL;ps->top = ps->capacity = 0;
}
- 入栈和出栈:
void STPush(ST* ps, STDatatype x)
{assert(ps);//看空间是否足够,不够就申请if (ps->capacity == ps->top){int newCapacity = ps->capacity = 0 ? 4 : 2 * ps->capacity;STDatatype* tmp = (STDatatype*)realloc(ps->arr, sizeof(STDatatype) * newCapacity);if (tmp == NULL){perror("reallloc fail!");exit(1);}ps->arr = tmp;ps->capacity = newCapacity;}ps->arr[ps->top++] = x;}
//这里是判空操作
bool STEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}void STPop(ST* ps)
{assert(ps);assert(!STEmpty(ps));--ps->top;
}
- 获取栈顶的元素:可在不删除栈顶元素的情况下,返回栈顶元素的值。获取元素个数,直接取ps->top。
//获取栈顶元素
STDatatype StackTop(ST* ps)
{assert(ps);assert(!STEmpty(ps));return ps->arr[ps->top - 1];
}
//获取元素个数
int STSize(ST* ps)
{assert(ps);assert(!STEmpty(ps));return ps->top;
}
二、队列
2.1概念与结构
概念:只允许在一端进行插入数据操作,在另一端进行删除操作的特殊线性表,具有先进先出特点。
入队列:进行插入操作的一端称为队尾。
出队列:进行删除操作的一端称为队头。
队列的底层结构
2.2用链表结构实现队列(vs):
头文件:Queue.h
//定义队列节点的结构.
typedef int QDataType;
typedef struct QueueNode
{QDataType data;struct QueueNode* next;
}QueueNode;typedef struct Queue
{struct QueueNode* phead;struct QueueNode* ptail;int size;//保存队列有效数据个数..
}Queue;//初始化.
void QueueInit(Queue* pq);//入队列,从队尾
void QueuePush(Queue* pq, QDataType x);//队列判空.
bool QueueEmpty(Queue* pq);//出队列,从队头
void QueuePop(Queue* pq);//取对头数据
QDataType QueueFront(Queue* pq);
//取队尾数据
QDataType QueueBack(Queue* pq);//队列有效元素个数
int QueueSize(Queue* pq);//销毁队列
void QueueDestroy(Queue* pq);
实现队列的基本操作:初始化、出入队列操作、获取队列的长度、销毁队列。
- 初始化队列,创建一个空的队列、设置队头指针和队尾指针为初始状态。
//初始化.
void QueueInit(Queue* pq)
{assert(pq);pq->phead = pq->ptail = NULL;pq->size = 0;
}
- 入队列:将元素插到队尾,若队列为空,则将插入的数据作为初始的队头队尾指针元素,若不为空,则将队尾指针更新指向新插入的元素。
//入队列,队尾.
void QueuePush(Queue* pq, QDataType x)
{assert(pq);//申请一个新节点QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));if (newnode == NULL){perror("malloc fail!");exit(1);}newnode->data = x;newnode->next = NULL;if (pq->phead == NULL){pq->phead = pq->ptail = newnode;}else{pq->ptail->next = newnode;pq->ptail = pq->ptail->next;}pq->size++;
}
- 出队列:首先先判空,若队列为空,无法进行出队操作,通常会返回一个特定的错误值或进行错误处理;若队列中只有一个元素,删除该元素后,队头指针和队尾指针都恢复到初始状态;若有多个元素,删除队头元素后,队头指针指向下一个指针。
bool QueueEmpty(Queue* pq)
{assert(pq);return pq->phead == NULL && pq->ptail == NULL;
}//出队列,队头
void QueuePop(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));if (pq->phead == pq->ptail){free(pq->phead);pq->phead = pq->ptail = NULL;}else{QueueNode* next = pq->phead->next;free(pq->phead);pq->phead = next;}--pq->size;
}
- 取队头队尾数据:首先判空,若队列为空,则不再执行下面的代码。
//取队头数据
QDataType QueueFront(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->phead->data;
}//取队尾元素
QDataType QUeueBack(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->ptail->data;
}
- 获取队列有效元素个数:这里用的是链表结构实现队列,所以直接取元素个数就可以了。
//队列有效元素个数
int QueueSize(Queue* pq)
{assert(pq);return pq->size;
}
- 销毁队列:将队头队尾指针恢复到初始状态,释放队列中所有元素占用的内存。
//销毁队列
void QueueDestroy(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));QueueNode* pcur = pq->phead;while (pcur){QueueNode* next = pcur->next;free(pcur);pcur = next;}pq->phead = pq->ptail = NULL;pq->size = 0;
}