Очередь на основе стеков

Опубликовано Sep 30, 2011 в Стеки и очереди | 6 коммент.

, ,

Очередь на основе стеков

Реализуйте класс очередь, используя для этого два стека. Нужно продемонстрировать знание стандартных структур данных и их интерфейсов,  а так же умение придумать и реализовывать необходимые для методов интерфейса алгоритмы. Подсказка – что должно получиться, ее обычно в подобных задачах не дают.

 public class MyQueue
 {
    //Ваш код
 
  public int size() {
    //Ваш код
  }
  public void add(T value) {
   //Ваш код
  }
  public T peek() {
    //Ваш код
  }
  public T remove() {
  //Ваш код
  }
};

Ожидаемые вопросы:

  1. Какого типа данные содержатся в узле?
  2. Можно ли выделить дополнительную память необходимого размера, кроме двух стеков?
  3. Есть ли среди полей узла списка поле, содержащее заведомо уникальные данные?
  4. Одинаково ли мы понимаем, что интерфейс класса стек содержит методы pop, push и peek со стандартной сигнатурой и безопасным управлением памятью? Может для определенности просто использовать стек из STL?

Оценка результатов:

От начинающего программиста вопросы ожидаются, хотя лучше их не задавать. Например, можно создать класс шаблона и, таким образом, первый вопрос самоликвидируется. Решение существует при отрицательном ответе на второй и третий вопрос, поэтому они не нужны. Но примется решение для конкретного типа данных с принятием допущений из второго и третьего вопросов.

От программиста с опытом возможен последний вопрос. Решение должно быть реализовано без всяких дополнительных условий.

Реализация на C# - немного модифицированный вариант автора Vova

 
public class QueueOnTwoStacks<T>
  {
    private Stack<T> StackMain  = new Stack<T>();
    private Stack<T> StackTemp = new Stack<T>();
    private T FirstInQueue;
 
    public QueueOnTwoStacks(){
    }
 
    public int size()
    {
      return StackMain.Count;
    }
 
    public void add(T value)
    {
      if (StackMain.Count == 0)
      {
        FirstInQueue = value;
      }
      StackMain.Push(value);
    }
 
    public T peek()
    {
      if (StackMain.Count != 0)
      {
        return FirstInQueue;
      }
      else return default(T);
    }
 
    public T remove()
    {
      if (StackMain.Count != 0)
      {
        StackTemp.Clear();
 
        T ret;
 
        if (StackMain.Count != 1)
        {
          while (StackMain.Count != 1)
          {
            StackTemp.Push(StackMain.Pop());
          }
 
          ret = StackMain.Pop();
 
          FirstInQueue = StackTemp.Peek();
 
          StackMain.Clear();
          while (StackTemp.Count != 0)
          {
            StackMain.Push(StackTemp.Pop());
          }
        }
        else
        {
          FirstInQueue = default(T);
          ret = StackMain.Pop();
        }
        return ret;
      }
      else
        return StackMain.Pop();
    }
  }

 

Другая реализация задачи. Вопрос: на чем основана идея алгоритмов методов peek(), pop(), push()?

Еще одна реализация на C# - пример использования расширяющего метода

//Расширяющий метод - добавляет к стандартному классу Stack<int>
//проверку того, пуст стек или нет. Ограничение - класс расширения
//нельзя сделать обобщенным, пришлось пример привести для типа Stack<int>
  public static class MyStackExtensions
  {
    public static bool empty(this Stack<int> stack)
    {
      return stack.Count == 0 ? true : false;
    }
  }   
 
  public class MyQueue
  {
    private Stack<int> s1, s2;
 
    private bool empty()
    {
      return size() == 0 ? true : false;
    }
 
    public MyQueue()
    {
      s1 = new Stack <int>();
      s2 = new Stack <int>();
    }
 
    public int size()
    {
      return s1.Count + s2.Count;
    }
    public void add(int value)
    {
      s1.Push(value);
    }
 
    public int peek()
    {
      if (!s2.empty()) return s2.Peek();
      while (!s1.empty()) s2.Push(s1.Pop());
      return s2.Peek();
    }
 
    public int remove()
    {
      if (!s2.empty()) return s2.Pop();
      while (!s1.empty()) s2.Push(s1.Pop());
      return s2.Pop();
    }
  }

