您的位置: 首页  >  IT文章  >  数据结构学习笔记(9.栈跟队列的特殊实现)

数据结构学习笔记(9.栈跟队列的特殊实现)

分类: IT文章 • 2023-11-08 14:58:59
数据结构学习笔记(9.栈和队列的特殊实现)

本节知识点：

1.使用两个链式栈实现链式队列：

数据结构学习笔记(9.栈跟队列的特殊实现)
数据结构学习笔记(9.栈跟队列的特殊实现)
代码如下：
LinkQueue.c文件：
/***************************************************************************************
文件名：LinkQueue.c
头文件：LinkQueue.h 
时间： 2013/04/02
作者： Hao
功能:  利用两个链式栈 实现的链式队列 
****************************************************************************************/
#include <stdio.h> 
#include <malloc.h>
#include "LinkStack.h"
#include "LinkQueue.h" 

typedef struct _tag_link_queue //队列的结构 
{
	LinkStack* instack;
	LinkStack* outstack;
}link_queue;

/*******************************************************************************************************
函数名： Creat_LinkQueueHead
函数功能：创建一个队列头  在队列头中定义两个指针指向 两个栈  
参数： void
返回值：ret 成功返回队列头  失败返回NULL 
*******************************************************************************************************/
LinkQueue* Creat_LinkQueueHead()
{
	link_queue* ret = (link_queue*)malloc(sizeof(link_queue));
	if(NULL != ret)
	{
		ret->instack = Creat_LinkStack();
		ret->outstack = Creat_LinkStack();
		if((NULL == ret->instack) || (NULL == ret->outstack))
		{
			free(ret);
			ret = NULL;
		}
	} 
	return ret;
} 

/*******************************************************************************************************
函数名： Destroy_LinkQueue
函数功能：销毁这个队列 释放队列中的所有元素 释放两个栈头 一个队列头  
参数： LinkQueue* queue 队列头 
返回值：void 
*******************************************************************************************************/
void Destroy_LinkQueue(LinkQueue* queue)
{
	if(NULL != queue)
	{
		link_queue* temp = (link_queue*)queue;
		Destroy_LinkStack(temp->instack);
		Destroy_LinkStack(temp->outstack);
		free(queue);
	}
} 

/*******************************************************************************************************
函数名： Get_Length
函数功能：获得队列中元素个数 
参数： LinkQueue* queue 队列头 
返回值：ret 成功返回元素个数  失败返回0 
*******************************************************************************************************/
int Get_Queue_Length(LinkQueue* queue)
{
	int ret = 0;
	if(NULL != queue)
	{
		link_queue* temp = (link_queue*)queue;
		ret = Get_LinkStack_Length(temp->instack) + Get_LinkStack_Length(temp->outstack);
	}
	return ret;
}

/*******************************************************************************************************
函数名： Clean_LinkQueue
函数功能：清空队列 
参数： LinkQueue* queue 队列头 
返回值：ret 成功返回1  失败返回0 
*******************************************************************************************************/
int Clean_LinkQueue(LinkQueue* queue)
{
	int ret = 0;
	if(NULL != queue)
	{
		ret = 1;
		link_queue* temp = (link_queue*)queue;
		Clean_LinkStack(temp->instack);
		Clean_LinkStack(temp->outstack);
	} 
	return 0;
}

/*******************************************************************************************************
函数名： LinkQueue_Push
函数功能：入队列操作 
参数： LinkQueue* queue 队列头   void* data 要入队的数据 
返回值：ret 成功返回1  失败返回0 
*******************************************************************************************************/
int LinkQueue_Push(LinkQueue* queue, void* data)
{
	int ret = 0;
	if((NULL != queue) && (NULL != data))
	{
		ret = 1;
		link_queue* temp = (link_queue*)queue;
		/*入队列操作 就把数据压入instack栈中*/
		LinkStack_Push(temp->instack, data);
	}
	return ret;
} 

/*******************************************************************************************************
函数名： LinkQueue_Pop
函数功能：出队列操作 
参数： LinkQueue* queue 队列头    
返回值：ret 成功返回队头数据  失败返回NULL 
*******************************************************************************************************/
void* LinkQueue_Pop(LinkQueue* queue)
{
	void* ret = NULL;
	if(NULL != queue)
	{
		link_queue* temp = (link_queue*)queue;
		/*先判断outstack栈是否为空  为空就把instack全部倒入outstack中  再弹出outstack中数据*/
		/*不为空就直接从outstack中  弹出数据*/
		if(0 == Get_LinkStack_Length(temp->outstack))
		{
			/*把instack全部倒入outstack中去*/ 
			while(Get_LinkStack_Length(temp->instack) > 0)
			{
				LinkStack_Push(temp->outstack, LinkStack_Pop(temp->instack));
			}
		} 

		/*弹出outstack中的栈顶数据*/ 
		ret =  LinkStack_Pop(temp->outstack);	
	} 
	return ret; 
}

