堆栈面试题之共享栈，最小栈，判断一个序列是否由一个栈进行基本的入出栈操作而得到1.共享栈：2.最小栈：3.判断一个序列是否由一个栈进行基本操作而得到

80 阅读 0 评论 53 点赞

我是靠谱客的博主幸福背包，最近开发中收集的这篇文章主要介绍堆栈面试题之共享栈，最小栈，判断一个序列是否由一个栈进行基本的入出栈操作而得到1.共享栈：2.最小栈：3.判断一个序列是否由一个栈进行基本操作而得到，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

`1.共享栈：`

方法：用数组实现，定义一个结构体，结构体中包含2个栈，其中一个栈的栈底数组中下标为0处，而两外一个栈的栈底为数组的最大值处。当两个栈的栈顶相遇时，即栈满。

`2.最小栈：`

即：每次取栈顶元素取出来当前栈中最小的元素。

方法1：使用2个栈来实现，一个栈用来保存入栈的所有元素，另外一个栈用来保存当前栈中最小的元素。所以在取栈顶元素时就从保存较小元素的那个栈中取。可能讲的不是很清楚，看下图所示：

方法2：使用1个栈来实现，每次入栈两个元素，第一个元素是需要入栈的元素，另一个元素是与栈顶比较时较小的值，如果栈顶元素较小，那么第二个元素就是栈顶元素。否则第二个元素就是当前要入栈的元素。如下图所示：

`3.判断一个序列是否由一个栈进行基本操作而得到`

例如：

最初的入栈序列为：a,b,c,d,e

判断序列：a,b,e,d,c能否由以上序列经过出入栈而得到

如果可以得到就返回1，否则就返回0.

方法：使用两个栈，如果最初的序列和需要判断的序列的元素相同，就让两个序列不同，就让最初的序列依旧入栈，知道遇到相同的元素.然后判断的结束的标志就是：最初的序列的长度和需要判断的序列的长度相同，且都入到各自的栈中。下面是上面3个题的代码实现： 
 
   第一题：共享栈：

#pragma once

#include<stddef.h>
#define ShareMaxSize 1000
typedef char ShareStackType;
typedef struct ShareStack
{
	ShareStackType data[ShareMaxSize];
	size_t top0;
	size_t top1;
}ShareStack;

//Top0的相关操作
//初始化栈
void InitShareStackTop0(ShareStack* stack);

//入栈
void PushShareStackTop0(ShareStack* stack,ShareStackType value);

//出栈
void PopShareStackTop0(ShareStack* stack);

//取栈首元素
int TopShareStackTop0(ShareStack* stack,ShareStackType* top);

//Top1的相关操作
//入栈
void PushShareStackTop1(ShareStack* stack,ShareStackType value);

//出栈
void PopShareStackTop1(ShareStack* stack);

//取栈首元素
int TopShareStackTop1(ShareStack* stack,ShareStackType* top);

#include"ShareStack.h"
#include<stdio.h>
void InitShareStackTop0(ShareStack* stack)
{
	if(stack == NULL)
	{
		//非法输入
		return;
	}
	stack->top0 = 0;
	stack->top1 = ShareMaxSize;
}
void PushShareStackTop0(ShareStack* stack,ShareStackType value)
{
	if(stack == NULL)
	{
		return;
	}
	if(stack->top0 >= stack->top1 )
	{
		//说明共享栈已满，直接return
		return;
	}
	stack->data [stack->top0 ++] = value;
}
void PopShareStackTop0(ShareStack* stack)
{
	if(stack == NULL)
	{
		return;
	}
	if(stack->top0 == 0)
	{
		//说明top1的栈已是空栈
		return;
	}
	--stack->top0 ;
}
int TopShareStackTop0(ShareStack* stack,ShareStackType* top)
{
	if(stack == NULL)
	{
		return 0;
	}
	if(stack->top0 < 0)
	{
		return 0;
	}
	*top = stack->data [stack->top0 - 1];
	return 1;
}

