用队列实现栈
方案一
这种方法的原理就是每次把新加入的数插到前头，这样队列保存的顺序和栈的顺序是相反的，它们的取出方式也是反的，那么反反得正，就是我们需要的顺序了。我们需要一个辅助队列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);
}
}
