首页 > 试题广场 >

由两个栈组成的队列

[编程题]由两个栈组成的队列
  • 热度指数:7521 时间限制:C/C++ 2秒,其他语言4秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
用两个栈实现队列,支持队列的基本操作。

输入描述:
第一行输入一个整数N,表示对队列进行的操作总数。

下面N行每行输入一个字符串S,表示操作的种类。

如果S为"add",则后面还有一个整数X表示向队列尾部加入整数X。

如果S为"poll",则表示弹出队列头部操作。

如果S为"peek",则表示询问当前队列中头部元素是多少。


输出描述:
对于每一个为"peek"的操作,输出一行表示当前队列中头部元素是多少。
示例1

输入

6
add 1
add 2
add 3
peek
poll
peek

输出

1
2

备注:
1<=N<=1000000

-1000000<=X<=1000000

数据保证没有不合法的操作
使用两个栈,入队栈和出队栈;入队使用入队栈,出队使用出队栈;
入队栈元素要转移到出队栈,必须保证: 
1.转移元素前出队栈为空 
2.转移元素后入队栈为空

import java.util.Scanner;
import java.util.Stack;

public class Main {
    private static Stack<Integer> stackPush;
    private static Stack<Integer> stackPop;

    public static void main(String[] args) {
        stackPush = new Stack<>();
        stackPop = new Stack<>();
        Scanner scanner = new Scanner(System.in);
        int n = Integer.valueOf(scanner.nextLine());
        String string;
        for (int i = 0; i < n; i++) {
            string = scanner.nextLine();
            if (string.equals("poll")) {
                poll();
            } else if (string.equals("peek")) {
                System.out.println(peek());
            } else {
                add(Integer.valueOf(string.split(" ")[1]));
            }
        }
    }

    public static void add(int number) {
        stackPush.push(number);
    }

    public static int poll() {
        if (stackPush.empty() && stackPop.empty()) {
            throw new RuntimeException("Your queue is empty!");
        }
        pushToPop();
        return stackPop.pop();
    }

    public static int peek() {
        if (stackPush.empty() && stackPop.empty()) {
            throw new RuntimeException("Your queue is empty!");
        }
        pushToPop();
        return stackPop.peek();
    }

    private static void pushToPop() {
        if (stackPop.empty()) {
            while (!stackPush.empty()) {
                stackPop.push(stackPush.pop());
            }
        }
    }
}


发表于 2019-12-13 15:12:07 回复(0)
#include <stdio.h>
#include <string.h>
#include <malloc.h>
#include <stdbool.h>

typedef struct {
    int *data;
    int top;
} stack;

stack *new_stack(int cap);

void push(stack *st, int val);

int pop(stack *st);

int top(stack *st);

bool is_empty(stack *st);

void destroy_stack(stack *st);

typedef struct {
    stack *data;
    stack *help;
} queue;

queue *new_queue(int n);

void add(queue *q, int val);

int poll(queue *q);

int peek(queue *q);

void destroy_queue(queue *q);

static void move(queue *q);

int main(void) {
    int n, x;
    char opt[10];
    scanf("%d", &n);
    queue *q = new_queue(n);
    for (int i = 0; i < n; i++) {
        scanf("%s", opt);
        if (strcmp(opt, "add") == 0) {
            scanf("%d", &x);
            add(q, x);
        } else if (strcmp(opt, "poll") == 0) {
            poll(q);
        } else {
            printf("%d\n", peek(q));
        }
    }
    destroy_queue(q);
    return 0;
}

stack *new_stack(int cap) {
    stack *st = (stack *) malloc(sizeof(stack));
    st->data = (int *) malloc(sizeof(int) * cap);
    st->top = -1;
    return st;
}

void push(stack *st, int val) {
    st->data[++st->top] = val;
}

int pop(stack *st) {
    return st->data[st->top--];
}

int top(stack *st) {
    return st->data[st->top];
}

bool is_empty(stack *st) {
    return st->top == -1;
}

