栈的链式存储结构（复习）_链栈选择题-CSDN博客

本文链接：https://blog.csdn.net/csdnxmj/article/details/78594046

本文介绍了一种使用链式栈实现队列的方法。通过定义链式栈的数据结构，并实现初始化、压栈、遍历等功能，最后展示了如何通过两个栈操作实现队列的先进先出特性。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

/*LinkStack.h函数*/

#ifndef _LINKSTACK_H_
#define _LINKSTACK_H_

#define SUCCESS 10000
#define FAILURE -10000


typedef int Elemtype;

struct StackNode
{
	Elemtype data;
	struct StackNode *next;
};

typedef struct StackNode StackNode;

struct LinkStack
{
	StackNode *top;
	int count;
};

typedef struct LinkStack LinkStack;


int InitStack(LinkStack *S);
int EmptyStack(LinkStack *s);
int Push(LinkStack *S,Elemtype e);
int TraverseStack(LinkStack *S);
int Pop(LinkStack *S);
int Queue(LinkStack *S);


#endif




/*Main.c函数*/

#include <stdio.h>
#include "LinkStack.h"

int main()
{
	LinkStack LinkStack;
	int ret;
	int i = 0;

	ret = InitStack(&LinkStack);
	if(SUCCESS == ret)
	{
		printf("Init success!\n");
	}
	else
	{
		printf("Init failure!\n");
	}

	ret = EmptyStack(&LinkStack);
	if(SUCCESS == ret)
	{
		printf("The satck is empty!\n");
	}
	else
	{
		printf("The stack is not empty!\n");
	}

	for(i = 0;i < 5;i++)
	{
		ret = Push(&LinkStack,i);
		if(SUCCESS == ret)
		{
			printf("Push %d success!\n",i);
		}
		else
		{
			printf("Push %d failure!\n",i);
		}
	}

	ret = Pop(&LinkStack);
	if(FAILURE == ret)
	{
		printf("Pop failure!\n");
	}
	else
	{
		printf("Pop %d success!\n",ret);
	}

	ret = TraverseStack(&LinkStack);
	if(SUCCESS == ret)
	{
		printf("Traverse the stack success!\n");
	}
	else
	{
		printf("Traverse the stack failure!\n");
	}

	return 0;
}




/*LinkStack.c函数*/

#include <stdio.h>
#include "LinkStack.h"
#include <stdlib.h>


int InitStack(LinkStack *S)
{
	S->top = NULL;
	S->count = 0;

	return SUCCESS;
}

int EmptyStack(LinkStack *S)
{
	if(NULL == S)
	{
		return FAILURE;
	}

	if(S->count == 0)
	{
		return SUCCESS;
	}
	else
	{
		return FAILURE;
	}

}


int Push(LinkStack *S,Elemtype e)
{
	if(NULL == S)
	{
		return FAILURE;
	}

	StackNode *p = (StackNode *)malloc(sizeof(StackNode));
	if(NULL == p)
	{
		return FAILURE;
	}

	p->data = e;
	p->next = S->top;
	S->top = p;
	S->count++;

	return SUCCESS;
}

int TraverseStack(LinkStack *S)  
{
	if(S->top == NULL)
	{
		return FAILURE;
	}

	int i = 0;

	for( i = 0;i < S->count;i++)
	{
		printf("%d ",S->top->data);
		S->top = S->top->next;
	}
	printf("\n");

	return SUCCESS;
}


int Queue(LinkStack *S)
{
	LinkStack Stack;

	if(FAILURE == InitStack(&Stack))
	{
		return FAILURE;
	}

	int i = 0;

	for(i = 0;i < 5;i++)
	{
		Push(&Stack,Pop(S));
	}
	
	for(i = 0;i < 5;i++)
	{
		printf("%d ",Pop(&Stack));
	}
	printf("\n");

	return SUCCESS;
}


int Pop(LinkStack *S)
{
	if(NULL == S)
	{
		return FAILURE;
	}

	StackNode *p = (StackNode *)malloc(sizeof(StackNode));
	if(NULL == p)
	{
		return FAILURE;
	}

	Elemtype e;
	e = S->top->data;
	p = S->top;
	S->top = S->top->next;
	free(p);
	S->count--;

	return e;

}


/*利用栈的接口函数实现的队列：即先进后出变为先进先出*/

#include <stdio.h>
#include "LinkStack.h"

int main()
{
	LinkStack LinkStack;
	int ret;
	int i = 0;

	for(i = 0;i < 5;i++)
	{
		ret = Push(&LinkStack,i);
		if(SUCCESS == ret)
		{
			printf("Push %d success!\n",i);
		}
		else
		{
			printf("Push %d failure!\n",i);
		}
	}

	ret = Queue(&LinkStack);  //接口函数中具体实现
	if(SUCCESS == ret)
	{
		printf("Use the Stack to Queue is success!\n");
	}
	else
	{
		printf("Use the stack to Queue is failure!\n");
	}

	return 0;
}