Problem of the Day -- Stacks && Queues

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 - 10 years 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 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 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 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 ago
I'll refactor and post it again. Thaks klm. :-)

reply permalink

Jt - 10 years 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 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 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 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 ago
Oh man this looks pretty intense

reply permalink

Pegleg - 10 years 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 - 9 years, 10 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 - 9 years, 10 months ago

Edit comments would be great...

reply permalink

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

Stacks && Queues

Comments:

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