C++采用队列实现栈的逆置
时间: 2023-11-07 18:14:52 浏览: 103
C++中可以使用STL中的queue容器来实现队列,也可以使用STL中的stack容器来实现栈。下面是采用队列实现栈的逆置的示例代码:
```cpp
#include <iostream>
#include <queue>
using namespace std;
void reverse_queue(queue<int>& q) {
if (q.empty()) {
return;
}
int top = q.front();
q.pop();
reverse_queue(q);
q.push(top);
}
int main() {
queue<int> q;
q.push(1);
q.push(2);
q.push(3);
q.push(4);
reverse_queue(q);
while (!q.empty()) {
cout << q.front() << " ";
q.pop();
}
return 0;
}
```
输出结果为:4 3 2 1
在reverse_queue函数中,我们通过递归实现了将队列中的元素逆序。具体实现方式是,先递归调用reverse_queue函数,将队列中除了队首元素的其他元素逆序;然后再将队首元素加入到逆序后的队列中。这样就可以实现将队列逆置的效果。
相关问题
c++ 使用额外的一个队列将栈逆置
可以使用一个辅助栈来将原栈逆置。具体实现方式是,将原栈中的元素依次出栈并压入辅助栈中,然后再将辅助栈中的元素依次出栈并压回原栈中,这样就完成了栈的逆置操作。以下是示例代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100
typedef struct {
int data[MAX_SIZE];
int top;
} Stack;
void init(Stack *s) {
s->top = -1;
}
int is_empty(Stack *s) {
return s->top == -1;
}
int is_full(Stack *s) {
return s->top == MAX_SIZE - 1;
}
void push(Stack *s, int x) {
if (is_full(s)) {
printf("Stack overflow\n");
exit(1);
}
s->data[++s->top] = x;
}
int pop(Stack *s) {
if (is_empty(s)) {
printf("Stack underflow\n");
exit(1);
}
return s->data[s->top--];
}
void reverse(Stack *s) {
Stack t;
init(&t);
while (!is_empty(s)) {
push(&t, pop(s));
}
while (!is_empty(&t)) {
push(s, pop(&t));
}
}
int main() {
Stack s;
init(&s);
push(&s, 1);
push(&s, 2);
push(&s, 3);
push(&s, 4);
reverse(&s);
while (!is_empty(&s)) {
printf("%d ", pop(&s));
}
printf("\n");
return 0;
}
```
输出结果为:4 3 2 1
利用栈将队列中元素逆置
可以将队列中的所有元素依次入栈,然后再依次出栈放回队列,这样就能实现队列中元素的逆置。
具体步骤如下:
1. 定义一个队列和一个栈。
2. 将队列中的所有元素依次入栈。
3. 循环出栈,将出栈的元素依次放回队列中。
4. 循环结束后,队列中的元素顺序已经被逆置。
以下是示例代码(使用Python实现):
```python
queue = [1, 2, 3, 4, 5] # 定义一个队列
stack = [] # 定义一个栈
# 将队列中的所有元素依次入栈
while queue:
stack.append(queue.pop(0))
# 将栈中的所有元素依次出栈,放回队列中
while stack:
queue.append(stack.pop())
print(queue) # 输出逆置后的队列
```
输出结果为:
```
[5, 4, 3, 2, 1]
```
相关推荐
![c](https://img-home.csdnimg.cn/images/20210720083646.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)