栈和队列面试题

程序员文章站 2022-06-08 18:00:52

...

1. 实现一个栈，要求实现Push（出栈）、Pop（入栈）、Min（返回最小值）的时间复杂度为O（1）

用两个栈实现
思路：

用两个栈来实现
一个栈为普通栈，一个栈专门放最小值
当普通栈要入的数据小于等于min栈的栈顶的时候两个栈同时入；反之如果大于的话min栈不入数据
出栈的时候如果min栈中的数据等于普通栈中的数据，两个栈同时出，否则min栈只将栈顶的元素返回即可

原理图：

入栈图：

栈和队列面试题

出栈图

栈和队列面试题

typedef int DataType;
#define Max_Size 100
typedef struct Stack
{
	DataType arry[Max_Size];
	int top;
}Stack;
void StackInit(Stack*Pstack) //栈的初始化
{
	assert(Pstack != NULL);
	Pstack->top = 0;
}
#if 0
DataType MinStackTop(Stack*PStack)//最小值栈的栈顶
{
	assert(PStack != NULL);
	return PStack->arry[PStack->top - 1];//这里的栈顶元素一定是top-1
}
DataType NormalStackTop(Stack*PStack)//普通栈的栈顶
{
	assert(PStack != NULL);
	return PStack->arry[PStack->top - 1];
}
void PushStack(Stack*NormalStack,Stack*MinStack, DataType data)//压栈
{
	assert(NormalStack != NULL);
	assert(MinStack != NULL);
	if (NormalStack->top==0&&MinStack->top==0)
	{
		NormalStack->arry[NormalStack->top++] = data;
		MinStack->arry[MinStack->top++] = data;
	}
	NormalStack->arry[NormalStack->top++] = data;
	if (MinStackTop(MinStack) >= data)//当要压的数小于最小值栈的栈顶时，两个栈同时压栈
	{
		MinStack->arry[MinStack->top++] = data;
	}
}
void PopStack(Stack*NormalStack,Stack*MinStack)//出栈
{
	assert(NormalStack != NULL);
	assert(MinStack != NULL);
	if (NormalStackTop(NormalStack) == MinStackTop(MinStack))//只有当两个栈的元素相同的时候两个栈才同时出栈
	{
		NormalStack->top--;
		MinStack->top--;
	}
	else
	{
		NormalStack->top--;
	}
}
DataType Min(Stack*NormalStack, Stack*MinStack)//返回最小值
{
	assert(NormalStack != NULL);
	assert(MinStack != NULL);
	return MinStackTop(MinStack);
}

测试用例：

void MinTest()
{
	Stack NormalStack;
	Stack MinStack;
	StackInit(&NormalStack);
	StackInit(&MinStack);
	int i = 0;
	int arry[] = { 4, 5, 1, 1, 1, 2, 3, 0 };
	for (i = 0; i < 8; i++)
	{
		PushStack(&NormalStack, &MinStack, arry[i]);
		printf("栈顶元素为：%d\n", NormalStackTop(&NormalStack));
		printf("栈中的最小元素为：%d\n", Min(&NormalStack, &MinStack));
	}
	printf("-----------------------------------------------------------------\n");
	for (i = 0; i < 7; i++)
	{
		PopStack(&NormalStack, &MinStack);
		printf("栈顶元素为：%d\n", NormalStackTop(&NormalStack));
		printf("栈中的最小元素为：%d\n", Min(&NormalStack, &MinStack));
	}
}

用一个栈实现

思路：与上面的思路十分相似，只不过是将数据压到了一个栈中，这时候就要注意最小值返回时是top-1还是top-2。

原理图：

栈和队列面试题

出栈图：

栈和队列面试题