void destroy_stack(stack *st) {
    free(st->data);
    free(st);
}

queue *new_queue(int n) {
    queue *q = (queue *) malloc(sizeof(queue));
    q->data = new_stack(n);
    q->help = new_stack(n);
    return q;
}

void add(queue *q, int val) {
    push(q->data, val);

}

int poll(queue *q) {
    if (is_empty(q->help)) {
        move(q);
    }
    return pop(q->help);
}

int peek(queue *q) {
    int x;
    if (is_empty(q->help)) {
        move(q);
    }
    x = top(q->help);
    return x;
}

void destroy_queue(queue *q) {
    destroy_stack(q->data);
    destroy_stack(q->help);
    free(q);
}

static void move(queue *q) {
    if (!is_empty(q->help)) {
        return;
    }
    while (!is_empty(q->data)) {
        push(q->help, pop(q->data));
    }
}

发表于 2022-02-16 00:08:40 回复(0)
import java.util.Scanner;
import java.util.Stack;

public class Main {


    public static void main(String[] args) {

        Queue<Integer>  queue = new Queue<Integer>();

        Scanner scanner = new Scanner(System.in);
        int n = Integer.valueOf(scanner.nextLine());
        String string;
        for (int i = 0; i < n; i++) {
            string = scanner.nextLine();
            if (string.equals("poll")) {
                queue.poll();
            } else if (string.equals("peek")) {
                System.out.println(queue.peek());
            } else {
                queue.offer(Integer.valueOf(string.split(" ")[1]));
            }
        }
    }
}

class Queue<T>{
    private Stack<T> in = new Stack<T>();
    private Stack<T> out = new Stack<T>();

    public synchronized boolean offer(T item) {
        in.push(item);
        return true;
    }


    public synchronized T poll() {

        if (!out.empty()) {
            return out.pop();
        }

        if (in.empty()) {
            return null;
        }

        while (!in.empty()) {
            T t = in.pop();
            out.push(t);
        }

        return out.pop();
    }

    public synchronized T peek(){

        if (!out.empty()) {
            return out.peek();
        }

        if (in.empty()) {
            return null;
        }

        while (!in.empty()) {
            T t = in.pop();
            out.push(t);
        }

        return out.peek();
    }

}

发表于 2021-03-21 07:48:57 回复(0)
#include<iostream>
#include<stack>
#include<algorithm>
#include<cstring>
using namespace std;
int main(){
    stack<int> s1,s2;
    int n,x;
    string str;
    scanf("%d",&n);
    while(n--){
        cin>>str;
        if(str=="add"){
            cin>>x;
            s1.push(x);
        }else{
            if(s2.empty()){
                while(!s1.empty()){
                    s2.push(s1.top());
                    s1.pop();
                }
            }
            if(str=="peek") printf("%d\n",s2.top());
            else s2.pop();
        }
    }
    return 0;
}
发表于 2020-09-24 17:00:17 回复(0)
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,x;
    string s;
    cin>>n;
    stack<int>s1,s2;
    while(n--)
    {
        cin>>s;
        if(s=="add")
        {
            cin>>x;
            s1.push(x);
        }
        else if(s=="poll")
        {
            if(s2.empty())
            {
                while(!s1.empty())
                {
                    s2.push(s1.top());
                    s1.pop();
                }
            }
            s2.pop();
        }
        else
        {
            if(s2.empty())
            {
                while(!s1.empty())
                {
                    s2.push(s1.top());
                    s1.pop();
                }
            }
            cout<<s2.top()<<endl;
        }
    }
    return 0;
}

发表于 2019-08-23 22:19:38 回复(0)
#include <iostream>
#include <stack>
using namespace std;

//两个栈实现一个队列,s1作为接收数据栈,s2作为队列使用
stack<int> s1, s2;

//s3转移元素到s4
void transData(stack<int> &s3, stack<int> &s4)
{
    while(!s4.empty())
        s4.pop();
    while(!s3.empty())
    {
        s4.push(s3.top());
        s3.pop();
    }
}

