Brief Discussion on Stacks and Queues

Queues and stacks are two of the most fundamental data structures. Queues follow the First-in-first-out (FIFO) policy, and stacks follow the Last-in-first-out (LIFO) policy. Although they may look very different, they can be interconnected in some ways. In this blog, we will discuss how we can implement one structure with the other one by reviewing two corresponding implementations for the leetcode problem 232 and 225.

Implementing Queues

232. Implement Queue using Stacks

One common and natural way to implement queues is by using two stacks. One is for incoming elements, and the other is for releasing elements. Thanks to programmer Carl, the following gif explains the mechanism crystal clear.

Define Stack

Given its necessity, we define a stack first.

typedef struct {
    int* stack;
    int stack_size;
    int stack_capacity;
} Stack;

Stack* create_stack(int capacity) {
    Stack* stack = (Stack*) malloc(sizeof(Stack));
    stack->stack = malloc(sizeof(int) * capacity);
    stack->stack_size = 0;
    stack->stack_capacity = capacity;
    return stack;
}

void stack_push(Stack* obj, int x) {
    obj->stack[obj->stack_size++] = x;
}

void stack_pop(Stack* obj) {
    obj->stack_size--;
}

int stack_peek(Stack* obj) {
    return obj->stack[obj->stack_size - 1];
}

bool stack_empty(Stack* obj) {
    return obj->stack_size == 0;
}

void stack_free(Stack* obj) {
    free(obj);
}

The standard operations for the stack are push, pop, and peek. The above implementation would be considered a standard stack structure in C.

Build Queues

With stack defined, we can now implement our Queues. As we mentioned before, we need one stack to receive elements in the queue and another to release elements from the queue.

typedef struct {
    Stack* in_stack;
    Stack* out_stack;
} MyQueue;

Stack Communication within Queue

The core of this implementation is how the two stacks cooperate and communicate. The following implementation is one version that works. You can get an idea of how stacks deal with the inner traffic.

MyQueue* myQueueCreate() {
    MyQueue* queue = (MyQueue*) malloc(sizeof(MyQueue));
    queue->in_stack = create_stack(100);
    queue->out_stack = create_stack(100);
    return queue;
}

void in2out(MyQueue* queue) {
    while (!stack_empty(queue->in_stack)) {
        stack_push(queue->out_stack, stack_peek(queue->in_stack));
        stack_pop(queue->in_stack);
    }
}

void myQueuePush(MyQueue* obj, int x) {
    stack_push(obj->in_stack, x);
}

int myQueuePop(MyQueue* obj) {
    if (stack_empty(obj->out_stack)) in2out(obj);
    int x = stack_peek(obj->out_stack);
    stack_pop(obj->out_stack);
    return x;
}

int myQueuePeek(MyQueue* obj) {
    if (stack_empty(obj->out_stack)) in2out(obj);
    return stack_peek(obj->out_stack);
}

bool myQueueEmpty(MyQueue* obj) {
    return stack_empty(obj->in_stack) && stack_empty(obj->out_stack);
}

void myQueueFree(MyQueue* obj) {
    free(obj->in_stack);
    free(obj->out_stack);
}

Implementing Stacks

Practical ways to implement stacks are using Queues or Linked Lists. If you use queues, you will need to implement a queue with standard operations, including push, pop and top. The inner traffic of the queue implementation can be described as following

As we can see, queue2 is only a temporary container for queue1, making it a little awkward to implement a stack with queues. Don’t get me wrong. This approach works fine for sure. But a more natural and easier way to implement it is using the Linked Lists.

Define Linked Lists

The first step is to implement a linked list. The next node and its self value are two essential elements of the linked list. Therefore,

typedef struct stackListNode {
    struct stackListNode* next;
    int val;
}

Linked List Traffic

Three standard operations of a Stack are push, pop and top. Based on the starter code from leetcode, we can complete the code.

typedef struct {
    ListNode* top;
} MyStack;

MyStack* myStackCreate() {
    /* allocate memory for stack and initialize it to 0 */
    MyStack* stack = calloc(1, sizeof(MyStack));
    return stack;
}

void myStackPush(MyStack* obj, int x) {
    ListNode* node = (ListNode*) malloc(sizeof(ListNode));
    node->val = x;
    node->next = obj->top;
    obj->top = node;
}

int myStackPop(MyStack* obj) {
    int x = obj->top->val;
    obj->top = obj->top->next;
    /* if you do it this way, the memory leaks. The old top node is leaked. */
    return x;
}

int myStackTop(MyStack* obj) {
    return obj->top->val;
}

bool myStackEmpty(MyStack* obj) {
    return obj->top == NULL;
}

void myStackFree(MyStack* obj) {
    /* same way you free a linked list */
    while (obj->top) {
        ListNode* node = obj->top;
        obj->top = node->next;
        free(node);
    }
    free(obj);
}

Leak or Not?

As you may have probably noticed from my comment above, there is a memory leakage problem with that implementation. If we move obj->top pointer to its next node, you will have no problem passing all tests, even with better spatial utilizations, but you will leave the previous obj->top unfreed. For a language like Python, the kernel will recycle the unfreed objects. However, you will need to free those used objects manually for lower-level languages like C.

A myStackPop implementation with proper memory handling should look similar to this,

int myStackPop(MyStack* obj) {
    ListNode* node = (ListNode*) malloc(sizeof(ListNode));
    int x = node->val;
    obj->top = node->next;
    free(node);
    return x;
}

In this way, the old node will be recycled appropriately.

References

• 232.用栈实现队列
• 225.用队列实现栈