Problem of the Day
A new programming or logic puzzle every Mon-Fri

Glad you're back for another great week!

Today's problem is about combining two common data structures in to one. Your goal is to implement a data structure that can pop and push like a stack and also dequeue and enqueue like a queue. Here is an example of how your data structure should work.

store.push(5)
> [5]

store.enqueue(6)
> [5,6]

store.push(7)
> [7,5,6]

store.pop()
> 7

store.dequeue()
> 5

Note: pop and dequeue will essentially do the same thing since they always pull from the front of the line. As always, bonus points for efficiency!

Comments:

• Kevin Benton - 10 years, 8 months ago

  '''A stack and a queue'''
  class Squeue(object):
      _store = []
      def pop(self):
        ''' Meaning of pop in challenge is opposite of normal list pop method'''
        ret = self._store[0]
        del self._store[0]
        return ret
  
      def push(self, x):
        self._store.insert(0, x)
        return self._store
  
      def enqueue(self, x):
        self._store.append(x)
        return self._store
  
      def dequeue(self):
        return self.pop()
  
  
  store = Squeue()
  print store.push(5)
  print store.enqueue(6)
  print store.push(7)
  print store.pop()
  print store.dequeue()
  

  reply permalink

• Sanket Apte - 10 years, 8 months ago

  import java.util.LinkedList; import java.util.List;

  public class StackQueue<T> {

  private LinkedList<T> stackQueue;
  
  public StackQueue() {
      stackQueue=new LinkedList<T>();  
  }
  
  public void push(T object){
      stackQueue.addFirst(object);
      System.out.println(stackQueue);
  }
  
  public void enqueue(T object){
      stackQueue.addLast(object);
      System.out.println(stackQueue);
  }
  
  public T pop(){
      T object=null;
      object=stackQueue.getFirst();
      stackQueue.removeFirst();
      System.out.println(stackQueue);
      return object;
  }
  
  public T dequeue(){
      T object=null;
      object=stackQueue.getLast();
      stackQueue.removeLast();
      System.out.println(stackQueue);
      return object;
  }
  
  public static void main(String[] args) {
      StackQueue<Integer> stackQueue=new StackQueue<Integer>();
      Integer a=0;
      stackQueue.enqueue(5);
      stackQueue.enqueue(6);
      stackQueue.push(4);
      a=stackQueue.pop();
      stackQueue.push(4);
      a= stackQueue.dequeue();
      stackQueue.enqueue(8);
      stackQueue.push(2);
      a=stackQueue.dequeue();
  
  }
  

  }

  reply permalink

• klm - 10 years, 8 months ago

  Sanket, shouldn't pop and dequeue return the same object. The object that is at the front of the queue or at the top of the stack (however you like to look at it)?

  reply permalink

• Sanket Apte - 10 years, 8 months ago

  Yes. My bad. I ended up into combining functionality of stack and queue into one data structure. I just missed out a part of problem that both functions pop and dequeue should remove from front of the line.

  reply permalink

• Sanket Apte - 10 years, 8 months ago

  I'll refactor and post it again. Thaks klm. :-)

  reply permalink

• Jt - 10 years, 8 months ago

  C#, not sure why, but it seemed to me that using a list or an array would be cheating somehow. Thus the string, so it's not very efficient, but it works.

  namespace ProblemOtd20140414
  {
    using System;
  
    class Program
    {
      static void Main(string[] args)
      {
        Quack quack = new Quack();
        quack.Push(5);
        quack.Print();
        quack.Enqueue(6);
        quack.Print();
        quack.Push(7);
        quack.Print();
        Console.WriteLine(quack.Pop());
        quack.Print();
        Console.WriteLine(quack.Dequeue());
        quack.Print();
  
        Console.WriteLine("Finished, press enter to exit");
        Console.ReadLine();
      }
    }
  
    public class Quack
    {
      private string quack;
  
      public int Dequeue()
      {
        return this.Pop();
      }
  
      public void Enqueue(int number)
      {
        quack = quack + number + ",";
      }
  
      public int Pop()
      {
        if (quack.Length == 0)
        {
          throw new Exception("The Quack does not contain any entries");
        }
  
        int pos = quack.IndexOf(",");
  
        if (pos == 0)
        {
          throw new Exception("The Quack does not contain valid entries");
        }
  
        int number = int.Parse(quack.Substring(0, pos));
        quack = quack.Substring(pos + 1);
  
        return number;
      }
  
      public void Print()
      {
        Console.WriteLine(quack);
      }
  
      public void Push(int number)
      {
        quack = number + "," + quack;
      }
    }
  }
  

  reply permalink