/*******************************************************************************************************
函数名： LinkQueue_Top
函数功能：获得队头数据 
参数： LinkQueue* queue 队列头    
返回值：ret 成功返回队头数据  失败返回NULL 
*******************************************************************************************************/
void* LinkQueue_Top(LinkQueue* queue)
{
	void* ret = NULL;
	if(NULL != queue)
	{
		link_queue* temp = (link_queue*)queue;
		/*先判断outstack栈是否为空  为空就把instack全部倒入outstack中  再弹出outstack中数据*/
		/*不为空就直接从outstack中  弹出数据*/
		if(0 == Get_LinkStack_Length(temp->outstack))
		{
			/*把instack全部倒入outstack中去*/ 
			while(Get_LinkStack_Length(temp->instack) > 0)
			{
				LinkStack_Push(temp->outstack, LinkStack_Pop(temp->instack));
			}
		} 
	
		/*弹出outstack中的栈顶数据*/ 
		ret = Get_LinkStack_Top(temp->outstack);		
	} 
	return ret; 
}

LinkQueue.h 文件：
#ifndef __LinkQueue_H__
#define __LinkQueue_H__

typedef void LinkQueue;  //这个是为了 封装方便 

LinkQueue* Creat_LinkQueueHead(void);

void Destroy_LinkQueue(LinkQueue* queue);

int Get_Queue_Length(LinkQueue* queue);

int Clean_LinkQueue(LinkQueue* queue);

int LinkQueue_Push(LinkQueue* queue, void* data);

void* LinkQueue_Pop(LinkQueue* queue);

void* LinkQueue_Top(LinkQueue* queue); 
 
#endif

main.c文件：
#include <stdio.h>
#include "LinkQueue.h"

int main()
{
	LinkQueue* queue = Creat_LinkQueueHead();
    int a[10] = {0};
    int i = 0;
    
    for(i=0; i<10; i++)
    {
        a[i] = i + 1;
        
        LinkQueue_Push(queue, a + i);
    }
    
    printf("Pop: %d\n", *(int*)LinkQueue_Pop(queue));
    printf("Top: %d\n", *(int*)LinkQueue_Top(queue));
    printf("Length: %d\n", Get_Queue_Length(queue));
    
    //Clean_LinkQueue(queue);
    
    while( Get_Queue_Length(queue) > 0 )
    {
        printf("Pop: %d\n", *(int*)LinkQueue_Pop(queue));
    }
    
    Destroy_LinkQueue(queue);
	return 0;
}

2.使用两个链式队列实现链式栈：

   a.使用两个队列实现栈，远远没有通过栈来实现队列高效，但是就把这个小算法当做，一个队列的应用来练习吧。
   b.首先定义两个队列，不考虑第一次压栈操作，判断q1和q2队列，哪个为空队列，把需要压栈的数据，放入非空队列中，例如q1中。push操作就，一直往这个非空队列中加入数据。pop操作的时候，也需要判断哪个队列为空队列，就把非空队列中的前n-1个元素，都放入空队列中，例如把q1中的前n-1个元素都放入q2中，此时把q1队列中最后一个数据出栈。后q1为空，q2为非空！如此循环。。。
如图：
数据结构学习笔记(9.栈跟队列的特殊实现)
代码如下：
LinkStack.c文件：
#include <stdio.h>
#include <malloc.h>
#include "LinkStack.h"
#include "LinkQueue.h"

typedef struct _tag_link_stack //栈的结构 
{
	LinkQueue* q1;
	LinkQueue* q2;
}link_stack;


LinkStack* Creat_LinkStack()
{
	link_stack* ret = (link_stack*)malloc(sizeof(link_stack));
	if(NULL != ret)
	{
		ret->q1 = Creat_LinkQueueHead();
		ret->q2 = Creat_LinkQueueHead();
		if((NULL == ret->q1) || (NULL == ret->q2))
		{
			free(ret);
			ret = NULL;
		}
	} 
	return ret;
}


void  Destroy_LinkStack(LinkStack* stack)
{
	if(NULL != stack)
	{
		link_stack* temp = (link_stack*)stack;
		Destroy_LinkQueue(temp->q1);
		Destroy_LinkQueue(temp->q2);
		free(stack);
	}
}