//Top1
void PushShareStackTop1(ShareStack* stack,ShareStackType value)
{
	if(stack == NULL)
	{
		return;
	}
	if(stack->top1 <= stack->top0 )
	{
		return;
	}
	stack->data [stack->top1 --] = value;
}
void PopShareStackTop1(ShareStack* stack)
{
	if(stack == NULL)
	{
		return;
	}
	if(stack->top1 == ShareMaxSize)
	{
		return;
	}
	++stack->top1 ;
}
int TopShareStackTop1(ShareStack* stack,ShareStackType* top)
{
	if(stack == NULL)
	{
		return 0;
	}
	if(stack->top1 == ShareMaxSize)
	{
		return 0;
	}
	*top = stack->data [stack->top1 + 1];
	return 1;
}
#include"ShareStack.h"
#include<stdio.h>
#include<windows.h>

#define TEST_HEADER printf("n================%s=================n",__FUNCTION__)

void TestTop0()
{
	ShareStack stack;
	ShareStackType top;
	TEST_HEADER;
	InitShareStackTop0(&stack);
	PushShareStackTop0(&stack,'a');
	PushShareStackTop0(&stack,'b');
	PushShareStackTop0(&stack,'c');
	PushShareStackTop0(&stack,'d');
	TopShareStackTop0(&stack,&top);
	printf("top:expect is d,actual is %cn",top);
	PopShareStackTop0(&stack);

	TopShareStackTop0(&stack,&top);
	printf("top:expect is c,actual is %cn",top);
	PopShareStackTop0(&stack);

	TopShareStackTop0(&stack,&top);
	printf("top:expect is b,actual is %cn",top);
	PopShareStackTop0(&stack);

	TopShareStackTop0(&stack,&top);
	printf("top:expect is a,actual is %cn",top);
	//PopShareStackTop0(&stack);
}
void TestTop1()
{
	ShareStack stack;
	ShareStackType top;
	TEST_HEADER;
	InitShareStackTop0(&stack);
	PushShareStackTop1(&stack,'a');
	PushShareStackTop1(&stack,'b');
	PushShareStackTop1(&stack,'c');
	PushShareStackTop1(&stack,'d');
	TopShareStackTop1(&stack,&top);
	printf("top:expect is d,actual is %cn",top);
	PopShareStackTop1(&stack);

	TopShareStackTop1(&stack,&top);
	printf("top:expect is c,actual is %cn",top);
	PopShareStackTop1(&stack);

	TopShareStackTop1(&stack,&top);
	printf("top:expect is b,actual is %cn",top);
	PopShareStackTop1(&stack);

	TopShareStackTop1(&stack,&top);
	printf("top:expect is a,actual is %cn",top);
	PopShareStackTop0(&stack);
}
int main()
{
	TestTop0();
	TestTop1();
	system("pause");
	return 0;
}

第二题：最小栈（在下面的代码中调用了栈的相关操作，但是其相关操作已经在前面的博客中写过）

#pragma once

#include"seqstack.h"

typedef char MiniStackType;
typedef struct mini_stack
{
	seqstack data;
	seqstack mini;
}mini_stack;

//初始化最小栈
void InitMiniStack(mini_stack* stack);

//入栈
void PushMiniStack(mini_stack* stack,MiniStackType value);

//出栈
void PopMiniStack(mini_stack* stack);

//取栈顶元素
int TopMiniStack(mini_stack* stack,MiniStackType* top);
//方法2
//使用同一个栈，把一个元素一次入栈2回，较小的元素第二次入栈，较大的元素第一次入栈

typedef struct MiniStack
{
	seqstack min;
}MiniStack;
typedef char MiniType;
void InitMini(MiniStack* stack);

void PushMini(MiniStack* stack,MiniType value);

void PopMini(MiniStack* stack);

int TopMini(MiniStack* stack,MiniType* top);

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