• Jt - 10 years, 8 months ago

  Sorry, I didn't like that answer after I posted it. So... refactor time. Let's take advantage of built in classes.

  namespace ProblemOtd20140414
  {
    using System;
    using System.Collections;
  
    class Program
    {
      static void Main(string[] args)
      {
        Quack2 quack2 = new Quack2();
        quack2.Push(5);
        quack2.Print();
        quack2.Enqueue(6);
        quack2.Print();
        quack2.Push(7);
        quack2.Print();
        Console.WriteLine(quack2.Pop());
        quack2.Print();
        Console.WriteLine(quack.Dequeue());
        quack2.Print();
  
        Console.WriteLine("Finished, press enter to exit");
        Console.ReadLine();
      }
    }
  
    public class Quack2 : Stack
    {
      public int Dequeue()
      {
        return int.Parse(this.Pop().ToString());
      }
  
      public void Enqueue(int number)
      {
        Array tempArray = this.ToArray();
        this.Clear();
        this.Push(number);
        foreach (object obj in tempArray)
        {
          this.Push(obj);
        }
      }
  
      public void Print()
      {
        foreach (int number in this.ToArray())
        {
          Console.Write(number + ",");
        }
        Console.WriteLine();
      }
    }
  }
  

  reply permalink

• Bumbleguppy - 10 years, 8 months ago

  var store = {
      box : [],
      enque : function(num){
          this.box[this.box.length] = num;
          return this.box;
      },
      push : function(num){
          var i = this.box.length;
          if(i > 1){
              while(i--){
                  this.box[i + 1] = this.box[i];
              }
          }
          this.box[0] = num;
          return this.box;        
      },
      pop : function(){
          var retval = this.box[0];
          var tempArray = [];
          var i = this.box.length - 1;
          if(i){
              --i;
              do{
                  tempArray[i] = this.box[i + 1];
              }while(i--);
              this.box = tempArray;
          }
          return retval;
      },
      deqeue: function(){
          var retVal = this.pop();
          return retVal;
      }
  };
  
  window.onload = function(){
      console.log(store.push(5));
      console.log(store.enque(6));
      console.log(store.push(7));
      console.log(store.pop());
      console.log(store.deqeue());
  }
  

  javascript, adhering to the spirit of the problem, I tried to re-invent the native array functions from scratch.

  reply permalink

• Hueho - 10 years, 8 months ago

  "c suxx"

  I couldn't do it with efficiency (using a simple double-linked list with head and tail), so I did it with a terrible gimmick: generic stacks/queues!

  (Also I called it a deque, but I'm pretty sure it's not an actual deque, since it only allow to get elements from the end of the list)

  Behold:

  #include <stdlib.h>
  #include <stdio.h>
  #include <stdbool.h>
  
  #define DEQUE_OF_TYPE(type) \
  typedef struct __Node_##type { \
    struct __Node_##type *next; \
    struct __Node_##type *prev; \
    type value; \
  } Node_##type; \
  typedef struct __Deque_##type { \
    Node_##type* head; \
    Node_##type* tail; \
    size_t size; \
  } Deque_##type; \
  Deque_##type* deque_##type##_create() { \
    Deque_##type* result = malloc(sizeof(Deque_##type)); \
    result->head = result->tail = NULL; \
    result->size = 0; \
    return result; \
  } \
  Node_##type* node_##type##_create(type value) { \
    Node_##type* result = malloc(sizeof(Node_##type)); \
    result->next = NULL; \
    result->prev = NULL; \
    result->value = value; \
    return result; \
  } \
  void deque_##type##_push(Deque_##type* deque, type value) { \
    Node_##type* pushed = node_##type##_create(value); \
    if(deque->tail == NULL && deque->head == NULL) { \
      deque->head = deque->tail = pushed; \
    } else if(deque->head == deque->tail) { \
      pushed->prev = deque->head; \
      deque->tail = deque->head->next = pushed; \
    } else { \
      pushed->prev = deque->tail; \
      deque->tail->next = pushed; \
      deque->tail = pushed; \
    } \
    deque->size++; \
  }  \
  typedef struct __Deque_##type##_result { \
    type value; \
    bool error; \
  } Deque_##type##_result; \
  Deque_##type##_result deque_##type##_pop(Deque_##type* deque) { \
    if(deque->tail == NULL && deque->head == NULL) { \
      Deque_##type##_result result = { .error = true }; \
      return result; \
    } else { \
      Node_##type* popped = deque->tail; \
      deque->tail = popped->prev; \
      deque->tail->next = NULL; \
      type value = popped->value; \
      free(popped); \
      deque->size--; \
      Deque_##type##_result result = { value, true }; \
      return result; \
    } \
  } \
  void deque_##type##_enqueue(Deque_##type* deque, type value) { \
    Node_##type* enqueued = node_##type##_create(value); \
    if(deque->tail == NULL && deque->head == NULL) { \
      deque->head = deque->tail = enqueued; \
    } else if(deque->head == deque->tail) { \
      enqueued->next = deque->head; \
      deque->head = deque->tail->prev = enqueued; \
    } else { \
      enqueued->next = deque->head; \
      deque->head->prev = enqueued; \
      deque->head = enqueued; \
    } \
    deque->size++; \
  } \
  Deque_##type##_result deque_##type##_dequeue(Deque_##type* deque) { \
    return deque_##type##_pop(deque); \
  } \
  type* deque_##type##_array(Deque_##type* deque) { \
    type* result = malloc(sizeof(type) * deque->size); \
    int count = 0; \
    for(Node_##type* n = deque->head; n != NULL; n = n->next) { \
      result[count++] = n->value; \
    } \
    return result; \
  }
  
  DEQUE_OF_TYPE(int)
  DEQUE_OF_TYPE(char)
  
  void print_deque_int(Deque_int* deque) {
    int* array = deque_int_array(deque);
    printf("[");
    if(deque->size > 0) printf("%d", array[0]);
    for(int i = 1; i < deque->size; i++) {
      printf(",%d", array[i]);
    }
    printf("]\n");
    free(array);
  }
  
  void print_deque_char(Deque_char* deque) {
    char* array = deque_char_array(deque);
    if(deque->size > 0) for(int i = 0; i < deque->size; i++) {
      printf("%c", array[i]);
    }
    printf("\n");
    free(array);
  }
  
  int main(int argc, char** argv) {
    Deque_int* deque = deque_int_create();
    deque_int_push(deque, 5);
    print_deque_int(deque);
  
    deque_int_enqueue(deque, 6);
    print_deque_int(deque);
  
    deque_int_push(deque, 7);
    print_deque_int(deque);
  
    printf("%d\n", deque_int_pop(deque).value);
    printf("%d\n", deque_int_dequeue(deque).value);
  
    Deque_char* char_deque = deque_char_create();
    deque_char_push(char_deque, 'b');
    deque_char_push(char_deque,'c');
    deque_char_enqueue(char_deque, 'a');
    print_deque_char(char_deque);
  
    return 0;
  }
  

  The most amazing thing: no warnings even with -Wall and -pedantic. :D

  reply permalink