//增加元素,要先将s2中的元素读过来,防止在上次插入过后,有poll,写完之后,再更新一下s2
void add(int x)
{
	transData(s2, s1);
    s1.push(x);
    transData(s1, s2);
}

//弹出元素
void poll()
{
    if(!s2.empty())
		s2.pop();
    else
        return;
}

//获取队列头元素
int peek()
{
    return s2.top();
}

int main()
{
    int n, x;
    string str;
    cin >> n;
    while(n--)
    {
        cin >> str;
        if(str == "add")
        {
            cin >> x;
            add(x);
        }
        else if(str == "poll")
            poll();
        else if(str == "peek")
            cout << peek() << endl;
    }
	return 0;
}

编辑于 2019-08-13 20:56:17 回复(0)
#include <bits/stdc++.h>
using namespace std;

int main(){
    string s;
    stack<int> S1, S2;
    int n, x;
    cin>>n;
    while(n--){
        cin>>s;
        if(s=="add"){
            cin>>x;
            S2.push(x);
        }else{
            if(S1.empty())
                while(!S2.empty()){
                    x = S2.top();
                    S2.pop();
                    S1.push(x);
                }
            if(s=="poll")
                S1.pop();
            else if(s=="peek")
                cout<<S1.top()<<endl;
        }
    }
    return 0;
}

发表于 2020-01-31 00:53:06 回复(0)
用一个入队栈和一个出队栈构建队列:
(1) 入队操作时元素直接进入入队栈;
(2) 出队操作时先看出队栈中是否有元素,如果有就先把其中的元素弹栈,否则就先将入队栈中的元素全部弹出到出队栈,再对出队栈进行弹栈出队,这样就能够保证先进先出。
(3) 查看队首元素与(2)的操作类似,只是不将元素弹出,仅仅只是查看栈顶元素。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Stack;

class StackQueue {
    public Stack<Integer> inStack;
    public Stack<Integer> outStack;
    public StackQueue() {
        inStack = new Stack<Integer>();
        outStack = new Stack<Integer>();
    }
    
    public void add(int val){
        inStack.push(val);
    }
    
    public void poll() {
        if(outStack.isEmpty()){
            while(!inStack.isEmpty())
                outStack.push(inStack.pop());
        }
        outStack.pop();
    }
    
    public int peek() {
        if(outStack.isEmpty()){
            while(!inStack.isEmpty())
                outStack.push(inStack.pop());
        }
        return outStack.peek();
    }
}


public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        StackQueue queue = new StackQueue();
        for(int i = 0; i < n; i++){
            String[] params = br.readLine().trim().split(" ");
            String op = params[0];
            if(op.equals("peek")){
                System.out.println(queue.peek());
            }else if(op.equals("poll")){
                queue.poll();
            }else{
                int val = Integer.parseInt(params[1]);
                queue.add(val);
            }
        }
    }
}

发表于 2021-06-13 21:35:43 回复(0)

import sys

class stackToQueue(object):
    def __init__(self):
        self.stackPush = []
        self.stackPop = []
        self.stackTemp = []

    def pushToPop(self):
        if not self.stackPop:
            while self.stackPush:
                self.stackPop.append(self.stackPush.pop())

    def add(self, num):
        self.stackPush.append(num)
        self.pushToPop()

    def peek(self):
        if self.stackPop:
            return self.stackPop[len(self.stackPop) - 1]
        else:
            self.pushToPop()
            return self.stackPop[len(self.stackPop) - 1]

    def poll(self):
        if self.stackPop:
            self.stackPop.pop()
        else:
            self.pushToPop()
            self.stackPop.pop()

N = int(input())
result = stackToQueue()
for i in range(N):
    line = sys.stdin.readline().strip()
    word = line.split()
    if word[0] == "add":
        result.add(int(word[1]))
    elif word[0] == "peek":
        print(result.peek())
    elif word[0] == "poll":
        result.poll()

