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

Stacks && Queues

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!

Permalink: http://problemotd.com/problem/stacks-queues/

Comments:

  • Kevin Benton - 3 years, 6 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 - 3 years, 6 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 - 3 years, 6 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 - 3 years, 6 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 - 3 years, 6 months ago

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

    reply permalink

  • Jt - 3 years, 6 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 - 3 years, 6 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 - 3 years, 6 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 - 3 years, 6 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 - 3 years, 6 months ago

    Oh man this looks pretty intense

    reply permalink

  • Pegleg - 3 years, 6 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 - 3 years, 4 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 - 3 years, 4 months ago

    Edit comments would be great...

    reply permalink

Content curated by @MaxBurstein