链表|数据结构—栈与队列的基本操作（c语言实现） c语言|数据结构

栈与队列

1.思考1
2.栈基本操作的实现
3.测试
4.思考2
5.队列的基本操作实现
6.测试

1.思考1 1.1 为什么栈用数组来模拟比用链表来模拟更优一些？
队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低，时间复杂度为O(n)。
2.栈基本操作的实现 2.1 初始化栈

void StackInit(stack*ps) { assert(ps); ps->_a = (StackDate*)malloc(sizeof(StackDate) * 4); ps->_top = 0; ps->_capacity = 4; }

2.2 入栈

void StackPush(stack*ps, StackDate x) { assert(ps); if (ps->_top == ps->_capacity) { stack*tmp = (StackDate*)realloc(ps, sizeof(StackDate)*(ps->_capacity) * 2); if (NULL == tmp) { printf("realloc failed\n"); exit(-1); } ps = tmp; ps->_capacity *= 2; } ps->_a[ps->_top] = x; ps->_top++; }

2.3 出栈

void StackPop(stack*ps) { assert(ps); assert(!StackIsEmpty(ps)); --ps->_top; }

注意： 出栈并不是真正意义上的删除数据，而是将_top向后挪动了一个位置。
2.4 获取栈顶数据

StackDate StackTop(stack*ps) { assert(ps); assert(!StackIsEmpty(ps)); return ps->_a[ps->_top - 1]; }

2.5 获取栈中有效元素个数

int StackSize(stack*ps) { assert(ps); return ps->_top; }

2.6 判断栈是否为空

bool StackIsEmpty(stack*ps) { assert(ps); return ps->_top == 0; }

2.7 销毁栈

void StackDestory(stack*ps) { assert(ps); free(ps->_a); ps->_a = NULL; ps->_top = ps->_capacity = 0; }

3.测试 3.1测试

void test() { //插入数据 stackst; StackInit(&st); StackPush(&st,1); StackPush(&st,2); StackPush(&st,3); StackPush(&st,4); while (!StackIsEmpty(&st)) { printf("%d ", StackTop(&st)); StackPop(&st); } printf("\n"); //获取栈顶数据 StackPush(&st, 1); StackPush(&st, 2); printf("%d ", StackTop(&st)); printf("\n"); //栈中有效数据个数 printf("%d ", StackSize(&st)); //销毁栈 StackDestory(&st); }

3.2测试结果

文章图片

4.思考2 4.1 为什么队列用链表模拟比数组模拟更加合适？
栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价小。
5.队列的基本操作实现 5.1 初始化队列

void QueueInit(Queue*pq) { assert(pq); pq->_head = pq->_tail = NULL; }

5.2 队尾入队列

void QueuePush(Queue*pq, QueueDate x) { assert(pq); QueueNode*newnode = (QueueNode*)malloc(sizeof(QueueNode)); if (NULL == newnode) { printf("malloc failed\n"); exit(-1); } newnode->next = NULL; newnode->val = x; if (NULL == pq->_tail) { pq->_head = pq->_tail = newnode; } else { pq->_tail->next = newnode; pq->_tail = newnode; } }

5.3 队头出队列

void QueuePop(Queue*pq) { assert(pq); assert(!QueueIsEmpty(pq)); if (NULL == pq->_head->next) { free(pq->_head); pq->_head = pq->_tail = NULL; } else { QueueNode*next = pq->_head->next; free(pq->_head); pq->_head = next; } }

代码分析：

文章图片

5.4 队列中有效元素的个数

int QueueSize(Queue*pq) { assert(pq); int count = 0; QueueNode*cur = pq->_head; while (cur) { ++count; cur = cur->next; } return count; }

5.5 判断队列是否为空

bool QueueIsEmpty(Queue*pq) { assert(pq); return pq->_head == NULL; }

5.6 获取队头数据

QueueDate QueueFront(Queue*pq) { assert(pq); assert(!QueueIsEmpty(pq)); return pq->_head->val; }

5.7 获取队尾的数据

QueueDate QueueBack(Queue*pq) { assert(pq); assert(!QueueIsEmpty(pq)); return pq->_tail->val; }

5.8 销毁队列

void QueueDestory(Queue*pq) { assert(pq); while (pq->_head) { if (pq->_head == pq->_tail) { free(pq->_head); pq->_head = pq->_tail = NULL; } else { QueueNode*next = pq->_head->next; free(pq->_head); pq->_head = next; } } }

注意： 和队头出队列一样分析。
6.测试 6.1测试

void test1() { //插入数据 Queue q; QueueInit(&q); QueuePush(&q, 1); QueuePush(&q, 2); QueuePush(&q, 3); QueuePush(&q, 4); //有效数据的个数 printf("%d ", QueueSize(&q)); printf("\n"); //获取队头数据 printf("%d",QueueFront(&q)); printf("\n"); //获取队尾数据 printf("%d",QueueBack(&q)); printf("\n"); //出队 QueuePop(&q); while (!QueueIsEmpty(&q)) { printf("%d ", QueueFront(&q)); QueuePop(&q); } printf("\n"); //销毁 QueueDestory(&q); printf("\n"); }

【链表|数据结构—栈与队列的基本操作（c语言实现）】6.2 测试结果