发表于 2022-02-12 17:58:33 回复(0)
《程序员代码面试指南》Python题解 https://zhuanlan.zhihu.com/p/444550262
class MyQueue:
    def __init__(self):
        # 栈A用来存放数据的
        self.stack_A = []
        # 栈A中的数据数
        self.num_A = 0
        # 栈B用来存放栈A中的数据
        self.stack_B = []
        # 栈B中的数据数
        self.num_B = 0

    # 存放数据
    def add(self, x):
        # 将x放入栈A中
        self.stack_A.append(x)
        self.num_A += 1

    # 将栈A中的数据全部放入栈B中
    def A2B(self):
        # 只有栈B中没有数据时
        # 才将栈A中的数据放入
        # 否则的话直接弹出栈B中的数据即可
        if self.num_B == 0:
            while self.num_A > 0:
                self.stack_B.append(self.stack_A.pop())
                # 更新
                self.num_B += 1
                self.num_A -= 1

    # 获取队头元素
    def peek(self):
        self.A2B()
        if self.num_B > 0:
            return self.stack_B[-1]
        else:
            return None

    # 弹出队列头部元素
    def poll(self):
        self.A2B()
        # 元素个数减1
        self.num_B -= 1
        return self.stack_B.pop()


# 操作次数
n = int(input())
# 自己定义的由两个栈组成的队列
myqueue = MyQueue()
for i in range(n):
    # 操作字符串
    operator = input().split()
    if operator[0] == 'add':
        myqueue.add(operator[1])
    elif operator[0] == 'peek':
        print(myqueue.peek())
    elif operator[0] == 'poll':
        myqueue.poll()


发表于 2021-12-14 09:08:15 回复(0)
C++,可以运行通过。
#include<iostream>
#include<stack>
#include<string>
using namespace std;
int main()
{
    int N,num;
    string x;
    stack<int> stack1,stack2;
    cin>>N;
    for(int i=0;i<N;++i){
        cin>>x;
        if(x=="add"){
            cin>>num;
            stack1.push(num);
        }else if(x=="poll"){
            if(!stack2.empty()){
                stack2.pop();
            }else{
                while(!stack1.empty()){
                    stack2.push(stack1.top());
                    stack1.pop();
                }
                stack2.pop();
            }
        }else if(x=="peek"){
            if(!stack2.empty()){
                cout<<stack2.top()<<endl;
            }else{
                while(!stack1.empty()){
                    stack2.push(stack1.top());
                    stack1.pop();
                }
                cout<<stack2.top()<<endl;
            }
        }
    }
    return 0;
}

发表于 2021-07-12 09:58:39 回复(0)
var line=readline()

let stackpush=[],stackpop=[]

var change=function(){
      if(stackpop.length==0){
            while(stackpush.length){
                stackpop.push(stackpush.pop())
            }
        }
};

while(line=readline()){
    let [action,num]=line.split(' ')
    if(action=='add'){
        stackpush.push(parseInt(num))
    }else if(action=='peek'){
        change()
       console.log( stackpop[stackpop.length-1])
    }else{
        change()
        stackpop.pop()
    }
}

发表于 2021-06-24 00:16:03 回复(0)
#include <iostream>
#include <stack>
#include <string>
using namespace std;

struct MyQueue{
    stack<int> st_push;
    stack<int> st_pop;
    
    void push2pop(){
        if(st_pop.empty()){
            while(!st_push.empty()){
                st_pop.push(st_push.top());
                st_push.pop();
            }
        }
    }
    
    void push(int val){
        st_push.push(val);
        push2pop();
    }
    
    void pop(){
        push2pop();
        st_pop.pop();
    }
    
    void peek(){
        push2pop();
        cout << st_pop.top() << endl;
    }
};