DataType MinStackTop(Stack*PStack)//存放最小值的栈顶
{
	assert(PStack != NULL);
	return PStack->arry[PStack->top - 2];//注意这里是top-2
}
DataType NormalStackTop(Stack*PStack)//普通栈的栈顶
{
	assert(PStack != NULL);
	return PStack->arry[PStack->top - 1];
}
void Push(Stack*Pstack, DataType data)//压栈
{
	assert(Pstack != NULL);
	Pstack->arry[Pstack->top++] = data;
}
void PushStack(Stack*Pstack, DataType data)//将最小值和数据压栈
{
	assert(Pstack != NULL);
	if (Pstack->top == 0)
	{
		Push(Pstack, data);
		Push(Pstack, data);
	}
	if (MinStackTop(Pstack) <= data)
	{
		Push(Pstack, MinStackTop(Pstack));
		Push(Pstack, data);
	}
	else
	{
		Push(Pstack, data);
		Push(Pstack, data);
	}
}
void PopStack(Stack*Pstack)//出栈
{
	assert(Pstack != NULL);
	Pstack->top -= 2;//出两次，所以top-2
}
DataType Min(Stack*Pstack)//返回最小值
{
	assert(Pstack != NULL);
	return Pstack->arry[Pstack->top - 2];
}

测试用例：

void MinTest()
{
	Stack stack;
	StackInit(&stack);
	int arry[] = { 4, 5, 1, 1, 1, 2, 3, 0 };
	int i = 0;
	for (i = 0; i < 8; i++)
	{
		PushStack(&stack,arry[i]);
		printf("栈顶元素为：%d\n", NormalStackTop(&stack));
		printf("栈中的最小元素为：%d\n", Min(&stack));
	}
	for (i = 0; i < 8; i++)
	{
		PopStack(&stack);
		printf("栈顶元素为：%d\n", NormalStackTop(&stack));
		printf("栈中的最小元素为：%d\n", Min(&stack));
	}
}

2. 使用两个栈实现一个队列

思路：

栈的出栈顺序是先进后出，而队列出的顺序是先进先出
用两个栈实现一个队列，可以将数据压到栈1里面
再将栈1里面的数据Pop出来，压到栈2里面，这样就实现了队列先进先出的要求
这个时候再去实现队列的一系列操作

原理图：

栈和队列面试题

要用到的栈的操作函数stack.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<string.h>
typedef int DataType;
#define Max_Size 100
typedef struct Stack
{
	DataType arry[Max_Size];
	int top;
}Stack;
void StackInit(Stack*Pstack)
{
	assert(Pstack != NULL);
	Pstack->top = 0;
}
void DestoryStack(Stack*Pstack)
{
	assert(Pstack != NULL);
	Pstack->top = 0;
}
void StackPush(Stack*Pstack,DataType data)
{
	assert(Pstack != NULL);
	Pstack->arry[Pstack->top++] = data;
}
void StackPop(Stack*Pstack)
{
	assert(Pstack != NULL);
	assert(Pstack->top > 0);
	Pstack->top--;
}
DataType StackTop(Stack*Pstack)
{
	assert(Pstack != NULL);
	return Pstack->arry[Pstack->top - 1];
}
int StackIsEmpty(Stack*Pstack)
{
	assert(Pstack != NULL);
	return Pstack->top == 0 ? 1 : 0;
}

#include "Stack.h"

typedef struct QueueBy2Stack
{
	Stack stack1;
	Stack stack2;
}QueueBy2Stack;
void QueueBy2StackInit(QueueBy2Stack*pQ)//队列的初始化
{
	assert(pQ != NULL);
	StackInit(&(pQ->stack1));
	StackInit(&(pQ->stack2));
}
void QueueBy2StackDestory(QueueBy2Stack*pQ)//队列的销毁
{
	assert(pQ != NULL);
	DestoryStack(&(pQ->stack2));
	DestoryStack(&(pQ->stack1));
}
void QueueBy2StackPush(QueueBy2Stack*pQ,DataType data)//队列里面插数据
{
	assert(pQ!= NULL);
	StackPush(&(pQ->stack1), data);
}
void QueueBy2StackMove(QueueBy2Stack*pQ)//两个栈之间数据的移动，每次都往空的那个栈里面移动
{
	assert(pQ != NULL);
	if (StackIsEmpty(&(pQ->stack2)))
	{
		while (!StackIsEmpty(&(pQ->stack1)))
		{
			int tmp = StackTop(&(pQ->stack1));
			StackPush(&(pQ->stack2), tmp);
			StackPop(&(pQ->stack1));
		}
	}
}
void QueueBy2StackPop(QueueBy2Stack*pQ)//出队列
{
	assert(pQ != NULL);
	QueueBy2StackMove(pQ);
	if (!StackIsEmpty(&(pQ->stack2)))
	{
		StackPop((&pQ->stack2));
	}
}
DataType QueueBy2StackFront(QueueBy2Stack*pQ)//队列的第一个数据
{
	assert(pQ != NULL);
	QueueBy2StackMove(pQ);
	assert(!StackIsEmpty(&(pQ->stack2))); 
	return StackTop(&(pQ->stack2));
}

