基于C语言链表，用两个栈实现队列

要求：
    有两个栈A和B，实现队列C。
实现思想：
    向队列C中压入数据等同于向栈A压栈，从队列C中弹出数据等同于从栈B中弹出数据。

    向A压栈时，判断A是否满栈以及B是否为空栈。如果A满B空，则将A中的所有数据弹出后压入B中，然后再向A压入数据；如果A满B非空，则不能像A中压入数据。
    从B弹栈时，判断A和B是否都为空，如果是，则队列为空；否则，判断B是否为空，若B非空，则从B弹栈；若B为空，则将A中的所有数据弹出后压入B中，然后从B弹栈；

PS： 不少函数使用的是void类型，没关注其返回值，可根据需要加入异常处理。多线程对队列C做写操作时，需要加锁。

// stack.c

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include "stack.h"

static void stack_AddHead(STACK_HEAD_S *pstHead, STACK_NODE_S *pstAddNode)
{
    pstAddNode->pstNext = pstHead->pstNext;
    pstHead->pstNext = pstAddNode;

    return;
}

/* 压栈 */
void stack_push(STACK_HEAD_S *pstHead, int iData)
{
    STACK_NODE_S *pstNode;

    if (NULL == pstHead || pstHead->iStackDeep > STACK_DEEP_MAX)
    {
        return;
    }

    pstNode = (STACK_NODE_S *)malloc(sizeof(STACK_NODE_S));
    if (NULL != pstNode)
    {
        memset(pstNode, 0, sizeof(*pstNode));
        pstNode->iData = iData;
        stack_AddHead(pstHead, pstNode);
        pstHead->iStackDeep++;
    }

    return;
}

/* 弹栈 */
int stack_popd(STACK_HEAD_S *pstHead)
{
    STACK_NODE_S *pstNode;
    int iData;

    if (NULL == pstHead || NULL == pstHead->pstNext)
    {
        return;
    }

    pstNode = pstHead->pstNext;
    pstHead->pstNext = pstHead->pstNext->pstNext;
    iData = pstNode->iData;
    free(pstNode);
    pstHead->iStackDeep--;

    return iData;
}

/* 获取栈深度 */
int stack_deep(STACK_HEAD_S *pstHead)
{
    int iStackDeep = -1;

    if (NULL != pstHead)
    {
        iStackDeep = pstHead->iStackDeep;
    }

    return iStackDeep;
}

int stack_empty(STACK_HEAD_S *pstHead)
{
    int iIsStackEmpty = 0;

    if (NULL == pstHead || 0 == pstHead->iStackDeep)
    {
        iIsStackEmpty = 1;
    }

    return iIsStackEmpty;
}

int stack_full(STACK_HEAD_S *pstHead)
{
    int iIsStackFull = 0;

    if (NULL != pstHead && STACK_DEEP_MAX == pstHead->iStackDeep)
    {
        iIsStackFull = 1;
    }

    return iIsStackFull;
}

// stack.h

#ifndef __STACK_H__
#define __STACK_H__

#define STACK_DEEP_MAX 256U

typedef struct tagStackNode{
    struct tagStackNode *pstNext;
    int iData;
} STACK_NODE_S;

typedef struct tagStackHead{
    STACK_NODE_S *pstNext;
    int iStackDeep;
} STACK_HEAD_S;


void stack_push(STACK_HEAD_S *pstHead, int iData);
int stack_popd(STACK_HEAD_S *pstHead);
int stack_deep(STACK_HEAD_S *pstHead);
int stack_empty(STACK_HEAD_S *pstHead);
int stack_full(STACK_HEAD_S *pstHead);

#endif

// queue_by_stack.c

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include "stack.h"

STACK_HEAD_S g_stHeadA;
STACK_HEAD_S g_stHeadB;

static int queue_IsAbleToPush(void)
{
    int iIsStackFull;
    int iIsStackEmpty;
    int iIsAble = 1;

    iIsStackFull = stack_full(&g_stHeadA);
    iIsStackEmpty = stack_empty(&g_stHeadB);
    if (1 == iIsStackFull && 0 == iIsStackEmpty)
    {
        iIsAble = 0;
    }

    return iIsAble;
}

int queue_empty(void)
{
    int iIsStackEmpty;

    iIsStackEmpty = stack_empty(&g_stHeadA);
    iIsStackEmpty &= stack_empty(&g_stHeadB);

    return iIsStackEmpty;
}

static void queue_PushStackAToStackB(void)
{
    int iStackDeep, iLoop, iData;

    iStackDeep = stack_deep(&g_stHeadA);
    for (iLoop = 0; iLoop < iStackDeep; iLoop++)
    {
        iData = stack_popd(&g_stHeadA);
        stack_push(&g_stHeadB, iData);
    }

    return;
}

void queue_push(int iData)
{
    int iIsAble;
    int iIsStackFull;

    iIsAble = queue_IsAbleToPush();
    if (0 == iIsAble)
    {
        return;
    }

    iIsStackFull = stack_full(&g_stHeadA);
    if (1 == iIsStackFull)
    {
        queue_PushStackAToStackB();
    }
    stack_push(&g_stHeadA, iData);

    return;
}

int queue_popd(void)
{
    int iIsQueueEmpty;
    int iIsStackEmpty;
    int iData;

    iIsQueueEmpty = queue_empty();
    if (1 == iIsQueueEmpty)
    {
        return -1;
    }

    iIsStackEmpty = stack_empty(&g_stHeadB);
    if (0 == iIsStackEmpty)
    {
        iData = stack_popd(&g_stHeadB);
    }
    else
    {
        queue_PushStackAToStackB();
        iData = stack_popd(&g_stHeadB);
    }

    return iData;
}

int queue_length(void)
{
    int iIsQueueEmpty;
    int iLength = -1;

    iIsQueueEmpty = queue_empty();
    if (0 == iIsQueueEmpty)
    {
        iLength = stack_deep(&g_stHeadB);
        iLength += stack_deep(&g_stHeadA);
    }

    return iLength;
}

void queue_test(void)
{
    int iLoop, iQueueLen, iData;
    int iFlag = 0;

    for (iLoop = 0; iLoop < 2 * STACK_DEEP_MAX; iLoop++)
    {
        queue_push(iLoop);
    }

    iQueueLen = queue_length();
    for (iLoop = 0; iLoop < iQueueLen; iLoop++)
    {
        iData = queue_popd();
        printf("%d\t", iData);
        iFlag++;
        if (0 == iFlag % 8)
        {
            printf("\n");
        }
    }
    printf("\n");

    return;
}

void main(void)
{
    queue_test();

    return;
}