We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Data Structures
  3. Queues
  4. Queue using Two Stacks
  5. Discussions

Queue using Two Stacks

Sort by

recency

|

515 Discussions

|

  • pradeep_tarakar
     + 0 comments

    Approach: * take 2 stacks one for enque and another for deque. * if operation is enqueue simply push to first stack * if operation is dequeue - check if there are elements in 2nd stack if not copy all elements from 1st stack and pop the top. Otherwise simply pop 2nd stack top * if operation is front - follow above step instead of popping print the top.

    Gist is: stack 2 will have a top element to pop or print. We only copy stack 1 elements into stack 2 when it is empty.

    int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */   
    
    stack<int> st1; // for enqueue
    stack<int> st2; // for dequeue
    int num_of_queries = 0;
    
    cin >> num_of_queries;
    
    for(int i=0; i < num_of_queries; i++){
        int op;
        cin >> op;
        
        if(op == 1){
            int data;
            cin >> data;
            st1.push(data);
            continue;
        }
        if(op == 2){
           if(!st2.empty()){
             st2.pop();
           }else{
            while(!st1.empty()){
                st2.push(st1.top());
                st1.pop();
            }
            st2.pop();
           } 
           continue;
        }
        
        if(op == 3){
            if(!st2.empty()){
                cout << st2.top()<<endl;
            }else{
                while(!st1.empty()){
                    st2.push(st1.top());
                    st1.pop();
                }
                cout << st2.top() <<endl;
            }
        }
    }
    
    return 0;
}

  • Shahriarcodes8
     + 0 comments

    python solution:

    query =[]
number_of_queries = int(input())
for q in range(number_of_queries):
    operation = input().split()
    if len(operation) == 2:
        query.append(operation[1])
    elif len(operation) == 1 and operation[0] != '3':
        query.remove(query[0])
    elif operation[0] == '3':
        print(query[0])

  • murad_jmv
     + 0 comments

    Optimal pseudocode, if you resolved it but couple tests giving timout exception then, rewrite this to your preffered programming language:

    enQStack = new Stack()
deQStack = new Stack()

enqueue(num):
	# push all new elements to enqueue stack O(1)
	enQStack.push(num)

dequeue():
	# if dequeue stack has elements pop from it O(1)
	# else fill dequeue stack with elements from enqueue stack O(n), then pop from it
	if deQStack is empty:
		fillDeQStack()
	deQStack.pop()

peek():
	# if dequeue stack has elements peek from it O(1)
	# else fill dequeue stack with elements from enqueue stack O(n), then peek from it
	if deQStack is empty:
		fillDeQStack()
	deQStack.peek()

fillDeQStack():
	# fill dequeue stack with elements from enqueue stack O(n), dequeue = reversed enqueue
	while enQStack is not empty:
		deQStack.push(enQStack.pop())

  • dinothedinosaur1
     + 0 comments

    Python 3 solution:

    queue = []

number_of_queries = int(input())

for _ in range(number_of_queries):
    query_and_data = input()
    query_and_data_split = query_and_data.split()
    if len(query_and_data_split) == 2:
        queue += [int(query_and_data_split[1])]
    elif int(query_and_data_split[0]) == 2:
        queue = queue[1:]
    elif int(query_and_data_split[0]) == 3:
        print(queue[0])

  • kuro_ece
     + 0 comments

    C solution:

    #include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <stdint.h>


typedef struct {
    int type;
    int value;
} query_t;

typedef struct {
    int* stack;
    size_t tos;
    size_t size;
} stack_t;

typedef struct {
    stack_t* s1;
    stack_t* s2;
} queue_t;


void stack_init(stack_t* s, size_t size) {
    s->size = size;
    s->stack = malloc(sizeof(int) * size);
    s->tos = 0;
}

stack_t* stack_new(size_t size) {
    if(size < 2) {
        return NULL;
    }
    stack_t* s = malloc(sizeof(stack_t) * 1);
    stack_init(s, size);
    return s;
}

void stack_deinit(stack_t * s) {
    s->size = 0;
    s->tos = 0;
    free(s->stack);
}

void stack_destroy(stack_t* s) {
    stack_deinit(s);
    free(s);
}

static inline int stack_is_empty(stack_t* s) {
    return s->tos == 0;
}

