做明星同款的网站,百度网站排名,江苏省建设信息网,wordpress 插件 免费用队列实现栈
OJ链接 请你仅使用两个队列实现一个后入先出#xff08;LIFO#xff09;的栈#xff0c;并支持普通栈的全部四种操作#xff08;push、top、pop 和 empty#xff09;。 实现 MyStack 类#xff1a; void push(int x) 将元素 x 压入栈顶。int pop() 移除并返…用队列实现栈
OJ链接 请你仅使用两个队列实现一个后入先出LIFO的栈并支持普通栈的全部四种操作push、top、pop 和 empty。 实现 MyStack 类 void push(int x) 将元素 x 压入栈顶。int pop() 移除并返回栈顶元素。int top() 返回栈顶元素。boolean empty() 如果栈是空的返回 true 否则返回 false 。 队列先进先出后进后出
栈先进后出后进先出 思路一个队列存数据另一个队列用来出数据时导数据 用单链表实现队列 代码
#includestdio.h
#includeassert.h
#includestdlib.h
#includestdbool.htypedef int QDataType;//创建队列节点
typedef struct QueueNode
{QDataType val;struct QueueNode* next;
}QNode;//创建维护队列的指针
typedef struct Queue
{QNode* phead;QNode* ptail;int size;//原本是需要遍历的写在结构体里可以很好的是时间复杂度由O(N)变为O(1)
}Queue;//初始化
void QueueInit(Queue* pq);//空间释放
void QueueDestroy(Queue* pq);//尾插
void QueuePush(Queue* pq, QDataType x);//头删
void QueuePop(Queue* pq);//取队头的数据
QDataType QueueFront(Queue* pq);//取队尾的数据
QDataType QueueBack(Queue* pq);//判断是否为空
bool QueueEmpty(Queue* pq);//队列元素个数
int QueueSize(Queue* pq);void QueueInit(Queue* pq)
{assert(pq);pq-phead pq-ptail NULL;pq-size 0;
}void QueueDestroy(Queue* pq)
{assert(pq);QNode* cur pq-phead;while (cur){QNode* next cur-next;free(cur);cur next;}pq-phead pq-ptail NULL;pq-size 0;
}void QueuePush(Queue* pq, QDataType x)
{assert(pq);QNode* newnode (QNode*)malloc(sizeof(QNode));if (newnode NULL){perror(malloc fail);return;}newnode-val x;newnode-next NULL;if (pq-ptail NULL){pq-ptail pq-phead newnode;}else{pq-ptail-next newnode;pq-ptail newnode;}pq-size;
}void QueuePop(Queue* pq)
{assert(pq);// assert(pq-phead);QNode* del pq-phead;pq-phead pq-phead-next;free(del);del NULL;if (pq-phead NULL)pq-ptail NULL;pq-size--;
}QDataType QueueFront(Queue* pq)
{assert(pq);// assert(pq-phead);return pq-phead-val;
}QDataType QueueBack(Queue* pq)
{assert(pq); assert(pq-ptail);return pq-ptail-val;
}bool QueueEmpty(Queue* pq)
{assert(pq);return pq-phead NULL;
}int QueueSize(Queue* pq)
{assert(pq);return pq-size;
}
声明栈MyStack
//匿名结构体
typedef struct {Queue q1;Queue q2;
} MyStack;//结构体类型
//如果不加typedefMyStack就是结构体变量
创建初始化栈myStackCreate
//初始化
MyStack* myStackCreate() {//MyStack mystack;出了作用域就销毁了MyStack* pst(MyStack*)malloc(sizeof(MyStack));QueueInit(pst-q1);QueueInit(pst-q2);return pst;
}
压栈myStackPush
哪个队列不为空就往哪个队列里面插入
//插入元素
void myStackPush(MyStack* obj, int x) {assert(obj);//找不为NULL的队列依次插入if(!QueueEmpty(obj-q1)){QueuePush(obj-q1, x);//尾插}else{QueuePush(obj-q2, x);}
}
出栈并返回栈顶元素myStackPop
这里有一个问题如何知道q1和q2谁为空谁不为空
首先用假设法假设其中一个队列是空另一个队列不是空然后进行验证。如果验证第一个队列不是空就交换位置。然后就开始找栈顶元素。先将非空队列里的元素一个一个导入到空队列记得Pop直到非空队列里只剩下一个元素的时候停止。这个元素就是栈顶元素然后返回它。最后不要忘记Pop一下。
//出栈
int myStackPop(MyStack* obj) {assert(obj);//判断为空/非空------假设法Queue*nonemptyobj-q1;Queue*emptyobj-q2;if(QueueEmpty(obj-q1))//{nonemptyobj-q2;emptyobj-q1;//创建}//直到队列里只剩下一个元素剩下的这个元素就是我们要找的栈顶元素while(QueueSize(nonempty)1)//队列里面的元素个数 1{QueuePush(empty, QueueFront(nonempty));//把队头的元素一个一个放到空队列QueuePop(nonempty);//把刚放的那个元素从原队列删除}int topQueueFront(nonempty);//队列尾的元素——栈顶元素QueuePop(nonempty);return top;
}
返回栈顶元素myStackTop
我们要能够发现栈顶的元素也就是队尾的元素。所以我们直接返回队尾元素就可以了。
//栈顶元素
int myStackTop(MyStack* obj) {if(!QueueEmpty(obj-q1)) {return QueueBack(obj-q1);}else{return QueueBack(obj-q2);}
}
判断栈是否为空myStackEmpty
//判断是否为空
bool myStackEmpty(MyStack* obj) {return QueueEmpty(obj-q1) QueueEmpty(obj-q2);//
}
释放空间myStackFree
//释放空间
void myStackFree(MyStack* obj) {QueueDestroy(obj-q1);QueueDestroy(obj-q2);free(obj);objNULL;
}
总代码
//匿名结构体
typedef struct {Queue q1;Queue q2;
} MyStack;//结构体类型
//如果不加typedefMyStack就是结构体变量//初始化
MyStack* myStackCreate() {//MyStack mystack;出了作用域就销毁了MyStack* pst(MyStack*)malloc(sizeof(MyStack));QueueInit(pst-q1);QueueInit(pst-q2);return pst;
}//插入元素
void myStackPush(MyStack* obj, int x) {assert(obj);//找不为NULL的队列依次插入if(!QueueEmpty(obj-q1)){QueuePush(obj-q1, x);//尾插}else{QueuePush(obj-q2, x);}
}//出栈
int myStackPop(MyStack* obj) {assert(obj);//判断为空/非空------假设法Queue*nonemptyobj-q1;Queue*emptyobj-q2;if(QueueEmpty(obj-q1))//{nonemptyobj-q2;emptyobj-q1;//创建}//直到队列里只剩下一个元素剩下的这个元素就是我们要找的栈顶元素while(QueueSize(nonempty)1)//队列里面的元素个数 1{QueuePush(empty, QueueFront(nonempty));//把队头的元素一个一个放到空队列QueuePop(nonempty);//把刚放的那个元素从原队列删除}int topQueueFront(nonempty);//队列尾的元素——栈顶元素QueuePop(nonempty);return top;
}//栈顶元素
int myStackTop(MyStack* obj) {if(!QueueEmpty(obj-q1)) {return QueueBack(obj-q1);}else{return QueueBack(obj-q2);}
}//判断是否为空
bool myStackEmpty(MyStack* obj) {return QueueEmpty(obj-q1) QueueEmpty(obj-q2);//
}//释放空间
void myStackFree(MyStack* obj) {QueueDestroy(obj-q1);QueueDestroy(obj-q2);free(obj);objNULL;
}
用栈实现队列
OJ链接 请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作push、pop、peek、empty 实现 MyQueue 类 void push(int x) 将元素 x 推到队列的末尾int pop() 从队列的开头移除并返回元素int peek() 返回队列开头的元素boolean empty() 如果队列为空返回 true 否则返回 false 思路 一个栈用于push另一个栈用于pop。当用来出栈的那个栈空了以后入栈的那个栈里面的元素才能导入另一个栈这样就可以很好的实现队列的先进先出原则。
用数组实现栈 代码
#includestdio.h
#includeassert.h
#includestdlib.h
#includestdbool.htypedef int STDatatype;
typedef struct Stack
{STDatatype* a;int top;int capacity;
}ST;void STInit(ST* pst);
void STDestroy(ST* pst);
void STPush(ST* pst, STDatatype x);
void STPop(ST* pst);
STDatatype STTop(ST* pst);
bool STempty(ST* pst);
int STSize(ST* pst);void STInit(ST* pst)
{assert(pst);pst-a 0;pst-top 0;pst-capacity 0;
}void Createcapacity(ST* pst)
{//扩容if (pst-top pst-capacity){int newcapacity pst-capacity 0 ? 4 : 2 * pst-capacity;STDatatype* tmp (STDatatype*)realloc(pst-a, sizeof(STDataType) * newcapacity);if (tmp NULL){perror(realloc fail);return;}pst-a tmp;pst-capacity newcapacity;}
}void STPush(ST* pst, STDatatype x)
{assert(pst);Createcapacity(pst);pst-a[pst-top] x;pst-top;
}void STPop(ST* pst)
{assert(pst);assert(pst-top 0);pst-top--;
}STDatatype STTop(ST* pst)
{assert(pst);assert(pst-top 0);return pst-a[pst-top - 1];
}bool STempty(ST* pst)
{assert(pst);return pst-top 0;//为0就是true 为0就是为flase
}int STSize(ST* pst)
{assert(pst);return pst-top;
}void STDestroy(ST* pst)
{assert(pst);free(pst-a);pst-a NULL;pst-top 0;pst-capacity 0;
}
声明队列MyQueue
typedef struct {ST stpush;ST stpop;
} MyQueue;
创建初始化队列myQueueCreate
创建的临时变量出了作用域就销毁了所以需要malloc才可。
MyQueue* myQueueCreate() {MyQueue*obj(MyQueue*)malloc(sizeof(MyQueue));STInit(obj-stpush);STInit(obj-stpop);return obj;
} 入队列myQueuePush
//入队列
void myQueuePush(MyQueue* obj, int x) {STPush(obj-stpush, x);
}
返回队头元素myQueuePeek
int myQueuePeek(MyQueue* obj) {//当stpop为空的时候if(STempty(obj-stpop)){//当stpush不为空while(!STempty(obj-stpush)){int xSTTop(obj-stpush);STPush(obj-stpop,x);STPop(obj-stpush);}}return STTop(obj-stpop);
}
从队列的开头移除并返回元素myQueuePop
可以直接调用myQueuePeek就会直接把元素都移到stpop我们只管删除就行了。
int myQueuePop(MyQueue* obj) {int firstmyQueuePeek(obj);STPop(obj-stpop);return first;
}
判断队列是否为空myQueueEmpty
bool myQueueEmpty(MyQueue* obj) {return STempty(obj-stpush) STempty(obj-stpop);
} 释放空间myQueueFree
销毁的时候要先销毁队列开辟的空间不然会造成野指针。
void myQueueFree(MyQueue* obj) {STDestroy(obj-stpush);STDestroy(obj-stpop);free(obj);objNULL;
}
总代码
typedef struct {ST stpush;ST stpop;
} MyQueue;MyQueue* myQueueCreate() {MyQueue* obj (MyQueue*)malloc(sizeof(MyQueue));STInit(obj-stpush);STInit(obj-stpop);return obj;
}//入队列
void myQueuePush(MyQueue* obj, int x) {STPush(obj-stpush, x);
}int myQueuePeek(MyQueue* obj) {//当stpop为空的时候if (STempty(obj-stpop)){//当stpush不为空while (!STempty(obj-stpush)){int x STTop(obj-stpush);STPush(obj-stpop, x);STPop(obj-stpush);}}return STTop(obj-stpop);
}int myQueuePop(MyQueue* obj) {int first myQueuePeek(obj);STPop(obj-stpop);return first;
}bool myQueueEmpty(MyQueue* obj) {return STempty(obj-stpush) STempty(obj-stpop);
}void myQueueFree(MyQueue* obj) {STDestroy(obj-stpush);STDestroy(obj-stpop);free(obj);obj NULL;
}
