# Problem of the DayA 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!

• Kevin Benton - 3 years, 11 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()
``````
• Sanket Apte - 3 years, 11 months ago

public class StackQueue<T> {

``````private LinkedList<T> stackQueue;

public StackQueue() {
}

public void push(T object){
System.out.println(stackQueue);
}

public void enqueue(T 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();

}
``````

}

• klm - 3 years, 11 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)?

• Sanket Apte - 3 years, 11 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.

• Sanket Apte - 3 years, 11 months ago

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

• Jt - 3 years, 11 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");
}
}

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;
}
}
}
``````
• Jt - 3 years, 11 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");
}
}

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();
}
}
}
``````
• Bumbleguppy - 3 years, 11 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;
}
};

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.

• Hueho - 3 years, 11 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* 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) { \
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) { \
deque->head = deque->tail->prev = enqueued; \
} else { \
} \
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

• Anonymous - 3 years, 11 months ago

Oh man this looks pretty intense

• Pegleg - 3 years, 11 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
``````
• - 3 years, 9 months ago

/* Mre64 6/12/14

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

public class Struct {

``````//use linkedList for the pop() push() like methods
//static variable to hold removed items
public static Integer keepNum;
//Constructor
Struct.store = store;
}
//push method
public static void push(int pushN){
System.out.println(store.toString());
}
//pop method
public static void pop(){
store.pollLast();
keepNum = store.getFirst();
store.removeAll(store);
System.out.println(store.toString());
}
//enqueue method
public static void enqueue(int 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
``````

public class StackQueues extends Struct {

``````public static void main(String[] args) {
//holds the list
//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();
}
``````

}

• - 3 years, 9 months ago