int main(void){
    MyQueue mq;
    int N;
    string s;
    int val;
    cin >> N;
    for(int i = 0; i < N; i++){
        cin >> s;
        if(s == "add"){
            cin >> val;
            mq.push(val);
        }else{
            if(s == "poll"){
                mq.pop();
            }else{
                mq.peek();
            }
        }
    }
    return 0;
}

用一个栈先压,将压后的栈弹出在压入另一个栈
连续两次就相当于队列
注意问题:
在弹出或获取peek的时候,需要先判断能否push2pop,然后再操作,否则出错。
发表于 2021-04-17 00:47:46 回复(0)
#include<bits/stdc++.h>
using namespace std;

class mystack
{
public:
    stack<int> st1, st2;
    
    void add(int x)
    {
        st1.push(x);
    }
    
    
    void poll()
    {
        transform();
        st2.pop();
        anti_transform();
    }
        
    int peek()
    {
        transform();
        int result = st2.top();
        anti_transform();
        return result;
    }
private:
    inline void transform()
    {
        while(!st1.empty())
        {
            st2.push(st1.top());
            st1.pop();
        }
    }
    
    inline void anti_transform()
    {
        while(!st2.empty())
        {
            st1.push(st2.top());
            st2.pop();
        }
    }
};

int main()
{
    int num;
    cin >> num;
    getchar();
    string line;
    mystack st;
    for(int i = 0; i < num; ++i)
    {
        int x;
        getline(cin,line);
        if(sscanf(line.c_str(),"add %d",&x) == 1)
        {
           st.add(x);
        }else if(strcmp(line.c_str(),"poll") == 0){
            st.poll();
        }else if(strcmp(line.c_str(),"peek") == 0){
            cout << st.peek() << endl;
        }
    }
    return 0;
}

发表于 2021-02-19 20:50:46 回复(0)
import java.util.*;
import java.io.*;
import java.math.*;

/*
    实现一个特殊功能的栈,在实现栈的基本功能的基础上,再实现返回栈中最小元素的操作。
*/
public class Main{
    
    public static void main(String[] args) {
        InputReader inputReader = new InputReader();
        PrintWriter printWriter = new PrintWriter(System.out);
        inputReader.nextLine();  // 输入
        int size = inputReader.nextInt(); // 将 String --> int
        TwoStackQueue stack = new TwoStackQueue();

        for (int i = 0; i < size; i++){
            inputReader.nextLine(); // 读取一行
            String operate = inputReader.next();

            if ("add".equals(operate)){
                Integer num = inputReader.nextInt();
                stack.add(num);
            }
            if ("poll".equals(operate)){
                stack.poll();
            }
            if ("peek".equals(operate)){
                printWriter.println(stack.peek());
            }
        }
        printWriter.close();
    }
    
}
 class TwoStackQueue{
    public Stack<Integer> stackPush;
    public Stack<Integer> stackPop;
    
    public TwoStackQueue(){
        stackPush=new Stack<Integer>();
        stackPop=new Stack<Integer>();
    }
    private void pushToPop(){
        if (stackPop.empty()){
            while(!stackPush.empty()){
                stackPop.push(stackPush.pop());
            }
        }
    }
     public void add(int pushInt){
         stackPush.push(pushInt);
         pushToPop();
     }
    public int poll(){
        if(stackPop.empty()&&stackPush.empty()){
            throw new RuntimeException("Your queue is empty.");
        }
        pushToPop();
        return stackPop.pop();
    }
    
    public int peek(){
        if(stackPop.empty()&&stackPush.empty()){
            throw new RuntimeException("Your queue is empty.");
        }
        pushToPop();
        return stackPop.peek();
    }
}
class InputReader{
    BufferedReader buf; // 缓冲字符流
    StringTokenizer tok;

    InputReader(){
        // InputStreamReader inputStreamReader = new InputStreamReader(System.in);
        // buf = new BufferedReader(inputStreamReader);
        buf = new BufferedReader(new InputStreamReader(System.in));
    }