Реализация на C++ - см. комментарий galileo


6 Коммент. : “Очередь на основе стеков”

  1. Вот попробовал. Интересно – правильно?

    public class QueueOnTwoStacks<T>
      {
     
        public Stack<T> StackEnd = new Stack<T>();
        private Stack<T> StackBegin = new Stack<T>();
        private T FirstInQueue;
        private int QueueSize = 0;
     
        public QueueOnTwoStacks()
        {
     
        }
     
        public int size()
        {
          return QueueSize;
        }
     
        public void add(T value)
        {
          if (QueueSize == 0)
          {
            FirstInQueue = value;
          }
          QueueSize++;
          StackEnd.Push(value);
        }
        public T peek()
        {
          if (QueueSize != 0)
          {
            return FirstInQueue;
          }
          else return default(T);
        }
        public T remove()
        {
     
          StackBegin.Clear();
     
          int cnt = 0;
     
          try
          {
            while (QueueSize - cnt != 1)
            {
              StackBegin.Push(StackEnd.Pop());
              cnt++;
            }
          }
          catch (Exception e)
          {
            Console.WriteLine("Очередь пуста");
          }
     
          if (QueueSize != 0)
          {
            T ret = StackEnd.Pop();
     
            QueueSize = cnt;
     
            FirstInQueue = StackBegin.Peek();
     
            StackEnd.Clear();
            while (StackBegin.Count != 0)
            {
              StackEnd.Push(StackBegin.Pop());
            }
     
            return ret;
          }
          else
            return default(T);
        }
      }
    • Галина says:

      В целом правильно, то есть работает. На что бы я обратила внимание при проверке.
      1)Почему public Stack StackEnd – public? Должен быть private.
      2) Не нужно вообще private int QueueSize = 0; – сам класс Stack
      знает, сколько в нем элементов – этим и нужно пользоваться.
      3) Названия StackEnd и StackBegin – запутывают, так как непонятно, чего конец и начало.
      4) Обработку исключений в таких задачах можно не трогать. Достаточно при попытке извлекать что-то из пустого стека будет его стандартного исключения.
      В теле поста будет приведено решение с учетом этих замечаний.

  2. Это тесты

     static void Main(string[] args)
        {
     
          QueueOnTwoStacks<int> testQueue = new QueueOnTwoStacks<int>();
     
     
          testQueue.add(1);
          testQueue.add(2);
          testQueue.add(3);
          testQueue.add(4);
          testQueue.add(5);
     
     
          Stack<int> testStack = testQueue.StackMain ;
     
          int i = testQueue.size(); 
     
          i = testQueue.peek();
     
          int elemPtr = testQueue.peek();
     
          i = testQueue.size();
     
          i = testQueue.remove(); 
     
          i = testQueue.size();
     
          testQueue.remove(); 
     
          elemPtr = testQueue.peek();
     
          testQueue.add(5);
     
          elemPtr = testQueue.peek();
        }
  3. Вариант на С++:

    #include <stack>
     
    template<class T> class TwoStacksQueue {
     
        std::stack<T> lifoStack, fifoStack;
     
        void fillFifoStack() {
            while(!lifoStack.empty()) {
                fifoStack.push(lifoStack.top());
                lifoStack.pop();
            }
        }
        public:
        bool empty() {
            return fifoStack.empty() && lifoStack.empty();
        }
     
        T front() {
            if (fifoStack.empty()) fillFifoStack();
            return fifoStack.top();
        }
        void pop() {
            if (fifoStack.empty()) fillFifoStack();
            fifoStack.pop();
        }
     
        void push(T v) {
            lifoStack.push(v);
        }
    };

Оставить комментарий

Ваш адрес email не будет опубликован.


*