int Get_LinkStack_Length(LinkStack* stack)
{
	/*q1 和 q2 注定有一个为空 一个非空*/ 
	int ret = 0; 
	if(NULL != stack)
	{
		link_stack* temp = (link_stack*)stack;
		ret = Get_Length(temp->q1);
		if(0 == ret) //如果q1队列为空 
		{
			 ret = Get_Length(temp->q2); //就把q2队列的长度返回 
		}
	}
	return ret; 
}


int Clean_LinkStack(LinkStack* stack)
{
	int ret = 0;
	if(NULL != stack)
	{
		ret = 1;
		link_stack* temp = (link_stack*)stack;
		Clean_LinkStack(temp->q1);
		Clean_LinkStack(temp->q2);
	} 
	return 0;
} 


int LinkStack_Push(LinkStack* stack, void* node)
{
	int ret = 0;
	if((NULL != stack) && (NULL != node))
	{
		ret = 1;
		link_stack* temp = (link_stack*)stack;
		if(Get_Length(temp->q1) == 0) //如果q1队列为空 就把数据加入q2队列 
		{
			LinkQueue_Push(temp->q2, node);
		} 
		else
		{
			LinkQueue_Push(temp->q1, node);//如果q2队列为空 就把数据加入q1队列
		} 
		
	} 
	return 0;
}


void* LinkStack_Pop(LinkStack* stack)
{
	void* ret = NULL; 
	if(NULL != stack)
	{
		link_stack* temp = (link_stack*)stack;
		if(Get_Length(temp->q1) == 0) //如果q1为空  就要把q2的前n-1 放入q1中 
		{
			while((Get_Length(temp->q2) - 1))
			{
				LinkQueue_Push(temp->q1, LinkQueue_Pop(temp->q2));
			} 
			ret = LinkQueue_Pop(temp->q2); //此时q2为空了 
		} 
		else //否则相反 
		{
			while((Get_Length(temp->q1) - 1))
			{
				LinkQueue_Push(temp->q2, LinkQueue_Pop(temp->q1));
			} 
			ret = LinkQueue_Pop(temp->q1); //此时q1为空了 
		} 
	} 
	return ret;
}


void* Get_LinkStack_Top(LinkStack* stack)
{
	void* ret = NULL; 
	if(NULL != stack)
	{
		link_stack* temp = (link_stack*)stack;
		if(Get_Length(temp->q1) == 0) //如果q1为空  就要把q2的前n-1 放入q1中 
		{
			while((Get_Length(temp->q2) - 1))
			{
				LinkQueue_Push(temp->q1, LinkQueue_Pop(temp->q2));
			} 
			ret = LinkQueue_Top(temp->q2); 
			LinkQueue_Push(temp->q1, LinkQueue_Pop(temp->q2));
		} 
		else //否则相反 
		{
			while((Get_Length(temp->q1) - 1))
			{
				LinkQueue_Push(temp->q2, LinkQueue_Pop(temp->q1));
			} 
			ret = LinkQueue_Top(temp->q1);  
			LinkQueue_Push(temp->q2, LinkQueue_Pop(temp->q1));
		} 
	} 
	return ret;
}

LinkStack.h文件：
#ifndef __LinkStack_H__
#define __LinkStack_H__
typedef void LinkStack;

LinkStack* Creat_LinkStack(void);

void  Destroy_LinkStack(LinkStack* stack);

int Get_LinkStack_Length(LinkStack* stack);

int Clean_LinkStack(LinkStack* stack);

int LinkStack_Push(LinkStack* stack, void* node);

void* Get_LinkStack_Top(LinkStack* stack);

void* LinkStack_Pop(LinkStack* stack); 

#endif

main.c文件：
#include <stdio.h>
#include <stdlib.h>
#include "LinkStack.h"

int main(int argc, char *argv[]) 
{
	LinkStack*  stack = Creat_LinkStack();
	int a = 9;
	int b = 12;
	int c = 1;
	
	LinkStack_Push(stack,&a);
	LinkStack_Push(stack,&b);
	LinkStack_Push(stack,&c);
	
	printf("%d\n",Get_LinkStack_Length(stack));
	
	printf("%d\n",*(int*)Get_LinkStack_Top(stack));
	
	printf("%d\n",*(int*)LinkStack_Pop(stack));
	printf("%d\n",*(int*)LinkStack_Pop(stack));
	printf("%d\n",*(int*)LinkStack_Pop(stack));
	Destroy_LinkStack(stack);
	return 0;
}



相关推荐