栈和队列

什么是栈，栈有什么特性？用C语言实现一个动态栈栈和程序运行时的栈区有什么区别？为什么将递归程序转化成循环时需要用到栈？什么是队列，队列有什么特性？栈和队列有什么区别？用C语言实现一个队列 什么是栈，栈有什么特性？

栈：一种特殊的线性表，只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO(Last In First Out)的原则。 压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。 出栈：栈的删除操作叫做出栈。出操作也在栈顶。 栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一点。因为数组在尾上插入数据的代价比较小。

用C语言实现一个动态栈

Stack.h

#include<stdio.h> #include<assert.h> #include<malloc.h> typedef int SDataType; typedef struct Stack { SDataType* _array; int _size; int _capacity; }Stack; void StackInit(Stack* ps); void StackPush(Stack* ps, SDataType data); void StackPop(Stack* ps); SDataType StackTop(Stack* ps); int StackSize(Stack* ps); int StackEmpty(Stack* ps); void StackDestroy(Stack* ps);

Stack.c

#define _CRT_SECURE_NO_WARNINGS 1 #include"Stack.h" void CheckCapacity(Stack* ps) { assert(ps); int NewCapacity = ps->_capacity * 2; if (ps->_size == ps->_capacity) { //开辟新空间 SDataType* ptmp = (SDataType*)malloc(sizeof(SDataType)* NewCapacity); if (NULL == ptmp) { assert(0); return; } //拷贝元素到新开辟数组空间 for (int i = 0; i < ps->_size; ++i) ptmp[i] = ps->_array[i]; //释放旧数组 free(ps->_array); ps->_array = ptmp;又得把ptmp（新数组）放进栈 ps->_capacity = NewCapacity;//size不用管 } } void StackInit(Stack* ps) { assert(ps); ps->_array = (SDataType*)malloc(sizeof(SDataType)* 10);//注意左值是要初始化的栈中的数组 初始化也要开辟新空间，开始给定一个最初开辟空间的大小capacity的值 if (NULL == ps->_array) { assert(0); return; } ps->_capacity = 10; ps->_size = 0; } void StackPush(Stack* ps, SDataType data) { assert(ps); //忽略之处 CheckCapacity(ps);//插入新元素必须判断原来空间是否够用 ps->_array[ps->_size] = data; ps->_size++; } void StackPop(Stack* ps) { assert(ps); //if (NULL == ps->_array)//还是那句话，（尾）删除就需要先判空 if(0 == ps->_size) //这两个一样吗？？？ 不一样，size = 0；说明数组空间开辟成功，只是里面无元素 //而 NULL == ps->_array 则是数组未开辟成功空间，在初始化时即中止 return; ps->_size--;//怎么有点儿奇怪？也不用释放？只需要size--就ok？是的 } SDataType StackTop(Stack* ps)//栈顶top 其实就是size（size是有效元素个数）只不过在栈的数组中下标是size-1 { assert(ps); return ps->_array[ps->_size - 1]; } int StackSize(Stack* ps) { assert(ps); return ps->_size; } int StackEmpty(Stack* ps) { assert(ps); return 0 == ps->_size;//空栈是capacity还是size？ } void StackDestroy(Stack* ps) { assert(ps); if (NULL == ps->_array)//重要理解 { return; } free(ps->_array); ps->_capacity = 0;//capacity都为0了还需要size为0？ ps->_size = 0;//这里两个都需要处理（销毁的时候，capacity = 0；size = 0（容易忘，注意）） } void TestStack() { Stack s; StackInit(&s); StackPush(&s, 1); StackPush(&s, 2); StackPush(&s, 3); printf("size = %d\n", StackSize(&s)); printf("top = %d\n", StackTop(&s)); StackPush(&s, 4); StackPush(&s, 5); printf("size = %d\n", StackSize(&s)); printf("top = %d\n", StackTop(&s)); StackPop(&s); StackPop(&s); printf("size = %d\n", StackSize(&s)); printf("top = %d\n", StackTop(&s)); StackDestroy(&s); } int main() { TestStack(); return 0; } 栈和程序运行时的栈区有什么区别？

栈区：是一块内存空间，由操作系统自动分配释放 ，存放函数的参数值，局部变量的值等 栈：具有后进先出的数据结构

为什么将递归程序转化成循环时需要用到栈？

在实现函数调用的时候，系统底层就是用栈来保存函数运行现场的；具体来说，每次调用函数时，会把当前函数的局部变量和返回地址都压栈保存起来，当函数调用结束返回的时候，再把局部变量从栈里弹出来。 而递归的核心就是重复的函数调用。因此如果要变成非递归，就可能需要自己实现栈数据结构用来保存一些状态变量；这其实就是在模拟函数调用。

