数据结构：栈和队列基本算法合集_世界观焦点
顺序栈的基本运算
（1）初始化栈InitStack(&s)
(资料图)
建立一个新的空栈s，实际上是将栈顶指针指向-1即可。
void InitStack(SqStack *&s)
{ s=(SqStack *)malloc(sizeof(SqStack));
s->top=-1;
}
（2）销毁栈DestroyStack(&s)
释放栈s占用的存储空间。
void DestroyStack(SqStack *&s)
{
free(s);
}
（3）判断栈是否为空StackEmpty(s)
栈S为空的条件是s->top==-1。
bool StackEmpty(SqStack *s)
{
return(s->top==-1);
}
（4）进栈Push(&s，e)
在栈不满的条件下，先将栈指针增1，然后在该位置上插入元素e。
bool Push(SqStack *&s，ElemType e)
{ if (s->top==MaxSize-1) //栈满的情况，即栈上溢出
return false;
s->top++; //栈顶指针增1
s->data[s->top]=e; //元素e放在栈顶指针处
return true;
}
（5）出栈Pop(&s，&e)
在栈不为空的条件下，先将栈顶元素赋给e，然后将栈指针减1。
bool Pop(SqStack *&s，ElemType &e)
{ if (s->top==-1) //栈为空的情况，即栈下溢出
return false;
e=s->data[s->top]; //取栈顶指针元素的元素
s->top--; //栈顶指针减1
return true;
}
（6）取栈顶元素GetTop(s，&e)
在栈不为空的条件下，将栈顶元素赋给e。
bool GetTop(SqStack *s，ElemType &e)
{
if (s->top==-1) //栈为空的情况，即栈下溢出
return false;
e=s->data[s->top]; //取栈顶指针元素的元素
return true;
}
链栈的基本运算
（1）初始化栈initStack(&s)
建立一个空栈s。实际上是创建链栈的头结点，并将其next域置为NULL。
void InitStack(LinkStNode *&s)
{ s=(LinkStNode *)malloc(sizeof(LinkStNode));
s->next=NULL;
}
（2）销毁栈DestroyStack(&s)
释放栈s占用的全部存储空间。
void DestroyStack(LinkStNode *&s)
{ LinkStNode *p=s，*q=s->next;
while (q!=NULL)
{ free(p);
p=q;
q=p->next;
}
free(p); //此时p指向尾结点，释放其空间
}
（3）判断栈是否为空StackEmpty(s)
栈S为空的条件是s->next==NULL，即单链表中没有数据结点。
bool StackEmpty(LinkStNode *s)
{
return(s->next==NULL);
}
（4）进栈Push(&s，e)
将新数据结点插入到头结点之后。
void Push(LinkStNode *&s，ElemType e)
{ LinkStNode *p;
p=(LinkStNode *)malloc(sizeof(LinkStNode));
p->data=e; //新建元素e对应的结点p
p->next=s->next; //插入p结点作为开始结点
s->next=p;
}
（5）出栈Pop(&s，&e)
在栈不空的条件下，将头结点的后继结点的数据域赋给e，然后将其删除。
bool Pop(LinkStNode *&s，ElemType &e)
{ LinkStNode *p;
if (s->next==NULL) //栈空的情况
return false;
p=s->next; //p指向开始结点
e=p->data;
s->next=p->next; //删除p结点
free(p); //释放p结点
return true;
}
（6）取栈顶元素GetTop(s，e)
在栈不为空的条件下，将头结点后继数据结点的数据域赋给e。
bool GetTop(LinkStNode *s，ElemType &e)
{ if (s->next==NULL) //栈空的情况
return false;
e=s->next->data;
return true;
}
顺序队列的基本运算
（1）初始化队列InitQueue(&q)
构造一个空队列q。将front和rear指针均设置成-1。
void InitQueue(SqQueue *&q)
{ q=(SqQueue *)malloc (sizeof(SqQueue));
q->front=q->rear=-1;
}
（2）销毁队列DestroyQueue(&q)
释放队列q占用的存储空间。
void DestroyQueue(SqQueue *&q)
{
free(q);
}
（3）判断队列是否为空QueueEmpty(q)
若队列q满足q->front==q->rear条件，则返回true；否则返回false。
bool QueueEmpty(SqQueue *q)
{
return(q->front==q->rear);
}
（4）进队列enQueue(&q，e)
在队列不满的条件下，先将队尾指针rear循环增1，然后将元素添加到该位置。
bool enQueue(SqQueue *&q，ElemType e)
{ if (q->rear==MaxSize-1) //队满上溢出
return false;
q->rear++;
q->data[q->rear]=e;
return true;
}
（5）出队列deQueue(&q，&e)
在队列q不为空的条件下，将队首指针front循环增1，并将该位置的元素值赋给e。
bool deQueue(SqQueue *&q，ElemType &e)
{ if (q->front==q->rear) //队空下溢出
return false;
q->front++;
e=q->data[q->front];
return true;
}
链队的基本运算
（1）初始化队列InitQueue(&q)
构造一个空队列，即只创建一个链队头结点，其front和rear域均置为NULL，不创建数据元素结点。
void InitQueue(LinkQuNode *&q)
{ q=(LinkQuNode *)malloc(sizeof(LinkQuNode));
q->front=q->rear=NULL;
}
（2）销毁队列DestroyQueue(&q)
释放队列占用的存储空间，包括链队头结点和所有数据结点的存储空间。
void DestroyQueue(LinkQuNode *&q)
{ DataNode *p=q->front，*r; //p指向队头数据结点
if (p!=NULL) //释放数据结点占用空间
{ r=p->next;
while (r!=NULL)
{ free(p);
p=r;r=p->next;
}
}
free(p); free(q); //释放链队结点占用空间
}
（3）判断队列是否为空QueueEmpty(q)
若链队结点的rear域值为NULL，表示队列为空，返回true；否则返回false。
bool QueueEmpty(LinkQuNode *q)
{
return(q->rear==NULL);
}
（4）进队enQueue(&q，e)
void enQueue(LinkQuNode *&q，ElemType e)
{ DataNode *p;
p=(DataNode *)malloc(sizeof(DataNode));
p->data=e;
p->next=NULL;
if (q->rear==NULL) //若链队为空，新结点既是队首结点又是队尾结点
q->front=q->rear=p;
else
{ q->rear->next=p; //将p结点链到队尾，并将rear指向它
q->rear=p;
}
}
（5）出队deQueue(&q，&e)
bool deQueue(LinkQuNode *&q，ElemType &e)
{ DataNode *t;
if (q->rear==NULL) return false; //队列为空
t=q->front; //t指向第一个数据结点
if (q->front==q->rear) //队列中只有一个结点时
q->front=q->rear=NULL;
else //队列中有多个结点时
q->front=q->front->next;
e=t->data;
free(t);
return true;
}
标签： REAR NULL PUSH DATA NEXT FREE RETURN TRUE WHILE FALSE 只有一个
X 关闭
X 关闭