    boolean hasNext(){
        // 为什么用while 而不用if?? 这里在多线程唤醒那里也遇到了
        while (tok == null || !tok.hasMoreElements()){
            return false;
        }
        return true;
    }
    // 从缓存中读入一行字符串
    void nextLine(){
        try {
            // 创建一个解析给定字符流的tokenizer。
            tok = new StringTokenizer(buf.readLine());
        } catch (Exception e) {
            tok = null;
        }
    }
    String next(){
        if(hasNext()){
            return tok.nextToken();
        }
        return null;
    }
    /*
        数据类型转换
        String --> int,long,double,BigInteger,BigDecimal
     */
    int nextInt(){
        return Integer.parseInt(next());
    }
    long nextLong(){
        return Long.parseLong(next());
    }
    double nextDouble(){
        return Double.parseDouble(next());
    }
    BigInteger nextBigInteger(){
        // 将BigInteger的十进制字符串表示形式转换为BigInteger。
        return new BigInteger(next());
    }
    BigDecimal nextBigDecimal(){
        //将BigDecimal的字符串表示 BigDecimal转换为 BigDecimal 。
        return new BigDecimal(next());
    }
}

发表于 2020-11-03 16:14:18 回复(0)
import java.io.*;
import java.util.*;

public class Main{
    private Stack<Integer> stackPush;
    private Stack<Integer> stackPop;
    public Main(){
        this.stackPush = new Stack<Integer>();
        this.stackPop = new Stack<Integer>();
    }
    public void pushTopop(){
      if(stackPop.isEmpty()){
        while(!stackPush.isEmpty()){
          stackPop.push(stackPush.pop());
        }
      }
    }
    public void add(int num){
      this.stackPush.push(num);
      pushTopop();

    }
    public int poll(){
      pushTopop();
      int val = this.stackPop.pop();
      return val;
    }
    public int peek(){
      pushTopop();
      int val = this.stackPop.peek();
      return val;
    }

    public static void main(String args[])throws IOException{
      Main ma = new Main();
 BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

   int nums = Integer.parseInt(br.readLine());
 for(int i =0;i<nums;i++){
       String[] input = br.readLine().split(" ");
       if(input[0].equals("add")){
           ma.add(Integer.parseInt(input[1]));
       }
       if(input[0].equals("poll")){
           ma.poll();
       }
       if(input[0].equals("peek")){
           int val= ma.peek();
           System.out.println(val);
       }

   }
   br.close();

    }
}

idea:栈是后进先出,队列是先进先出。
那就让两个栈在中间运作。如果是add先加入一个栈A中,如果poll,把其他数据弹入到栈B,再弹出栈A最后一个值。如果是peek,就只使用栈A的peek(),下次再要add,将数据push入栈B。
但这里有一个问题,就是如何区分栈A栈B,如何告诉机器下一次该找栈A还是栈B。同时,这样每一次处理时间复杂度和空间复杂度都是O(N)实在是有些夸张
如何区分栈AB,首先取名为栈AB,如果栈AB都为空,放入栈A。如果栈A为空,栈B不为空。放入栈B如果栈AB都不为空,栈Bsize大于1,放入栈B。else 放入栈A。这种讨论发生在add poll 和peak中
所以一定需要改进
所有数据放入栈A,栈A放入栈B。
poll和peak都更容易实现。
但是时间复杂度和空间复杂度都是O(N)


实现了,但是有错,因为单个元素push pop还是没有能够改变顺序

具体实现:一个栈作为压入栈,在压入数据时只往这个栈中压入,记为stackPush;另外一个栈作为弹出栈,只从这个栈中弹出记做stackPop

