网站开发学校 优帮云,高明网站建设报价,健身房网站建设案例,做网站难本篇博客将介绍栈和队列的定义以及实现。
1.栈的定义 栈是一种特殊的线性表#xff0c;只允许在固定的一端进行插入和删除数据#xff0c;插入数据的一端叫做栈顶#xff0c;另一端叫做栈底。栈中的数据遵守后进先出的原则 LIFO (Last In First Out)。 插入数据的操作称为压…本篇博客将介绍栈和队列的定义以及实现。
1.栈的定义 栈是一种特殊的线性表只允许在固定的一端进行插入和删除数据插入数据的一端叫做栈顶另一端叫做栈底。栈中的数据遵守后进先出的原则 LIFO (Last In First Out)。 插入数据的操作称为压栈/进栈/入栈。 删除数据的操作称为出栈。 压栈和出栈的操作都在栈顶。 2. 栈的实现
栈的实现可以利用数组或者链表在此处由于数组在尾部插入和删除数据较为简单因此我们利用数组实现栈的相关操作。数组的结构如下 因此我们需要实现以下功能
typedef int STDataType;
typedef struct Stack
{STDataType* a;int top; //栈顶int capaicty;
}ST;void STInit(ST* pst); //初始化
void STDestroy(ST* pst);//内存释放
void STPush(ST* pst, STDataType x);//压栈
void STPop(ST* pst);//出栈
STDataType STTop(ST* pst);//返回栈顶数据
bool STEmpty(ST* pst);//判断栈是否为空
int STSize(ST* pst);//返回栈中数据个数 接下来我们可以初始定义一个结构体: ST st; 具体函数代码如下
void STInit(ST* pst)
{assert(pst);pst-a NULL;//pst-top -1; //top指向栈顶数据pst-top 0; //top指向栈顶数据的下一个pst-capaicty 0;
}void STDestroy(ST* pst)
{assert(pst);free(pst-a);pst-a NULL;pst-top 0;pst-capaicty 0;
}void STPush(ST* pst, STDataType x)
{if (pst-top pst-capaicty){ int newCapacity pst-capaicty 0 ? 4 : pst-capaicty * 2;STDataType* tmp (STDataType*)realloc(pst-a, newCapacity * sizeof(STDataType));if (tmp NULL){perror(realloc fail);return;}pst-a tmp;pst-capaicty newCapacity;}pst-a[pst-top] x;pst-top;
}void STPop(ST* pst)
{assert(pst);assert(!STEmpty(pst));pst-top--;
}STDataType STTop(ST* pst)
{ assert(pst);assert(!STEmpty(pst));return pst-a[pst-top - 1];
}bool STEmpty(ST* pst)
{assert(pst);return pst-top 0;//等于0为真
}int STSize(ST* pst)
{assert(pst);return pst-top;
}
需要注意的是当打印栈时则是通过 STDataType STTop(ST* pst); 返回栈顶数据打印然后栈顶数据出栈再打印新的栈顶。直到栈为空代码如下
while (!STEmpty(st))
{printf(%d , STTop(st));STPop(st);
}
3. 队列的定义 队列只允许一端进行插入数据的操作二在另一端删除数据的一种特殊线性表队列数据按照先进先出入队列 FIFO (First in FIrst Out)。 队尾插入数据对头删除数据。 4. 队列的实现
同样的队列的实现也可以利用数组和链表实现在此处使用单链表较为简单因为入队相当于单链表的尾插出队相当于单链表的头删。 因此我们需要实现以下功能
typedef int QueueDataType;typedef struct QueueNode //定义每个结点的结构
{struct QueueNode* next;QueueDataType data;
}QNode;typedef struct Queue //标识整个队列
{QNode* phead;QNode* ptail;int size;
}Queue;void QueueInit(Queue* pq);//队列初始化
void QueueDestory(Queue* pq);//内存释放
void QueuePush(Queue* pq, QueueDataType x);//入队
void QueuePop(Queue* pq);//出队
QueueDataType QueueFront(Queue* pq);//队头数据
QueueDataType QueueBack(Queue* pq);//队尾数据
int QueueSize(Queue* pq);//队列节点个数
bool QueueEmpty(Queue* pq);//判断空队列
接下来我们定义初始结构体
Queue q; 具体实现代码如下
void QueueInit(Queue* pq)
{assert(pq);pq-phead NULL;pq-ptail NULL;pq-size 0;
}
void QueueDestory(Queue* pq)
{assert(pq);QNode* cur pq-phead;while (cur){QNode* next cur-next;free(cur);cur next;}pq-phead pq-ptail NULL;pq-size 0;
}
void QueuePush(Queue* pq, QueueDataType x)
{assert(pq);QNode* newnode (QNode*)malloc(sizeof(QNode));if (newnode NULL){perror(malloc fail\n);return;}newnode-data x;newnode-next NULL;if (pq-ptail NULL){assert(pq-phead NULL);pq-phead pq-ptail newnode;}else {pq-ptail-next newnode;pq-ptail newnode;}pq-size;
}void QueuePop(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));//1. 一个节点//2. 多个节点if (pq-phead-next NULL){free(pq-phead);pq-phead pq-ptail NULL;}else{QNode* next pq-phead-next;free(pq-phead);pq-phead next;}pq-size--;
}
QueueDataType QueueFront(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq-phead-data;
}
QueueDataType QueueBack(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq-ptail-data;
}
int QueueSize(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq-size;
}
bool QueueEmpty(Queue* pq)
{assert(pq);return pq-phead NULL pq-ptail NULL;//空 turn//return pq-size;
}
同样的返回对头数据打印然后对头数据出队再打印新的对头。直到队列为空代码如下
while (!QueueEmpty(q))
{printf(%d , QueueFront(q));QueuePop(q);
}