• Anonymous - 10 years, 8 months ago

  Oh man this looks pretty intense

  reply permalink

• Pegleg - 10 years, 8 months ago

  Python how you so sexy?

  list = []
  def push(item):
      list.insert(0, item)
      print('Pushed',item)
  
  def pop():
      if(len(list)<=0):
          print('List empty!')
          return
      temp = list.pop(0)
      print('Poppd',temp)
      return temp
  
  def enqueue(item):
      list.append(item)
      print('Qdd',item)
  
  def dequeue():
      if(len(list)<=0):
          print('List empty!')
          return
      temp = list.pop(0)
      print('poppedzz', temp)
      return temp
  

  reply permalink

• Mre64 - 10 years, 6 months ago

  /* Mre64 6/12/14

  «The Internet is a great way to get on the net.»
      - Bob Dole, Republican presidential candidate 
  

  */ import java.util.LinkedList;

  public class Struct {

  //use linkedList for the pop() push() like methods
  public static LinkedList<Integer> store = new LinkedList<Integer>();
  //static variable to hold removed items
  public static Integer keepNum;
  //Constructor
  Struct(LinkedList<Integer> store){
      Struct.store = store;
  }
  //push method
  public static void push(int pushN){
      store.addFirst(pushN);
      System.out.println(store.toString());
  }
  //pop method
  public static void pop(){
      store.pollLast();
      keepNum = store.getFirst();
      store.removeAll(store);
      store.add(keepNum);
      System.out.println(store.toString());
  }
  //enqueue method
  public static void enqueue(int enqueueN){
      store.addLast(enqueueN);
      System.out.println(store.toString());
  }
  //dequeue method
  public static void dequeue(){
      store.removeLast();
  }
  

  } /* Mre64 6/12/14

  «The Internet is a great way to get on the net.»
      - Bob Dole, Republican presidential candidate 
  

  */ import java.util.ArrayList; import java.util.LinkedList;

  public class StackQueues extends Struct {

  public static void main(String[] args) {
      //holds the list
      LinkedList<Integer> stack = new LinkedList<Integer>();
      //invokes new object from Struct class
      Struct store = new Struct(stack);
      //call functions
      store.push(5);
      store.enqueue(6);
      store.push(7);
      store.pop();
      store.dequeue();
  }
  

  }

  reply permalink

• Mre64 - 10 years, 6 months ago

  Edit comments would be great...

  reply permalink