目录
1.栈底层结构的选择
2.栈的实现
3.栈
3.1入栈
3.2出栈
3.3栈顶删除
4.队列
4.1队列介绍
4.2队列初始化
4.3入队列
4.4队头删除
1.栈底层结构的选择
栈是一种数据结构
具有“后进先出的”的特点
现在面临的两种选择,一种是顺序表,另一种是链表。选择顺序表应该是优于链表的,链表的出栈和入栈时过于复杂,可以选用顺序表,仅需改变数组的下标即可实现。
2.栈的实现
栈首先要有栈顶,容量,和数据。
存入栈的数据只能出栈顶的数据,不能修改栈底的数据以及其他的数据,栈顶我们用top来表示,顺序表是arr,capacity来表示栈的容量大小。
typedef struct Stack
{STDataType*arr;int top;int capacity;
};
这样栈的结构实现好了,接着实现栈的功能。
3.栈
3.1入栈
入栈之前我们要确保栈还有多余的空间可以留给新的数据,所以要对栈进行检查容量大小。
if (ps->top == ps->capacity)
{int tmp = ps->capacity == 0 ? 4 : 2 * ps->capacity;STDataType* p = (STDataType*)realloc(ps->arr, sizeof(STDataType) * tmp);if (p == NULL){perror("realloc Fail");exit(1);}else{ps->arr = p;ps->capacity = tmp;}
}
如果top和capacity相等的话,就要进行扩容。
3.2出栈
STDataType StackTop(ST* ps)
{assert(ps);assert(!StackEmpty(ps));return ps->arr[ps->top - 1];
}
值得注意的是出栈之情要检查是否为空指针,是否为空栈。
3.3栈顶删除
栈顶删除就是将top减一即可,这里不做过多解释。
void STPop(ST* ps)
{assert(!StackEmpty(ps));assert(ps);ps->top--;}
4.队列
4.1队列介绍
队列是使用链表实现的,包含队头队尾,队列节点等。
4.2队列初始化
void QueueInit(Queue* pq)
{pq->phead = pq->ptail = NULL;pq->size = 0;
}
4.3入队列
void QueuePush(Queue* pq, QDataType x)
{QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));if (newnode == NULL){perror("malloc faild");exit(1);}else{newnode->data = x;newnode->next = NULL;}assert(pq);if (pq->phead ==NULL){pq->phead = pq->ptail = newnode;}else{pq->ptail->next = newnode;pq->ptail = newnode;}pq->size++;
}
入队列需要先创建一个队列节点,然后将需要插入的数据x赋给新节点。
值得注意的是要先确定pq和pq是非空的。
4.4队头删除
void QueuePop(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));if (pq->phead == pq->ptail){free(pq->phead);pq->phead = pq->ptail = NULL;}else{QueueNode* tmp = pq->phead->next;free(pq->phead);pq->phead = tmp;}pq->size--;}
如果对头和队尾相等,此时是只有一个节点,直接将头节点释放就行,然后将头尾节点置为空指针。
如果头尾不相等,那先创建一个临时指针保存phead,然后释放头节点,最后将头节点置为tmp即可,最后要将size--,这样一个删除的接口就实现好了。
队列主要的难实现的函数就是这些,其他的简单的这里就不解释了。