因为数据压入栈的时候,顺序是先进后出。
那么只要把stackPush的数据压入stackPop中,顺序就会变过来了
但是听上去简单,必须做到以下两点
1.如果stackPush要往stackPop中压入数据,那么必须一次性把stackPush中的数据全部压入
2.如果stackPop不为空,stackPush绝对不能像stackPop中压入数据,违反了以上两点都会发生错误 
发表于 2020-09-18 15:57:47 回复(0)
#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int n, k;
    string str;
    vector<int> vec;
    cin>>n;
    while(n--)
    {
        cin>>str;
        if(str=="add")
        {
            cin>>k;
            vec.push_back(k);
        }
        else if(str == "peek")
        {
            cout<<vec[0]<<endl;
        }
         else if(str == "poll")
        {
            vec.erase(vec.begin());
        }
    }
    
    return 0;
}
编辑于 2020-08-23 19:56:35 回复(0)
#include <iostream>
#include <string>
#include <stack>

using namespace std;

int main () {
    int n, num;
    cin >> n;
    stack<int> stk1, stk2;
    for (int i = 0; i < n; ++i) {
        string command;
        cin >> command;
        if (command == "add") {
            cin >> num;
            stk1.push(num);
        } else if (command == "peek") {
            if (stk2.empty()) {
                if (stk1.empty()) {
                    cout << "error" << endl;
                } else {
                    while (!stk1.empty()) {
                        num = stk1.top();
                        stk2.push(num);
                        stk1.pop();
                    }
                    cout << stk2.top() << endl;
                }
            } else {
                cout << stk2.top() << endl;
            }
        } else { // poll
            if (stk2.empty()) {
                if (stk1.empty()) {
                    cout << "error" << endl;
                } else {
                    while (!stk1.empty()) {
                        num = stk1.top();
                        stk2.push(num);
                        stk1.pop();
                    }
                    stk2.pop();
                }
            } else {
                stk2.pop();
            }
        }
    }
    return 0;
}

发表于 2020-08-10 11:24:25 回复(0)

C++实现


这个也是众所周知系列了,值得注意的一点就是,两个栈,一个作为进队栈,一个作为出队栈,在出队栈的元素弹出完之前,都不需要将进队栈的元素倒过去。
上个代码摸个鱼
#include <bits/stdc++.h>
using namespace std;

class myQueue{
private:
    stack<int> s1, s2;

public:
    void add(int x){
        s1.push(x);
    }
    
    void poll(){
        if(s2.empty()){
            while(s1.empty() == false){
                s2.push(s1.top());
                s1.pop();
            }
        }
        s2.pop();
    }
    
    int peek(){
        if(s2.empty()){
            while(s1.empty() == false){
                s2.push(s1.top());
                s1.pop();
            }
        }
        return s2.top();
    }
};

int main(){
    int n;
    cin>>n;
    myQueue mq;
    while(n>0){
        --n;
        string op="";
        cin>>op;
        if(op == "add"){
            int temp;
            cin>>temp;
            mq.add(temp);
        }
        else if(op == "poll"){
            mq.poll();
        }
        else
            cout<<mq.peek()<<endl;
    }
}



发表于 2020-07-17 21:06:55 回复(0)
#队列先进先出,栈先入后出
#一个输入栈,一个输出栈,输入栈的顺序是进的顺序,
#将输入栈pop到输出栈后,输出栈的顺序是输出的顺序
import sys
class MyQueue:
    def __init__(self):
        self.push_stack = []
        self.poll_stack = []
    
    def add(self, data):
        self.push_stack.append(data)
    
    def __deliverData(self):
        if not self.poll_stack:
            while self.push_stack:
                self.poll_stack.append(self.push_stack.pop())
                
    def peek(self):
        self.__deliverData()
        return self.poll_stack[-1]
    
    def poll(self):
        self.__deliverData()
        self.poll_stack.pop()

myQueue = MyQueue()
n = int(sys.stdin.readline().strip())
for i in range(n):
    line = sys.stdin.readline().strip()
    args = line.split(' ')
    if args[0] == 'add':
        myQueue.add(int(args[1]))
    elif args[0] == 'peek':
        print(myQueue.peek())
    elif args[0] == 'poll':
        myQueue.poll()


发表于 2020-06-20 19:03:43 回复(0)