# 链表实现队列的出队和入队，栈的入栈和出栈

2017-01-13 19:12:54来源:CSDN作者:a1358884804人点击

queue.h

`#ifndef QUEUE_H_#define QUEUE_H_#include<iostream>typedef struct tagstudent{	int data;	struct tagstudent *next;}node;typedef struct tagqueue{	node *first;//队列头指针，指向链表的第一个节点	node *rear;}queue;class Cqueue{public:	Cqueue(){	}	~Cqueue(){	}	queue *push_queue(queue *HQ, int x);	queue *pop_queue(queue *HQ);	int    top_queue(queue *HQ);private:	queue *HQ;};#endif`
queue.cpp

`#include"queue.h"queue * Cqueue:: push_queue(queue *HQ, int x){	node *s;	s = new node;	s->data = x;	s->next = NULL;	if (HQ->rear == NULL)//queue is empty	{		HQ->first = s;		HQ->rear = s;	}	else	{		HQ->rear->next = s;//将尾指针的next指向新增元素s		HQ->rear = s;//将尾指针移动到新入队的元素s	}	return HQ;}queue *Cqueue::pop_queue(queue *HQ)//只能把队列第一个删掉{	node *s; int x;	if (HQ->first == NULL)	{		throw("空队列");	}	else{		s = HQ->first;		x = HQ->first->data;		if (HQ->first == HQ->rear)//队列只有一个节点		{			HQ->first = NULL;			HQ->rear = NULL;		}		else		{			HQ->first = HQ->first->next;			delete s;		}	}	return HQ;}int Cqueue::top_queue(queue *HQ){	if (HQ->first != NULL)	{		return HQ->first->data;	}	else		throw("队列为空");}`

stack.h

`#ifndef STACK_H_#define STACK_H_#include<iostream>typedef struct tagstudent{	int data;	struct tagstudent *next;}node;typedef struct tagstack{	node *stacklow;//栈底指针，指向链表第一个节点	node *stacktop;//栈顶指针}stack;class Cstack{public:	Cstack(){	}	~Cstack(){	}	stack *push(stack *ST, int x);	stack *pop(stack *ST);	int    top(stack *ST);private:	Cstack *ST;};#endif`

stack.cpp

`#include"stack.h"stack *Cstack::push(stack *ST,int x){	node *s;	s = new node;	s->data = x;	if (ST->stacklow == NULL)//空栈	{		ST->stacklow = s;		ST->stacktop = s;	}	else	{		ST->stacktop->next = s;		ST->stacktop = s;	}	return ST;}stack * Cstack::pop(stack *ST){	node *s;	if (ST->stacklow == NULL)	{		throw("空栈");	}	else	{		s = ST->stacklow;		if (ST->stacklow == ST->stacktop)//只有一个节点		{			ST->stacklow = NULL;			ST->stacktop = NULL;		}		else		{			while (s->next != ST->stacktop)			{				s = s->next;			}			ST->stacktop = s;			ST->stacktop->next = NULL;		}		return ST;	}}int Cstack::top(stack *ST){	if (ST->stacklow != NULL)//栈不为空	{		return ST->stacktop->data;	}	else		throw("栈为空");}`

栈后进先出，入栈就是单链表在尾节点插入， 出栈就是删除单链表尾节点，需要从头结点进行遍历，一直找到尾节点的前驱节点为止。