兰州网站建设兼职,沙洋网页定制,做产品包装的3d网站,网站建设售前怎么做好目录 一、用栈实现队列1.1初始化队列1.2模拟入队列1.3模拟出队列1.4取模拟的队列头元素1.5判断队列是否为空 二、用队列实现栈2.1初始化栈2.2模拟出栈2.3模拟入栈2.4取模拟的栈顶元素2.5判读栈是否为空 一、用栈实现队列
具体题目可以参考LeetCode232. 用栈实现队列 首先要想到… 目录 一、用栈实现队列1.1初始化队列1.2模拟入队列1.3模拟出队列1.4取模拟的队列头元素1.5判断队列是否为空 二、用队列实现栈2.1初始化栈2.2模拟出栈2.3模拟入栈2.4取模拟的栈顶元素2.5判读栈是否为空 一、用栈实现队列
具体题目可以参考LeetCode232. 用栈实现队列 首先要想到的是队列是一种先进先出的结构而栈是一种先进后出的结构。依此我们可以定义两个栈结构来模拟先进先出既然要定义两个栈那么为了方便调用我们可以将这两个栈结构定义在一个结构体中如下
typedef struct {ST st1;//栈1ST st2;//栈2
} MyQueue;实现 MyQueue类
void push(int x)将元素 x推到队列的末尾int pop()从队列的开头移除并返回元素int peek()返回队列开头的元素boolean empty()如果队列为空返回 true否则返回 false。
1.1初始化队列
我们定义的结构体在主函数外部为了让每个函数都能用到那么我们就必须要用malloc来动态开辟空间这样此结构会被保存在静态区每次函数调用时便不会销毁此变量然后再将此结构体中的栈初始化。
MyQueue* myQueueCreate()
{MyQueue* queue (MyQueue*)malloc(sizeof(MyQueue));//动态开辟结构体变量//注意初始化栈的参数为地址StackInit(queue-st1);//初始化栈1StackInit(queue-st2);//初始化栈2return queue;
}1.2模拟入队列
我们可以将栈1作为存数据的栈那么每次入队列操作就是进栈操作StackPush(obj-st1, x);。
void myQueuePush(MyQueue* obj, int x)
{assert(obj);StackPush(obj-st1, x);
}1.3模拟出队列
思路1 如果我们用栈1obj-st1来存放数据在模拟出队列时我们首先要断言栈1不为空那么当栈1不为空且我们需要出队列头元素时。此时就需要栈2obj-st2来暂存数据即我们将栈1除栈底的全部元素都出栈并入栈到栈2obj-st2然后再出栈1最后的元素并返回这样就模拟了先入先出性质。还需要注意的是在返回最后一个元素前还需要再将所有数据从栈2再入到栈1。逻辑如下 思路2 栈1用来存数据栈2用来出数据。 那么为什么栈2的元素可以直接出呢当我们需要模拟出队列时我们可以先将栈1中所以元素出栈并入栈到栈2这样一来栈2中的top就相当于队列头元素。每次从栈2中出元素时要先判断栈2中是否有元素若没有就将栈1中的元素出栈并入栈到栈2中。大致逻辑如下 与思路一相比较思路二栈2无需重新入栈1还可继续模拟出队列。只能说两种思路各有好处下列代码实现使用的是思路一
int myQueuePop(MyQueue* obj)
{assert(obj);assert(StackSize(obj-st1) ! 0);//栈1不为空ST* empty obj-st2;//栈2为空ST* noempty obj-st1;//栈1不为空//将栈1除栈底的所有元素出栈并入栈到栈2while(StackSize(noempty) 1){StackPush(empty,StackTop(noempty));StackPop(noempty);}//找到队头int ret StackTop(noempty);StackPop(noempty);//重新入栈1while(StackSize(empty) 0){StackPush(noempty,StackTop(empty));StackPop(empty);}return ret;
}1.4取模拟的队列头元素
此函数实现与1.3模拟出队列方法相似就不多介绍了如下
int myQueuePeek(MyQueue* obj)
{assert(obj);ST* empty obj-st2;ST* noempty obj-st1;//将栈1除栈底的所有元素出栈并入栈到栈2while(StackSize(noempty) 1){StackPush(empty,StackTop(noempty));StackPop(noempty);}//找到队头int ret StackTop(noempty);StackPush(empty,ret);StackPop(noempty);//重新入栈1while(StackSize(empty) 0){StackPush(noempty,StackTop(empty));StackPop(empty);}return ret;
}1.5判断队列是否为空
依据上面思路因为栈1是用来存数据的所以当栈1为空时就代表我们模拟的队列为空。
bool myQueueEmpty(MyQueue* obj)
{assert(obj);return StackEmpty(obj-st1);
}二、用队列实现栈
具体题目可以参考LeetCode225. 用队列实现栈 与用栈实现队列相似我们同样需要两个队列来模拟实现栈且关键在于还原队列先入先出的性质依此性质来实现函数。既然这样我们可以如下定义结构体
typedef struct
{Queue* q1;//队列1Queue* q2;//队列2
} MyStack;我们可以看到与模拟队列不同的是模拟栈的结构体中存放的是两个结构体指针这与队列的实现方法有关。因为我们用的队列是用链表实现的所以其每个节点都是组成队列的一部分且我们应该通过指针将他们一个个都连接起来即通过指针来寻找节点。 至于用栈实现队列问题中的结构体我们存放的是两个关于栈的结构体是因为我们所使用的栈使用数组来实现的这样一来我们操作的就是栈结构体中某一个元素即动态开辟的数组。当然在我们也可以放两个栈结构体指针只不过在下面初始化队列时myQueueCreate() 我们需要额外malloc动态开辟栈结构大小的空间然后将指针指向该空间的地址。 实现 MyStack类
void push(int x)将元素 x压入栈顶int pop()移除并返回栈顶元素int top()返回栈顶元素boolean empty()如果栈是空的返回 true否则返回 false。
2.1初始化栈
malloc()动态开辟栈结构体没什么问题与模拟队列相似。但为什么还要给结构体中的两个队列结构体指针动态开辟空间呢这样不就违背了我们上面探讨的问题了吗其实不然这里的两个结构体指针事实上指向的是存放队列头指针和尾指针的结构体如下
typedef struct Queue
{QNode* phead;//队列头指针QNode* ptail;//队列尾指针int size;//长度
}Queue;这样一来基本每个函数都需要用到此结构体那么我们就必须malloc开辟来增加作用域和生命周期。 最后再初始化这两个存放头/尾指针的结构体并返回用来模拟栈的结构体地址。
MyStack* myStackCreate()
{MyStack* pst (MyStack*)malloc(sizeof(MyStack));pst-q1 (Queue*)malloc(sizeof(Queue));pst-q2 (Queue*)malloc(sizeof(Queue));QueueInit(pst-q1);QueueInit(pst-q2);return pst;
}2.2模拟出栈
与模拟出队列不同的是这里用来模拟出栈的两个队列都可以用来出栈和入栈具体方法如下 为了还原栈先入后出的性质我们可以先找到不为空的队列因为两个队列都有可能有数据但不同时有然后将有数据的队列noempty除队尾的一个节点全都出队列并入队列到无数据的队列empty这样一来就找到了尾节点模拟的栈顶。还需要注意的是此时我们无需再将数据重新入到noempty。 逻辑大致如下 int myStackPop(MyStack* obj)
{//先假设队列1为空Queue* empty obj-q1;Queue* noempty obj-q2;//纠正if(QueueEmpty(obj-q2)){empty obj-q2;noempty obj-q1;}//noempty出并入到emptywhile(QueueSize(noempty) 1){int cmp QueueFront(noempty);QueuePop(noempty);QueuePush(empty, cmp);}//取到模拟的栈顶元素int ret QueueFront(noempty);QueuePop(noempty);return ret;
}2.3模拟入栈
依据上面的方法我们是要将数据入到不为空的队列简单的if语句便可完成筛选。
void myStackPush(MyStack* obj, int x)
{assert(obj);if(!QueueEmpty(obj-q1)){QueuePush(obj-q1, x);}else{QueuePush(obj-q2, x);}
}2.4取模拟的栈顶元素
同样我们需要找到不为空的那个队列且事实上队列尾指针指向的那个节点就是模拟的栈的栈顶我们只需返回此元素即可。
int myStackTop(MyStack* obj)
{assert(obj);//找不为空的队列if(!QueueEmpty(obj-q1))return QueueBack(obj-q1);elsereturn QueueBack(obj-q2);
}2.5判读栈是否为空
当两个队列都没有数据时那么模拟的栈就是空栈。
bool myStackEmpty(MyStack* obj)
{assert(obj);return QueueEmpty(obj-q1) QueueEmpty(obj-q2);
}
