Chapter 4(栈与队列)


1.栈的顺序存储结构
//*********************************stack_array.h************************************
#ifndef STACK_ARRAY_H
#define STACK_ARRAY_H

#define MAXSIZE 1000
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
typedef int datatype;

typedef struct stack_array
{
	datatype data[MAXSIZE];
	size_t top;
}SqStack;


//栈初始化
bool InitStack(SqStack *p);


//入栈
bool push(SqStack *stack,datatype e);


//出栈
bool pop(SqStack *stack,datatype *e);


#endif //STACK_ARRAY_H


//*********************************stack_array.c************************************

#include "stack_array.h"

//栈初始化
bool InitStack(SqStack *p)
{
	if(NULL == p)return false;
	p->top = -1;
	return true;
}

//入栈
bool push(SqStack *stack,datatype e)
{
	if(MAXSIZE-1 == stack->top)return false;//栈满

	++stack->top;//入栈
	stack->data[stack->top] = e;
	
	return true;
}


//出栈
bool pop(SqStack *stack,datatype *e)
{
	if(-1 == stack->top)return false;
	*e = stack->data[stack->top];
	--stack->top;
	return true;
}



//*********************************stack_arrayTest.c************************************

#include "stack_array.h"





int main()

{

	SqStack stack;

	InitStack(&stack);

	for(int i = 1;i <= 10;i++)

	{

		push(&stack,i);

	}

	datatype tmp;

	for(int i =1;i <= 10;i++)

	{

		pop(&stack,&tmp);

		printf("%d 
",tmp);

	}

}


2.两栈共享空间（栈的顺序存储结构）
//*******************************stack_share.h***********************************

#ifndef STACK_SHARE_H
#define STACK_SHARE_H

#define MAXSIZE 1000
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#include <memory.h>
typedef int datatype;

typedef struct stack_share
{
	datatype data[MAXSIZE];
	size_t top1;
	size_t top2;
}SqDoubleStack;


//初始化栈
void InitStack(SqDoubleStack *stack);

//压栈
bool push(SqDoubleStack *stack,datatype e,int num);

//弹栈
bool pop(SqDoubleStack *stack,datatype *e,int num);



#endif //STACK_SHARE_H


//*******************************stack_share.c***********************************

#include "stack_share.h"

//初始化栈
void InitStack(SqDoubleStack *stack)
{
	stack->top1 = -1;
	stack->top2 = MAXSIZE;
}

//压栈
bool push(SqDoubleStack *stack,datatype e,int num)
{
	if(stack->top1+1 == stack->top2)return false;

	if(1 == num)
	{
		stack->data[++stack->top1] = e;
	}
	else if(2 == num)
	{
		stack->data[--stack->top2] = e;
	}
	return true;
}

//弹栈
bool pop(SqDoubleStack *stack,datatype *e,int num)
{
	if(1 == num)
	{
		if(-1 != stack->top1)return false;
		*e = stack->data[stack->top1--];
	}
	else if(2 == num)
	{
		if(MAXSIZE != stack->top2)return false;
		*e = stack->data[stack->top2++];
	}
	return true;
}



//*******************************stack_shareTest.c***********************************

#include "stack_share.h"





int main()

{

	SqDoubleStack stack;

	InitStack(&stack);

	memset(stack.data,0,sizeof(int)*1000);

	for(int i =1;i <= 10;i++)

	{

		push(&stack,i,1);

	}

	for(int i =1;i <= 10;i++)

	{

		push(&stack,i,2);

	}



	for(int i = 0;i < 1000;i++)

	{

		printf("%d ",stack.data[i]);

	}

	return 0;

}

3.*****链栈*****
//****************************stack_link.h************************************
#ifndef STACK_LINK_H

#define STACK_LINK_H



#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
typedef int datatype;


typedef struct StackNode

{

	datatype data;

	struct StackNode *next;

}StackNode;

typedef struct StackLink

{

	StackNode *top;

	size_t count;

}Stack;



//创建链栈
Stack *create();

//压栈

bool push(Stack *stack,datatype e);

//弹栈

bool pop(Stack *stack,datatype *e);


#endif //STACK_LINK_H



//****************************stack_link.c************************************
#include "stack_link.h"


//创建链栈

Stack *create()

{

	Stack *stack = (Stack *)malloc(sizeof(Stack));

	stack->top = NULL;

	stack->count = 0;

	return stack;

}



//压栈

bool push(Stack *stack,datatype e)

{

	if(NULL == stack)return false;



	StackNode *node = (StackNode *)malloc(sizeof(StackNode)); //申请新节点



	node->data = e;//为新节点赋值

	node->next = stack->top;



	stack->top = node;//使top指向新节点

	++stack->count;//count++

	return true;

}





//弹栈

bool pop(Stack *stack,datatype *e)

{

	if(NULL == stack->top)return false;//如果栈空，弹出失败



	StackNode *curr = stack->top;//保存栈顶节点地址

	StackNode *next = curr->next;//保存栈顶下一个节点地址



	*e = curr->data;//保存弹出值

	stack->top = next;//使top指向原栈顶下一个节点

	--stack->count;



	free(curr);

	return true;

}



//****************************stack_linkTest.c************************************
#include "stack_link.h"



int main()

{

	Stack *stack = create();

	for(int i = 1;i <= 10;i++)

	{

		push(stack,i);

	}

	datatype tmp;

	for(int i = 1;i <= 10;i++)

	{

		pop(stack,&tmp);

		printf("%d ",tmp);

	}

	printf("
");

	return 0;

}


4.循环队列（顺序存储结构）
//************************************circular_queue.h****************************************
#ifndef CIRCULAR_LINK_H
#define CIRCULAR_LINK_H

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#define MAXSIZE 1000
typedef int datatype;

typedef struct 
{
	datatype data[MAXSIZE];
	size_t front;
	size_t rear;
}SqQueue;


//初始化队列
void InitQueue(SqQueue *Q);

//求队列长度
size_t length(SqQueue Q);

//入队
bool EnQueue(SqQueue *Q,datatype e);

//出队
bool DeQueue(SqQueue *Q,datatype *e);


#endif //CIRCULAR_LINK_H


//************************************circular_queue.c****************************************
#include "circular_queue.h"


//初始化队列
void InitQueue(SqQueue *Q)
{	
	Q->front = 0;
	Q->rear  = 0;
}

//求队列长度
size_t length(SqQueue Q)
{
	return (Q.rear-Q.front+MAXSIZE)%MAXSIZE;
}

//入队
bool EnQueue(SqQueue *Q,datatype e)
{
	if((Q->rear+1)%MAXSIZE == Q->front)return false;

	Q->data[Q->rear] = e;
	Q->rear = (Q->rear+1)%MAXSIZE;
	return false;
}

//出队
bool DeQueue(SqQueue *Q,datatype *e)
{
	if(Q->front == Q->rear)return false;

	*e = Q->data[Q->front];
	Q->front = (Q->front+1)%MAXSIZE;
	return true;
}



//************************************circular_queueTest.c****************************************
#include "circular_queue.h"


int main()
{
	SqQueue Q;
	InitQueue(&Q);
	
	printf("length:%d 
",length(Q));

	for(size_t i = 1;i <= 1000;i++)
	{
		EnQueue(&Q,i);
	}
	printf("length:%d 
",length(Q));
	size_t temp;

	for(size_t i = 1;i <= 10;i++)
	{
		DeQueue(&Q,&temp);
		printf("%d ",temp);
	}
	printf("
");
	printf("length:%d 
",length(Q));
	for(size_t i = 1;i <= 10;i++)
	{
		EnQueue(&Q,i);
	}

	printf("length:%d 
",length(Q));
	for(size_t i = 1;i <= 1000;i++)
	{
		DeQueue(&Q,&temp);
		printf("%d ",temp);
	}
	printf("length:%d 
",length(Q));
	return 0;
}


5.链队列
//*******************************queue_link.h****************************************
#ifndef QUEUE_LINK_H
#define QUEUE_LINK_H


#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>



typedef int datatype;



typedef struct QNode

{

	datatype data;

	struct QNode *next;

}QNode,*QueuePtr;


typedef struct 

{

	QueuePtr front,rear;

}LinkQueue;

//创建队列

LinkQueue create();

//入队

bool EnQueue(LinkQueue *Q,datatype e);

//出队

bool DeQueue(LinkQueue *Q,datatype *e);


#endif //QUEUE_LINK_H


//*******************************queue_link.c****************************************
#include "queue_link.h"


//创建队列

LinkQueue create()

{

	QueuePtr head = (QueuePtr)malloc(sizeof(QNode));

	head->next = NULL;

	LinkQueue Q;

	Q.front = head;

	Q.rear  = head;

	return Q;

}



//入队

bool EnQueue(LinkQueue *Q,datatype e)

{

	QueuePtr s = (QueuePtr)malloc(sizeof(QNode));//创建新节点

	if(!s)return false;



	s->data = e; //设置新节点数据

	s->next = NULL;



	Q->rear->next = s; //将原来的队尾指向新节点

	Q->rear = s; //队尾指针指向s

	return true;

}



//出队

bool DeQueue(LinkQueue *Q,datatype *e)

{

	if(Q->front == Q->rear)return false;



	QueuePtr node = Q->front->next;//保存要删除节点的地址

	QueuePtr behind = node->next;//保存要删除节点下一个节点的地址



	*e = node->data;//保存数据

	

	Q->front->next = behind;//使front指向下一个节点



	if(Q->rear == node)Q->rear = Q->front;//假如出队前队列只有一个元素，则出队后队列为空，队尾应该指向头节点。

	

	free(node);

	

	return true;

}





//*******************************queue_linkTest.c****************************************
#include "queue_link.h"



int main()

{

	LinkQueue Q = create();



	for(size_t i = 1;i <= 10;i++)

	{

		EnQueue(&Q,i);

	}



	size_t tmp;

	for(size_t i = 1;i <= 10;i++)

	{

		DeQueue(&Q,&tmp);

		printf("%d ",tmp);

	}

	printf("
");

	return 0;

}

附件列表

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/LyndonMario/p/9326340.html