什么是队列，队列有什么特性？栈和队列有什么区别？

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾 出队列：进行删除操作的一端称为对头 队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低。 栈与队列的相同点： 1.都是线性结构。 2.插入操作都是限定在表尾进行。 3.都可以通过顺序结构和链式结构实现。、 4.插入与删除的时间复杂度都是O（1），在空间复杂度上两者也一样。 5.多链栈和多链队列的管理模式可以相同。 栈与队列的不同点： 1.删除数据元素的位置不同，栈的删除操作在表尾进行，队列的删除操作在表头进行。 2.应用场景不同；常见栈的应用场景包括括号问题的求解，表达式的转换和求值，函数调用和递归实现，深度优先搜索遍历等；常见的队列的应用场景包括计算机系统中各种资源的管理，消息缓冲器的管理和广度优先搜索遍历等。 3.顺序栈能够实现多栈空间共享，而顺序队列不能。

用C语言实现一个队列 Queue.h #include<stdio.h> #include<assert.h> #include<malloc.h> #include<stdlib.h> typedef int QDataType; typedef struct QNode { QDataType _data; struct QNode* _pNext; }QNode,*pQNode; typedef struct Queue { pQNode _front; pQNode _back; }Queue; void QueueInit(Queue* q); void QueuePush(Queue* q, QDataType data); void QueuePop(Queue* q); QDataType QueueFront(Queue* q); QDataType QueueBack(Queue* q); int QueueSize(Queue* q); int QueueEmpty(Queue* q); void QueueDestroy(Queue* q); //void TestQueue();

Queue.c

#define _CRT_SECURE_NO_WARNINGS 1 #include"Queue.h" pQNode BuyNewNode(QDataType data)//注意参数和队列无关，别再传错了,还有QDataType data的QDataType别再忘记了 { pQNode pNewNode = (pQNode)malloc(sizeof(QNode)); if (NULL == pNewNode) { assert(0); return NULL; } pNewNode->_data = data; pNewNode->_pNext = NULL;//不管data? 不行，在哪里？ return pNewNode; } void QueueInit(Queue* q) { assert(q);//对比栈（顺序表），这里初始化不需要开辟新空间（给第一个节点） q->_front = q->_back = NULL;//不管data，在这里，初始化不需要管data } void QueuePush(Queue* q, QDataType data) { assert(q); pQNode pNewNode = BuyNewNode(data); if (NULL == q->_front)//插入需要判空,用头和尾随便一个判断？是的，但最后用头 { q->_front = q->_back = pNewNode;//因为为空，所以不需要pNext } q->_back->_pNext = pNewNode;//连接 q->_back = pNewNode;//队列尾往后走一个（也可以理解为标记） } void QueuePop(Queue* q)//插入：两种情况（1.判空 2.普通） //删除：三种情况（1.判空 2.判断是都只有一个节点 3.普通） { //assert(q); pQNode pDelNode = NULL;//用来标记头节点 if (NULL == q->_front) { return; } //pDelNode = q->_front; //标记头节点（老师是在这里标记的） //if (NULL == pDelNode->_pNext)//判断是否只有一个节点（老师） if (q->_front == q->_back)//判断是否只有一个节点（我） { q->_front = q->_back = NULL;//是不是这样？是的 free(q->_front);//这个在前面？必须在后面（理解），提前释放指针会丢失 /只要删除就需要free //free(pDelNode); } else { pDelNode = q->_front; //标记头节点 q->_front = q->_front->_pNext; free(pDelNode);//注意一下 //pDelNode = NULL;//不需要 } } QDataType QueueFront(Queue* q) { assert(q); return q->_front->_data; } QDataType QueueBack(Queue* q) { assert(q); return q->_back->_data; } int QueueSize(Queue* q) { int count = 0; pQNode pCur = NULL; pCur = q->_front; while (pCur) { ++count; pCur = pCur->_pNext; } return count; } int QueueEmpty(Queue* q) { assert(q); return NULL == q->_front;//判空就是判断是否是初始化状态 } void QueueDestroy(Queue* q)//需不需要判空 { assert(q); pQNode pCur = NULL; pCur = q->_front; if (NULL == q->_front) return; if (q->_front == q->_back) q->_front = q->_back = NULL; while (pCur) { q->_front = q->_front->_pNext; free(pCur); pCur = q->_front; } //循环结束还有一步（让队列尾back指向空），别再忘记了 q->_front = q->_back = NULL;//（对比单链表无这一步？！）多余吗？ //不多余，这一步目的在于让 q->_back = NULL; //队列和单链表区别在于 队列还有个队尾指针，千万别忘记处理 } void TestQueue() { Queue q; QueueInit(&q); QueuePush(&q, 1); QueuePush(&q, 2); QueuePush(&q, 3); QueuePush(&q, 4); printf("front = %d\n", QueueFront(&q)); printf("back = %d\n", QueueBack(&q)); printf("size = %d\n", QueueSize(&q)); QueuePop(&q); printf("front = %d\n", QueueFront(&q)); printf("back = %d\n", QueueBack(&q)); printf("size = %d\n", QueueSize(&q)); QueuePop(&q); QueuePop(&q); printf("front = %d\n", QueueFront(&q)); printf("back = %d\n", QueueBack(&q)); printf("size = %d\n", QueueSize(&q)); QueuePop(&q); printf("size = %d\n", QueueSize(&q)); QueueDestroy(&q); } int main() { TestQueue(); system("pause"); return 0; }