测试用例：

void QueueBy2StackTest()
{
	QueueBy2Stack pQ;
	QueueBy2StackInit(&pQ);
	int i = 0;
	int arry[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
	for (i = 0; i < sizeof(arry) / sizeof(arry[0]); i++)
	{
		QueueBy2StackPush(&pQ, arry[i]);
	}
	printf("队列的第一个元素为：%d\n", QueueBy2StackFront(&pQ));
	for (i = 0; i < sizeof(arry) / sizeof(arry[0])-1; i++)
	{
		QueueBy2StackPop(&pQ);
		printf("队列的第一个元素为：%d\n", QueueBy2StackFront(&pQ));
	}
	QueueBy2StackDestory(&pQ);
}

3. 使用队列实现一个栈

这道题是将上面那道题的要求反过来，用两个队列实现一个栈，说先同上面一样我们要用队列先进先出的特点实现栈先进后出的特点。

思路：

用两个队列
将一个队列中的数据除最后一个除外均移动到另外一个队列中
然后将最后一个数据（也就是栈要往出弹的第一个元素）拿出来压到为空的那个队列中
每一次往队列里面插数据的时候，都是往不为空的那个队列里面插

原理图：

栈和队列面试题

队列的一系列操作函数Queue.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int DataType;
typedef struct QNode
{
	DataType data;
	struct QNode *Pnext;
}QNode;
typedef struct Queue
{
	QNode*Pfront;
	QNode*Prear;
	int  size;
}Queue;
void QueueInit(Queue *PQ)//队列初始化
{
	assert(PQ != NULL);
	PQ->Pfront = NULL;
	PQ->Prear = NULL;
	PQ->size = 0;
}
void DestoryQueue(Queue*PQ)//销毁队列
{
	assert(PQ != NULL);
	QNode*Pnext = NULL;
	QNode*Pnode = NULL;
	for (Pnode = PQ->Pfront; Pnode != NULL; Pnode = Pnext)
	{
		Pnext = Pnode->Pnext;
		free(Pnode);
	}
	PQ->Pfront = NULL;
	PQ->Prear = NULL;
	PQ->size = 0;
}
void QueuePush(Queue*PQ, DataType data)//插入
{
	assert(PQ != NULL);
	QNode*Pnewnode = (QNode*)malloc(sizeof(QNode));
	Pnewnode->data = data;
	Pnewnode->Pnext = NULL;
	PQ->size++;
	if (PQ->Pfront == NULL)
	{
		PQ->Pfront = Pnewnode;
		PQ->Prear = Pnewnode;
		return;
	}
	assert(Pnewnode != NULL);
	PQ->Prear->Pnext = Pnewnode;//尾插，让旧的最后一个节点指向新的的节点
	PQ->Prear = Pnewnode;//更新尾指针
}
void PopQueue(Queue*PQ)//头删
{
	assert(PQ != NULL);
	assert(PQ->Pfront != NULL);
	PQ->size--;
	QNode*PFront = PQ->Pfront;
	PQ->Pfront = PFront->Pnext;
	free(PFront);
	if (PQ->Pfront == NULL)//当只有一个节点的时候删除完成之后Pfront和Prear都要重新置空
	{
		PQ->Prear = NULL;
	}
}
DataType FrontData(Queue*PQ)//队列中的第一个数据
{
	assert(PQ != NULL);
	assert(PQ->Pfront != NULL);
	return PQ->Pfront->data;
}
int QueueSize(Queue*PQ)
{
	assert(PQ != NULL);
	return PQ->size;
}
int QueueIsEmpty(Queue*PQ)//判断队列是不是空 
{
	assert(PQ != NULL);
	return PQ->size == 0 ? 1 : 0;
}

#include"Queue.h"
typedef struct StackBy2Queue
{
	Queue Queue1;
	Queue Queue2;
}StackBy2Queue;
void StackBy2QueueInit(StackBy2Queue*SQ)//初始化
{
	assert(SQ != NULL);
	QueueInit(&(SQ->Queue1));
	QueueInit(&(SQ->Queue2));
}
void StackBy2QueueDestory(StackBy2Queue*SQ)//销毁
{
	assert(SQ != NULL);
	DestoryQueue(&(SQ->Queue1));
	DestoryQueue(&(SQ->Queue2));
}

void StackBy2QueuePush(StackBy2Queue*SQ,DataType data)//插入数据
{
	assert(SQ != NULL);
	Queue*EmptyQ =&(SQ->Queue2);
	Queue*NotEmptyQ = &(SQ->Queue1);
	if (!(QueueIsEmpty(&(SQ->Queue2))))
	{
		NotEmptyQ = &(SQ->Queue2);
		EmptyQ = &(SQ->Queue1);
	}
	QueuePush(NotEmptyQ, data);//一直往不为空的栈中压数据
}
void StackBy2QueuePop(StackBy2Queue*SQ)
{
	assert(SQ != NULL);
	Queue*EmptyQ = &(SQ->Queue2);
	Queue*NotEmptyQ = &(SQ->Queue1);
	int data = 0;
	if (!(QueueIsEmpty(&(SQ->Queue2))))
	{
		NotEmptyQ = &(SQ->Queue2);
		EmptyQ = &(SQ->Queue1);
	}
	while (QueueSize(NotEmptyQ) > 1)//将不为空的队列除最后一个数外，全部压到空的队列中
	{
		data = FrontData(NotEmptyQ);
		PopQueue(NotEmptyQ);
		QueuePush(EmptyQ, data);
	}
}
DataType StackBy2QueueFront(StackBy2Queue*SQ)//返回栈的第一个数据
{
	assert(SQ != NULL);
	int data = 0;
	Queue*EmptyQ = &(SQ->Queue2);
	Queue*NotEmptyQ = &(SQ->Queue1);
	if (!(QueueIsEmpty(&(SQ->Queue2))))
	{
		NotEmptyQ = &(SQ->Queue2);
		EmptyQ = &(SQ->Queue1);
	}
	while (QueueSize(NotEmptyQ) > 1)//将NotEmpty队列中仅剩的一个元素拿出来
	{
		data = FrontData(NotEmptyQ);
		PopQueue(NotEmptyQ);
		QueuePush(EmptyQ, data);
	}
	data = FrontData(NotEmptyQ);
	PopQueue(NotEmptyQ);
	QueuePush(EmptyQ, data);
	return data;
}

测试用例：

void StackBy2QueueTest()
{
	StackBy2Queue stack;
	StackBy2QueueInit(&stack);
	int arry[] = { 1, 2, 3, 4, 5, 6, 7, 8 };
	int i = 0;
	for (i = 0; i < sizeof(arry) / sizeof(arry[0]); i++)
	{
		StackBy2QueuePush(&stack, arry[i]);
	}
	for (i = 0; i <= sizeof(arry) / sizeof(arry[0]); i++)
	{
		printf("栈里面第一个元素为：%d\n", StackBy2QueueFront(&stack));
		StackBy2QueuePop(&stack);
	}

}

4. 元素出栈，入栈顺序的合法性，如入栈的序列（1,2,3,4,5），出栈序列为（4,5,3,2,1）

这个题就是判断出栈是否正确。那就依次看出栈的序列中的数据是否可以经过入栈序列操作后得到

方法1

思路：

当outch不等于inch的时候或者栈为空的时候就一直压栈直到inch和outch相等为止，然后将相等的那个元素从栈里面弹出去
outch和inch相等的时候inch[]的下标要往后移一个，并且将相同的元素出栈
当inch的下标已经走到了最后的时候，栈顶元素不等于outch的是说明不合法

Stack.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<string.h>
typedef int DataType;
#define Max_Size 100
typedef struct Stack
{
	DataType arry[Max_Size];
	int top;
}Stack;
void StackInit(Stack*Pstack)
{
	assert(Pstack != NULL);
	Pstack->top = 0;
}
void DestoryStack(Stack*Pstack)
{
	assert(Pstack != NULL);
	Pstack->top = 0;
}
void StackPush(Stack*Pstack,DataType data)
{
	assert(Pstack != NULL);
	Pstack->arry[Pstack->top++] = data;
}
void StackPop(Stack*Pstack)
{
	assert(Pstack != NULL);
	assert(Pstack->top > 0);
	Pstack->top--;
}
DataType StackTop(Stack*Pstack)
{
	assert(Pstack != NULL);
	return Pstack->arry[Pstack->top - 1];
}
int StackIsEmpty(Stack*Pstack)
{
	assert(Pstack != NULL);
	return Pstack->top == 0 ? 1 : 0;
}

#pragma once
#include"Stack.h"
#include<string.h>
int IsQrderValid(char in[],int sizein,char out[],int sizeout)
{
	int i = 0;
	int j = 0;
	Stack stack;
	if (sizein != sizeout)
		return 0;
	if (sizein == 0)
	{
		return 1;
	}
	StackInit(&stack);
	char outch;
	char inch;
	j = 0;
	for (i = 0; i < sizeout; i++)
	{
		outch = out[i];
		
		if (StackIsEmpty(&stack) || StackTop(&stack) != outch)//当栈为空或者栈里面的栈顶元素和出栈序列的元素不一样的是时候，要一直压栈，直到栈顶元素和出栈序列相等
		{
			for (; j < sizein; j++)
			{
				inch = in[j];
				StackPush(&stack, inch);
				if (out[i] == in[j])
				{
					j++;
					break;
				}
			}
		}
			if (j == sizein)//当入栈序列走到最后的时候，并且栈顶元素和出栈序列元素不相等，说明出栈序列不正确
			{
				if (outch != StackTop(&stack))
				{
					return 0;
				}
			}
			StackPop(&stack);
		}
	return 1;
}

测试用例：

void IsOrderValidTest()
{
	char *in = "abcdefg";
	char *out = "decfbga";
	printf("%s 是否合法: %s\n", out,
		IsQrderValid(in, strlen(in), out, strlen(out)) ? "合法" : "不合法");
	out = "fegdacb";
	printf("%s 是否合法: %s\n", out,
		IsQrderValid(in, strlen(in), out, strlen(out)) ? "合法" : "不合法");
	out = "efdgbca";
	printf("%s 是否合法: %s\n", out,
		IsQrderValid(in, strlen(in), out, strlen(out)) ? "合法" : "不合法");
	out = "cdbefag";
	printf("%s 是否合法: %s\n", out,
		IsQrderValid(in, strlen(in), out, strlen(out)) ? "合法" : "不合法");
	
}

5.实现一个共享栈

思路：

分为两个栈一个从头开始，一个从尾部开始
扩容的时候分开拷，注意栈1和栈2从哪里开始拷，拷多少个元素过去，很关键
压栈和出栈以及求栈顶元素的时候，分别对栈1和栈2操作就可以了

原理图：

栈和队列面试题

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<string.h>
#define CAPACITY 4
typedef struct ShareStack
{
	int *arry;
	int capacity;
	int top1;
	int top2;
}ShareStack;
void ShareStackInit(ShareStack*SPstack)
{
	assert(SPstack != NULL);
	SPstack->arry = (int*)malloc(sizeof(int)*CAPACITY);
	SPstack->capacity = CAPACITY;
	SPstack->top1 = 0;
	SPstack->top2 = SPstack->capacity - 1;
}
void ShareStackDestory(ShareStack*SPstack)
{
	assert(SPstack != NULL);
	free(SPstack->arry);
	SPstack->capacity = 0;
	SPstack->top1 = 0;
	SPstack->top2 = 0;
}

void ExpendIfRequired(ShareStack*SPstack)//判断是否需要扩容
{
	assert(SPstack != NULL);
	if (SPstack->top1!=SPstack->top2+1)//当top1不等于top2加1的时候说明栈已满
	{
		return;
	}
	int OldCapacity = SPstack->capacity;
	SPstack->capacity *= 2;
	int*Newarry = (int*)malloc(sizeof(int)*SPstack->capacity);//扩容之后将原来的共享栈里面的内容拷贝过去 
	memcpy(Newarry, SPstack->arry, sizeof(int)*SPstack->top1);
	int Stack2size = (OldCapacity - 1) - SPstack->top2;
	memcpy(Newarry+SPstack->capacity-Stack2size, SPstack->arry+SPstack->top1, sizeof(int)*Stack2size);//因为共享栈的容量变了所以拷贝栈2里面的内容要拷贝到从扩容后的栈的容量减一处

	SPstack->top2 += OldCapacity;//拷贝完，因为共享栈的容量变了所以top2要更新
	free(SPstack->arry);
	SPstack->arry = Newarry;
}


void ShareStackPush(ShareStack*SPstack,int data,int which)//往共享栈里面压数据
{
	assert(SPstack != NULL);
	assert(which == 1 || which == 2);
	ExpendIfRequired(SPstack);
	if (which == 1)
	{
		SPstack->arry[SPstack->top1++] = data;
	}
	else
	{
		SPstack->arry[SPstack->top2--] = data;//注意往栈2压的时候top2要--
	}
}
void ShareStackPop(ShareStack*SPstack, int which)
{
	assert(SPstack != NULL);
	assert(which == 1 || which == 2);
	if (which == 1)
	{
		assert(SPstack->top1 > 0);
		SPstack->top1--;
	}
	else
	{
		assert(SPstack->top2 < SPstack->capacity - 1);
		SPstack->top2++;//这里栈2里面的内容出栈后，top2要++
	}
}
int ShareStackTop(ShareStack*SPstack, int which)//返回栈顶元素
{
	assert(SPstack != NULL);
	assert(which == 1 || which == 2);
	if (which == 1)
	{
		assert(SPstack->top1>0);
		return SPstack->arry[SPstack->top1 - 1];
	}
	else
	{
		assert(SPstack->top2 < SPstack->capacity - 1);
		return SPstack->arry[SPstack->top2 + 1];
	}
}

测试用例：

void ShareStackTest1()
{
	ShareStack Stack;
	ShareStackInit(&Stack);
	ShareStackPush(&Stack, 1, 1);
	ShareStackPush(&Stack, 2, 1);
	ShareStackPush(&Stack, 3, 1);
	ShareStackPush(&Stack, 4, 1);
	ShareStackPush(&Stack, 5, 1);
	ShareStackPush(&Stack, 10, 2);
	ShareStackPush(&Stack, 11, 2);
	ShareStackPush(&Stack, 12, 2);
	ShareStackPush(&Stack, 13, 2);
	ShareStackPush(&Stack, 14, 2);
	ShareStackPush(&Stack, 15, 2);
	int i = 0;
	for (i = 0; i < 5; i++)
	{
		printf("The top data of first-stack is:%d\n", ShareStackTop(&Stack, 1));
		ShareStackPop(&Stack, 1);
	}
	for (i = 0; i < 6; i++)
	{
		printf("The top data of sencond-stack is:%d\n", ShareStackTop(&Stack, 2));
		ShareStackPop(&Stack, 2);
	}
}

方法2：

第二种方法是奇偶栈，一个栈为数组下标为奇数的元素，另外一个为下标为偶数的元素，我觉得这个方法相较于第一种方法来说简单，特别是在扩容后要将原来栈里面的元素拷贝到扩容后的栈里面的时候。

思路：

将数组分为两个栈，一个是下标为偶数的偶数栈，一个是下标为奇数的奇数栈
扩容的时候，将数据拷贝到新空间的时候相较于第一种方法来说更为简单
压栈和出栈以及求栈顶元素的时候，分别对奇数栈和偶数栈操作就可以了

原理图：

栈和队列面试题

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<string.h>
#define CAPACITY 4
typedef struct ShareStack
{
	int *arry;
	int top1;
	int top2;
	int capacity;
}ShareStack;
void ShareStackInit(ShareStack*SPstack)
{
	assert(SPstack != NULL);
	SPstack->arry = (int*)malloc(sizeof(int)*CAPACITY);
	SPstack->capacity = CAPACITY;
	SPstack->top1 = 0;//偶数栈
	SPstack->top2 = 1;//奇数栈
}
void ExpendIfRequired(ShareStack*SPstack)
{
	assert(SPstack != NULL);
	if (SPstack->top1 != SPstack->top2 + 1)
	{
		return;
	}
	int OldCapacity = SPstack->capacity;
	SPstack->capacity *= 2;
	int*Newarry = (int*)malloc(sizeof(int)*SPstack->capacity);
	memcpy(Newarry, SPstack->arry, sizeof(int)*SPstack->top2);//将旧的空间的数据挪到新的空间去
	free(SPstack->arry);
	SPstack->arry = Newarry;
}
void ShareStackPush(ShareStack*SPstack, int data, int which)
{
	assert(SPstack != NULL);
	assert(which == 1 || which == 2);
	ExpendIfRequired(SPstack);
	if (which == 1)
	{
		SPstack->arry[SPstack->top1+2] = data;//这里往栈里面压数据之后top要加2
	}
	else
	{
		SPstack->arry[SPstack->top2+2] = data;
	}
}
void ShareStackPop(ShareStack*SPstack, int which)
{
	assert(SPstack != NULL);
	assert(which == 1 || which == 2);
	assert(SPstack->top2 < SPstack->capacity - 1);
	if (which == 1)
	{
		SPstack->top1-=2;//从站里面pop数据之后top-2
	}
	else
	{
		SPstack->top2-=2;
	}
}
int ShareStackTop(ShareStack*SPstack, int which)
{
	assert(SPstack != NULL);
	assert(which == 1 || which == 2);
	assert(SPstack->top2 < SPstack->capacity - 1);

	if (which == 1)
	{
		return SPstack->arry[SPstack->top1 - 2];//返回栈顶元素的时候要减2
	}
	else
	{
		return SPstack->arry[SPstack->top2 - 2];
	}
}

测试用例：

void ShareStackTest2()
{
	ShareStack Stack;
	ShareStackInit(&Stack);
	ShareStackPush(&Stack, 1, 1);
	ShareStackPush(&Stack, 2, 1);
	ShareStackPush(&Stack, 3, 1);
	ShareStackPush(&Stack, 4, 1);
	ShareStackPush(&Stack, 5, 1);
	ShareStackPush(&Stack, 10, 2);
	ShareStackPush(&Stack, 11, 2);
	ShareStackPush(&Stack, 12, 2);
	ShareStackPush(&Stack, 13, 2);
	ShareStackPush(&Stack, 14, 2);
	ShareStackPush(&Stack, 15, 2);
	int i = 0;
	for (i = 0; i < 5; i++)
	{
		printf("The top data of first-stack is:%d\n", ShareStackTop(&Stack, 1));
		ShareStackPop(&Stack, 1);
	}
	for (i = 0; i < 6; i++)
	{
		printf("The top data of sencond-stack is:%d\n", ShareStackTop(&Stack, 2));
		ShareStackPop(&Stack, 2);
	}
}

相关标签：用两个栈实现一个共享栈根据入栈序列判断出栈序列是否合格两个栈实现一个队列返回栈中的最小值

上一篇： Weka连接MySQL数据库及连接失败问题解决

下一篇：三国周宣人物生平简介，周宣相梦真有那么准吗？

栈和队列面试题

leetcode-225用队列实现栈

LeetCode_225 用队列实现栈

LeetCode-225 用队列实现栈

LeetCode_225. 用队列实现栈

队列实现栈 | 栈实现队列

【面试】一道关于变量提升和运算符的前端面试题

PHP的面试题集,附我的答案和分析（一）

数据结构 - 栈的实现和应用

PHP队列服务HTTPSQS的安装和使用实例

用两个栈实现队列(Python)