0225-用队列实现栈

用队列实现栈

方案一

这种方法的原理就是每次把新加入的数插到前头，这样队列保存的顺序和栈的顺序是相反的，它们的取出方式也是反的，那么反反得正，就是我们需要的顺序了。我们需要一个辅助队列tmp，把s的元素也逆着顺序存入tmp中，此时加入新元素x，再把tmp中的元素存回来，这样就是我们要的顺序了，其他三个操作也就直接调用队列的操作即可

C-源代码

typedef int LinkQueueData;

//节点
typedef struct link_queue_node {
    LinkQueueData data;
    struct link_queue_node *next;
}LinkQueueNode;

typedef struct link_queue {
    LinkQueueNode *head;//队头
    LinkQueueNode *tail;//队尾
    int count;//队大小
}LinkQueue;


LinkQueue *linkQueueCreate() {
    LinkQueue *queue = NULL;
    
    queue = (LinkQueue *)malloc(sizeof(LinkQueue));
    if (queue == NULL) {
        return NULL;
    }
    
    queue->head = NULL;
    queue->tail = NULL;
    queue->count = 0;
    
    return queue;
}

bool linkQueueIsEmpty(LinkQueue *queue) {
    return queue->count == 0;
}

int linkQueueEnqueue(LinkQueue *queue, LinkQueueData data) {
    if (queue == NULL) {
        return -1;
    }
    
    LinkQueueNode *p = NULL;
    
    p = (LinkQueueNode *)malloc(sizeof(LinkQueueNode));
    if (p == NULL) {
        return -1;
    }
    
    p->data = data;
    p->next = NULL;
    if (queue->head == NULL) {
        queue->head = p;
    }
    else {
        queue->tail->next = p;
    }
    queue->tail = p;
    queue->count++;
    
    return 0;
}

int linkQueueDequeue(LinkQueue *queue, LinkQueueData *data) {
    if (queue == NULL || linkQueueIsEmpty(queue)) {
        return -1;
    }
    
    *data = queue->head->data;
    
    LinkQueueNode *p = queue->head;
    p = queue->head;
    queue->head = queue->head->next;
    queue->count--;
    
    if (queue->head == NULL) {
        queue->tail = NULL;
    }
    
    free(p);
    
    return 0;
}

void linkQueueDestory(LinkQueue *queue) {
    
    if (queue != NULL && !linkQueueIsEmpty(queue)) {
        
        LinkQueueData data;
        while (!linkQueueIsEmpty(queue)) {
            int ret = linkQueueDequeue(queue, &data);
            if (ret != 0) {
                printf("delete failure\n");
            }
        }
        
        free(queue);
    }
    
}


typedef struct {
    
    LinkQueue *q;
} MyStack;

/** Initialize your data structure here. */
MyStack* myStackCreate(int maxSize) {
    
    MyStack *stack = (MyStack *)malloc(sizeof(MyStack));
    stack->q = linkQueueCreate();
    
    return stack;
}

/** Push element x onto stack. */
void myStackPush(MyStack* obj, int x) {
    
    LinkQueue *queue = linkQueueCreate();
    
    while(!linkQueueIsEmpty(obj->q)) {
        
        linkQueueEnqueue(queue, obj->q->head->data);
        
        int data = 0;
        linkQueueDequeue(obj->q, &data);
    }
    
    linkQueueEnqueue(obj->q, x);
    
    while(!linkQueueIsEmpty(queue)) {
        
        linkQueueEnqueue(obj->q, queue->head->data);
        
        int data = 0;
        linkQueueDequeue(queue, &data);
    }
    
    free(queue);
}

/** Removes the element on top of the stack and returns that element. */
int myStackPop(MyStack* obj) {
    
    int data;
    linkQueueDequeue(obj->q, &data);
    
    return data;
}

/** Get the top element. */
int myStackTop(MyStack* obj) {
    
    return obj->q->head->data;
}

/** Returns whether the stack is empty. */
bool myStackEmpty(MyStack* obj) {
    
    return linkQueueIsEmpty(obj->q);
}

void myStackFree(MyStack* obj) {
    
    linkQueueDestory(obj->q);
    
    free(obj);
}

void test_0225(void) {
    MyStack *stack = myStackCreate(5);
    myStackPush(stack, 1);
    myStackPush(stack, 2);
    myStackPush(stack, 3);
    myStackPush(stack, 4);
    
    while (!myStackEmpty(stack)) {
        int data = myStackPop(stack);
        printf("%d\n", data);
    }
}

参考Grandyang