static inline int stack_is_full(stack_t* s) {
    return s->tos == s->size;
}

#if 0
void stack_resize(stack_t* s, size_t new_size) {
    int* new_mem = malloc(sizeof(int) * new_size);
    memcpy(new_mem, s->stack, s->tos * sizeof(int));
    free(s->stack);
    s->stack = new_mem;
    s->size = new_size;
}

void stack_expand(stack_t* s) {
    stack_resize(s, s->size * 2);
}

void stack_shrink(stack_t* s) {
    if(s->size > 2) {
        stack_resize(s, s->size / 2);
    }
}
#endif /* 0 */

int stack_push(stack_t * s, int item) {
    /*
    if(s->tos > ((s->size * 3) / 4)) {
        stack_expand(s);
    }
    */
    if(stack_is_full(s)) {
        return 0;
    }
    s->stack[s->tos++] = item;
    return 1;
}

int stack_pop(stack_t* s, int* item) {
    if(stack_is_empty(s)) {
        return 0;
    }
    /*
    if(s->tos < (s->size / 4)) {
        stack_shrink(s);
    }
    */
    int temp = s->stack[--s->tos];
    if(item) {
        (*item) = temp;
    }
    return 1;
}

int stack_peek(stack_t* s, int* item) {
    if(stack_is_empty(s)) {
        return 0;
    }
    (*item) = s->stack[s->tos - 1];
    return 1;
}

void queue_init(queue_t* q, size_t size) {
    q->s1 = stack_new(size);
    q->s2 = stack_new(size);
}

queue_t* queue_new(size_t size) {
    queue_t* q = malloc(sizeof(queue_t) * 1);
    queue_init(q, size);
    return q;
}

void queue_deinit(queue_t* q) {
    stack_deinit(q->s1);
    stack_deinit(q->s2);
}

void queue_destroy(queue_t* q) {
    stack_destroy(q->s1);
    stack_destroy(q->s2);
    free(q);
}

int queue_is_empty(queue_t* q) {
    return stack_is_empty(q->s1) && stack_is_empty(q->s2);
}

int queue_push(queue_t * q, int item) {
    return stack_push(q->s1, item);
}

int queue_pop(queue_t* q, int * item) {
    if(stack_is_empty(q->s2)) {
        while(!stack_is_empty(q->s1)) {
            int temp = 0;
            stack_pop(q->s1, &temp);
            stack_push(q->s2, temp);
        }
    }
    return stack_pop(q->s2, item);
}

int queue_peek(queue_t* q, int* item) {
    if(stack_is_empty(q->s2)) {
        while(!stack_is_empty(q->s1)) {
            int temp = 0;
            stack_pop(q->s1, &temp);
            stack_push(q->s2, temp);
        }
    }
    return stack_peek(q->s2, item);
}

int main() {
    uint32_t num_queries = 0;
    query_t * queries = NULL;
    char buffer[16] = {0};
    int read_chars = 0;
    
    fgets(buffer, sizeof(buffer) - 1, stdin);
    sscanf(buffer, "%u", &num_queries);
    
    queries = malloc(sizeof(query_t) * num_queries);
    
    for(size_t i = 0; i < num_queries; ++i) {
        fgets(buffer, sizeof(buffer), stdin);
        read_chars = sscanf(buffer, "%d", &queries[i].type);
        if(queries[i].type == 1) {
            sscanf(&buffer[read_chars], "%d", &queries[i].value);
        }
        /* printf(">>> %s", buffer); */
    }
    
    /*
    for(size_t i = 0; i < num_queries; ++i) {
        printf("%d ", queries[i].type);
        if(queries[i].type == 1) {
            printf(": %d", queries[i].value);
        }
        printf("\n");
    }
    */
    
    queue_t * queue = queue_new(100000);
    for(size_t q = 0; q < num_queries; ++q) {
        if(queries[q].type == 1) {
            queue_push(queue, queries[q].value);
            
        } else if(queries[q].type == 2) {
            queue_pop(queue, NULL);
            
        } else {
            int item = 0;
            queue_peek(queue, &item);
            printf("%d\n", item);
        }
    }
    
    queue_destroy(queue);
    free(queries);
    
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */    
    return 0;
}