void InitMiniStack(mini_stack* stack)
{
	if(stack == NULL)
	{
		return;
	}
	InitStack(&stack->data);
	InitStack(&stack->mini );
}
void PushMiniStack(mini_stack* stack,MiniStackType value)
{
	int ret = 0;
	MiniStackType min;
	MiniStackType top;
	if(stack == NULL)
	{
		return;
	}
	if(stack->mini.size == 0)
	{
		PushStack(&stack->mini,value);
		PushStack(&stack->data,value);
		return;
	}
	else
	{
		ret = TopStack(&stack->mini,&top);
		min = top < value ? top : value;
		PushStack(&stack->mini,min);
		PushStack(&stack->data,value);
	}
}
void PopMiniStack(mini_stack* stack)
{
	if(stack == NULL)
	{
		return;
	}
	PopStack(&stack->mini);
	PopStack(&stack->data);
}
int TopMiniStack(mini_stack* stack,MiniStackType* top)
{
	if(stack == NULL)
	{
		return 0;
	}
	return TopStack(&stack->mini,top);
}
/
/
/
//以下是第二种方法
void InitMini(MiniStack* stack)
{
	if(stack == NULL)
	{
		return;
	}
	InitStack(&stack->min );
}
void PushMini(MiniStack* stack,MiniType value)
{
	int ret = 0;
	MiniType top;
	MiniType min;
	if(stack == NULL)
	{
		return;
	}
	if(stack->min .size == 0)
	{
		PushStack(&stack->min ,value);
		PushStack(&stack->min ,value);
	}
	else
	{
		ret = TopStack(&stack->min ,&top);
		if(ret)
		{
			min = top < value ? top : value;
			PushStack(&stack->min ,value);
			PushStack(&stack->min ,min);
		}
	}
}
void PopMini(MiniStack* stack)
{
	if(stack == NULL)
	{
		return;
	}
	PopStack(&stack->min );
	PopStack(&stack->min );
}
int TopMini(MiniStack* stack,MiniType* top)
{
	if(stack == NULL)
	{
		return 0;
	}
	return TopStack(&stack->min ,top);
}

#include"MiniStack.h"
#include<stdio.h>
#include<windows.h>

#define TEST_HEADER printf("n===================%s==================n",__FUNCTION__)
void Test()
{
	mini_stack stack;
	MiniStackType top;
	int ret = 0;
	int ret1 = 0;
	int ret2 = 0;
	TEST_HEADER;
	InitMiniStack(&stack);
	PushMiniStack(&stack,'e');
	PushMiniStack(&stack,'s');
	PushMiniStack(&stack,'a');
	PushMiniStack(&stack,'c');
	PushMiniStack(&stack,'b');
	ret = TopMiniStack(&stack,&top);
	//printf("ret expect is 1,actual is %dn",ret);
	printf("top expect is a,actual is %cn",top);
	PopMiniStack(&stack);
	PopMiniStack(&stack);
	PopMiniStack(&stack);
	ret1 = TopMiniStack(&stack,&top);
	//printf("ret expect is 1,actual is %dn",ret1);
	printf("top expect is e,actual is %cn",top);
	PopMiniStack(&stack);

	ret2 = TopMiniStack(&stack,&top);
	//printf("ret expect is 1,actual is %dn",ret2);
	printf("top expect is e,actual is %cn",top);
	PopMiniStack(&stack);
}
void Test2()
{
	MiniStack stack;
	MiniType top;
	int ret = 0;
	TEST_HEADER;
	InitMini(&stack);
	PushMini(&stack,'e');
	PushMini(&stack,'s');
	PushMini(&stack,'a');
	PushMini(&stack,'c');
	PushMini(&stack,'b');
	ret = TopMini(&stack,&top);
	//printf("ret expect is 1,actual is %dn",ret);
	printf("top expect is a,actual is %cn",top);
	PopMini(&stack);
	PopMini(&stack);
	PopMini(&stack);
	ret = TopMini(&stack,&top);
	//printf("ret expect is 1,actual is %dn",ret);
	printf("top expect is e,actual is %cn",top);
	PopMini(&stack);
	TopMini(&stack,&top);
	printf("top expect is e,actual is %cn",top);
}
int main()
{
	Test();
	Test2();
	system("pause");
	return 0;
}

第三题：判断序列

int IsOrderByStack(char input[],int input_size,char output[],int output_size)
{
	int input_index = 0;
	int output_index = 0;
	char top ;
	seqstack stack;
	InitStack(&stack);
	if(input == NULL || output == NULL)
	{
		return 0;
	}
	for(input_index = 0;input_index < input_size;input_index++)
	{
		PushStack(&stack,input[input_index]);
		while(TopStack(&stack,&top))
		{
			if(output_index > output_size)
			{
				return 0;
			}
			if(top == output[output_index])
			{
				++output_index;
				PopStack(&stack);
			}
			else
			{
				break;
			}
		}
	}
	if(input_index == output_index && TopStack(&stack,&top) == 0)
	{
		return 1;
	}
	return 0;
}

以上代码都是在VS2010中实现的^+^.