スタックとキューの面接問題(C言語版)

1.出入桟の正当性の判断
https://blog.csdn.net/Payshent/article/details/69951411
2.2つのスタックを使用して1つのキューを実現
思想:1.スタック1内のすべてのデータはスタック2に弾き出される(スタック2は空のスタックである)
           2.スタック2からすべてのデータをポップアップすると、キューの効果が得られます.
(デフォルトの圧送データはキュー1に圧送され、キュー2からデータが出力される)

typedef struct Stack
{
	DataType _array[MAX_SIZE];          //  
	DataType top;			    //  
	int size;			    //  
}Stack;
void StackInit(Stack* p)
{
	p->size = 0;
	p->top = -1;
}

void StackPush(Stack* p,DataType x)
{
	if (p->size < MAX_SIZE)
	{
		p->_array[++p->top] = x;
		p->size++;
	}
	else
	{
		printf("  
");
	}
}
DataType StackPop(Stack* p)
{
	assert(p);
	p->top--;
	p->size--;
	return p->_array[p->top + 1];
}

void test1(Stack* s,Stack* s1)
{
	if (StackEmpty(s1) == 0)                          //  s1    
	{
		while (s->top >= 0)
		{
			s1->_array[++s1->top] = StackPop(s);        //s      ，  s1 
			s1->size++;
		}
		while (s1->top >= 0)
		{
			printf("%d ", s1->_array[s1->top--]);         // s1    
		}
		printf("
");
	}
	else
	{
		printf("%d ", s1->_array[s1->top--]);
	}
}

3.2つのキューを使用して1つのスタックを実装
思想:1.まずキュー1の要素をキュー2に押し込み、キュー1に要素が1つしか残っていないので、残りの要素をポップアップします.
           2.さらにキュー2の要素をキュー1に押し込み、最後の要素を残してポップアップ
           3.キュー1に要素がないまで、上記の手順を繰り返します.
(途中で要素を押し込む必要がある場合は、空でないキューに押し込みます)

typedef struct QueueNode
{
	DataType data;
	struct QueueNode* _next;
}QueueNode;
typedef	struct Queue
{
	QueueNode* _head;
	QueueNode* _tail;
}Queue;

Queue.c
void QueueInit(Queue* p)
{
	p->_head = p->_tail = NULL;
}

QueueNode* BuyNode(DataType x)
{
	QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode));
	assert(newNode);
	newNode->data = x;
	newNode->_next = NULL;
	return newNode;
}
void QueuePush(Queue* p, DataType x)
{
	if (p->_head == NULL)
		p->_head = p->_tail = BuyNode(x);
	else
	{
		p->_tail->_next = BuyNode(x);
		p->_tail = p->_tail->_next;
	}
}
QueueNode* QueuePop(Queue* p)
{
	assert(p);
	QueueNode* flag = p->_head;
	p->_head = p->_head->_next;
	return flag;
}
void QueueDestory(Queue* p)
{
	while (p->_head)
	{
		QueueNode* del = p->_head;
		p->_head = p->_head->_next;
		free(del);
	}
}
void test1(Queue* p, Queue* p1)
{
	while (p->_head)
	{
		while (p->_head != p->_tail)                 //     
		{
			QueuePush(p1, QueuePop(p)->data);      //          p1
		}
		printf("%d ", QueuePop(p)->data);
		while (p1->_head)
		{
			QueuePush(p, QueuePop(p1)->data);       // p1        p
		}
	}
	printf("
");
}

4.1つの配列で2つのスタックを実現
https://blog.csdn.net/zw_1510/article/details/51644230

void ShareStacktest3()                  //       
{
	DataType arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
	Stack s1;
	Stack s2;
	int i = 0;
	int j = sizeof(arr) / sizeof(arr[0]) - 1;
	int capacity = j + 1;
	StackInit(&s1);
	StackInit(&s2);
	while (s1.size < 2)
	{
		if (s1.size < MAX_SIZE)
		{
			StackPush(&s1, arr[i]);
			i++;
		}
		else
		{
			printf(" 1 
");
			break;
		}
	}
	Print(&s1);
	printf("
");
	while (s2.size < 7)
	{
		if (s2.size < MAX_SIZE)
		{
			StackPush(&s2, arr[j]);
			j--;
		}
		else
		{
			printf(" 2 :
");
			break;
		}
	}
	Print(&s2);
	printf("
");
}