| 【数据结构】用栈实现队列（c语言） | 您所在的位置：网站首页 › 队列数组实现C语言 › 【数据结构】用栈实现队列（c语言） |
【数据结构】用栈实现队列（c语言）
|
使用栈实现队列的下列操作： push(x) -- 将一个元素放入队列的尾部。pop() -- 从队列首部移除元素。peek() -- 返回队列首部的元素。empty() -- 返回队列是否为空。示例: MyQueue queue = new MyQueue(); queue.push(1); queue.push(2); queue.peek(); // 返回 1 queue.pop(); // 返回 1 queue.empty(); // 返回 false分析：这道题要用栈实现队列，一个栈是肯定不行的，因为栈是先进后出，而队列是先进先出，所以这里要想用栈实现队列，就要开辟两个不通过的栈，一个用来入数据，一个用来出数据，来回倒一圈就可以实现队列：
需要说明的是，因为目前还没有学习c++，所以写代码时就得先实现一下栈的接口，再进行后续操作。 具体实现代码如下： typedef int STDataType; typedef struct Stack { STDataType* _a; int _top;//栈顶 int _capacity; }Stack; void StackInit(Stack* ps, int n) { assert(ps); ps->_a = (STDataType*)malloc(sizeof(STDataType)*n); ps->_top = 0; ps->_capacity = n; } void StackDestroy(Stack* ps) { assert(ps); free(ps->_a); ps->_a=NULL; ps->_top = ps->_capacity=0; } void StackPush(Stack* ps, STDataType x)//在栈顶入数据 { assert(ps); if (ps->_top == ps->_capacity)//容量检测 { ps->_a = (STDataType*)realloc(ps->_a, ps->_capacity * 2 * sizeof(STDataType)); ps->_capacity *= 2; } ps->_a[ps->_top] = x; ps->_top++; } void StackPop(Stack* ps)//在栈顶出数据 { assert(ps); if (ps->_top > 0) { ps->_top--; } } STDataType StackTop(Stack* ps)//取出栈顶的数据 { assert(ps); return ps->_a[ps->_top - 1]; } int StackSize(Stack* ps)//返回数据个数 { assert(ps); return ps->_top;//top其实就是链表中的size } int StackEmpty(Stack* ps) { assert(ps); if (ps->_top == 0) { return 0; } else { return 1; } //return ps->_top == 0 ? 0 : 1; } typedef struct { Stack pushST; Stack popST; } MyQueue; /** Initialize your data structure here. */ MyQueue* myQueueCreate(int maxSize) { MyQueue* pqueue=(MyQueue*)malloc(sizeof(MyQueue)); StackInit(&pqueue->pushST,maxSize); StackInit(&pqueue->popST,maxSize); return pqueue; } /** Push element x to the back of queue. */ void myQueuePush(MyQueue* obj, int x) { StackPush(&obj->pushST,x); } /** Removes the element from in front of queue and returns that element. */ int myQueuePop(MyQueue* obj) { if(StackEmpty(&obj->popST)==0) { while(StackEmpty(&obj->pushST)!=0) { StackPush(&obj->popST,StackTop(&obj->pushST)); StackPop(&obj->pushST); } } int front=StackTop(&obj->popST); StackPop(&obj->popST); return front; } /** Get the front element. */ int myQueuePeek(MyQueue* obj) { if(StackEmpty(&obj->popST)==0) { while(StackEmpty(&obj->pushST)!=0) { StackPush(&obj->popST,StackTop(&obj->pushST)); StackPop(&obj->pushST); } } return StackTop(&obj->popST); } /** Returns whether the queue is empty. */ bool myQueueEmpty(MyQueue* obj) { if(StackEmpty(&obj->pushST)==0&&StackEmpty(&obj->popST)==0) { return true; } else { return false; } } void myQueueFree(MyQueue* obj) { StackDestroy(&obj->pushST); StackDestroy(&obj->popST); free(obj); } /** * Your MyQueue struct will be instantiated and called as such: * struct MyQueue* obj = myQueueCreate(maxSize); * myQueuePush(obj, x); * int param_2 = myQueuePop(obj); * int param_3 = myQueuePeek(obj); * bool param_4 = myQueueEmpty(obj); * myQueueFree(obj); */
|
【本文地址】
公司简介
联系我们