栈与队列基本操作

数组下标），栈顶指针存放栈顶元素，初始化时栈顶为-1。下面给出顺序栈的算法。

#include<stdio.h>#include<stdlib.h>#define maxsize 10typedef struct stacknode * stack;typedef int elementype;  //方便一处改，处处改struct stacknode{    elementype *data;    elementype top;};stack Creatstack() //初始化{	stack S=(stack)malloc(sizeof(struct stacknode));	S->data=(elementype*)malloc(maxsize*sizeof(elementype));	S->top=-1;	return S;}int Iffull(stack S){	if(S->top==maxsize-1)		return 1;	else		return 0;}int Ifempty(stack S){	if(S->top==-1)		return 1;	else		return 0;}int Push(stack S,elementype x){	if(Iffull(S))		return 0;	else	{		S->data[++S->top]=x;		return 1;	}}elementype Pop(stack S)  {	if(Ifempty(S))		return 0;	else		return(S->data[S->top--]);}int main(){	int i;	elementype a;	stack S1=Creatstack();	for(i=0;i<maxsize;i++)	{		scanf("%d",&a);	    Push(S1,a);	}	for(i=0;i<maxsize;i++)	  PRintf("%d ",Pop(S1));	printf("/n");    return 0;}这是个简单的入栈和出栈的小算法，上面有些地方用int，有些地方用elementype，在这里是一样的，但是用elementype是为了和结构体里面数组元素保持一致，做到一处改动可以处处改动。
链栈：链栈与顺序栈不同，没有长度限制（除了申请空间失败），又由于入栈和出栈顺序不同，在链表的处理上要做好。栈有一个栈顶指针，在我的程序里栈顶指针不指向数据，下面给出一些基本的算法。
#include<stdio.h>#include<stdlib.h>typedef struct snode * stack;typedef int elementype;struct snode{	elementype data;	stack next;};stack Creatstack(){	stack S;	S=(stack)malloc(sizeof(struct snode));	S->next=NULL;	return S;}int Ifempty(stack S)   //S是栈顶指针{	return S->next==NULL;}int Push(stack S,elementype x){	stack temp;	temp=(stack)malloc(sizeof(struct snode));	if(!temp)		return 0;	else	{	  temp->data=x;      temp->next=S->next;	  S->next=temp;	  return 1;	}}elementype Pop(stack S){	stack T;	elementype m;	T=S->next;	m=T->data;	S->next=T->next;	free(T);	return m;}int main(){	stack S1;	int i,k;	S1=Creatstack();	for(i=0;i<5;i++)	{		scanf("%d",&k);		Push(S1,k);	}	for(i=0;i<5;i++)		printf("%d ",Pop(S1));	printf("/n");	return 0;}
3.队列顺序队列/循环队列：顺序队列与循环队列基本一致，都是利用数组存放数据，但是循环队列在利用空间上要更高效一些。顺序队列用一个向量空间（一般使用一维数组）来存放当前队列中的元素。由于队列的队头和队尾的位置是变化的，设置两个指针front和rear分别指示队头元素和队尾元素在向量空间中的位置，它们的初值在队列初始化时均应置为0。二者判断队空队满条件：顺序队列中q.front = q.rear 表示队空,q.rear = maxsize表示队满.而在循环队列中q.front=q.rear表示队空,而无法用q.rear=maxsize表示队满.（有两种方法，一种是设置标志位，另外一种是放弃一个空间，队尾指针不指向任何元素，用这两种状态把队空队满区分开。第二种较为常用。下面给出循环队列的常见算法及c代码。
#include<stdio.h>#include<stdlib.h>#define maxsize 8 //队列最大容量,但是对于循环队列可以存放的元素个数为maxsize-1个typedef int elementype;typedef struct qnode * Queue;struct qnode{	elementype * data; //存放数据的数组，这里用指针形式，data[maxsize]也可	int front,rear;};Queue Create(){	Queue Q;    Q=(Queue)malloc(sizeof(struct qnode));	Q->data=(elementype *)malloc(maxsize*sizeof(elementype));	Q->front=Q->rear=0;	return Q;}int ifempty(Queue Q){	return Q->front==Q->rear;}int iffull(Queue Q){	return (Q->rear+1)%maxsize==Q->front;}int Insert(Queue Q,elementype x){	if(iffull(Q))	return 0;	else	{     	Q->data[Q->rear]=x;    	Q->rear=(Q->rear+1)%maxsize;    	return 1;	}}elementype Delete(Queue Q){	int m;	if(ifempty(Q))		return 0;	else	{		m=Q->data[Q->front];		Q->front=(Q->front+1)%maxsize;		return m;	}}int length(Queue Q){	return (Q->rear-Q->front+maxsize)%maxsize; //求队列元素个数，也就是长度}int main(){	Queue Q1;	int i,k;	Q1=Create();	for(i=0;i<maxsize-1;i++)	{		scanf("%d",&k);		Insert(Q1,k);	}	printf("%d个元素/n",length(Q1));	for(i=0;i<maxsize-1;i++)		printf("%d ",Delete(Q1));	printf("/n");	return 0;}在这个程序里，先入队，然后出队，int型的函数也可以用bool型，返回true or false，来表明是否入队成功或者是否队空或队满，（不支持bool的可以用define定义）bool型其实就是一种特殊的整型。
链队列：链队列就是用一个线性链表来表示一个队列，队列中每个元素对应链表中一个链
接点，队头指针front指向线性链表的第1个链接点，队尾指针rear指向链表的最后一个链
接点，与顺序存储结构的队列不同的是，队头指针和队尾指针都是指向实际队头元素和队尾元素所在的链接点。测试链接队列为空的条件是front为NULL。在判断队空时1.假设不带头结点，队头队尾指针分别为f和r，则f和r都指向真正的节点，那么f==r表示f和r指向同一个节点，这时，队列中只有一个节点，只有f==r==null时表示队列为空。2. 假设队列有头节点，所以f不可能为null（若f==null，则这个队列在内存中丢失），f始终指向头结点，因此当r也指向头结点时表示队列为空。在我的代码中取无头节点的情况。
#include<stdio.h>
#include<stdlib.h>#define maxsize 6 //自己定义，也可不定义typedef struct queue * Queue;typedef struct queuenode * Ptrtnode;typedef int elementype;struct queue{	elementype data;	Queue next;};struct queuenode{	Queue front;	Queue rear;};void Create(Ptrtnode Q)  //初始化链队列{	Q->front=Q->rear=NULL;}int Insert(Ptrtnode Q,elementype x)  {	Queue temp=(Queue)malloc(sizeof(struct queue));	if(temp==NULL)  //申请空间失败	 return 0;	if(Q->rear==NULL)  //如果队列为空		Q->front=Q->rear=temp;	else	{	   temp->data=x;	   Q->rear->next=temp;	   Q->rear=temp;	}  return 1;}elementype Delete(Ptrtnode Q){	int m;	Queue p;	if(Q->front==NULL)		return 0;	else	{		m=Q->front->data;		p=Q->front; 		Q->front=p->next;		if(Q->front==NULL)		{			Q->rear=NULL;		}		free(p);		return m;	}}int main(){	int i,k;	Queue Q1;	Ptrtnode S;	S=(Ptrtnode)malloc(sizeof(struct queuenode));	Create(S);	Q1=(Queue)malloc(sizeof(struct queue));	scanf("%d",&k);	Q1->data=k;	Q1->next=NULL;	S->front=Q1;	S->rear=Q1;	for(i=1;i<maxsize;i++)	{		scanf("%d",&k);		Insert(S,k);	}	for(i=0;i<maxsize;i++)		printf("%d ",Delete(S));	printf("/n");	return 0;}