【C#算法实现】由两个栈组成的队列

前言

本文是【程序员代码面试指南（第二版）学习笔记】C#版算法实现系列之一，用C#实现了《程序员代码面试指南》（第二版）栈和队列中的由两个栈组成的队列。

一、题目要求

用两个栈实现队列的基础功能——入队、出队、获取队首元素。

二、算法设计及代码实现

2.1 算法思想

1、初始化的两个栈，第一个栈只需要不断将要入队的元素放入栈中即可；另一个栈则需要在每次出队和获取队首元素操作时检查栈是否为空，如果为空，则需要将第一个栈的元素全部逐个压入此栈，此时此栈按顺序出栈的序列将会是正常队列的出队顺序。正所谓负负得正。
2、入队：放入第一个栈即可。
3、出队：第二个栈为空，便将第一个栈的元素逐个弹出全部压入第二个栈，再弹出栈顶元素；不为空就直接弹出栈顶元素。
4、获取队首元素：第二个栈为空，便将第一个栈的元素逐个弹出全部压入第二个栈，再返回栈顶元素；不为空就直接返回栈顶元素。

2.2 代码实现

using System.Collections;

public class TwoStackQueue {
    // 该栈用于队列元素的初始入队
    private readonly Stack<int> stackPush = new();
    // 该栈用于队列的出队操作
    private readonly Stack<int> stackPop = new();
    // 将push中的入队序列倒序压入pop栈
    private void PushToPop() {
        while (stackPush.Count > 0) {
            stackPop.Push(stackPush.Pop());
        }
    }

    // 入队
    public void Add(int value) {
        stackPush.Push(value);
    }

    // 出队
    public int Poll() {
        // Pop栈不空, 则直接弹出一个元素
        if (stackPop.Count > 0) {
            return stackPop.Pop();
        }
        // 否则需要将Push栈的元素逐个压入Pop栈, 再弹出一个元素
        else {
            PushToPop();
            return stackPop.Pop();
        }
    }

    public int Peek() {
        // Pop栈不空, 则直接返回一个元素
        if (stackPop.Count > 0) {
            return stackPop.Peek();
        }
        // 否则需要将Push栈的元素逐个压入Pop栈, 再返回一个元素
        else {
            PushToPop();
            return stackPop.Peek();
        }
    }
}