This post is intended for use in class and review. In this lesson we will observe some multiple choice question examples to provoke thoughts on the fundamental principles governing stack and queue operations.

Note that the multiple choice questions are not included on this website.

Discussion: Stacks and Queues

If a stack is implemented using a one-dimensional array and the top of the stack is always found at location 0 in the array, how would you implement push and pop?

That is, at the end of any push or pop operation, the top of the stack is stored at location 0.

Write separate algorithms for your push and pop operations.

After considering the scenario above do you think it’s possible to implement a stack using the wrap-around technique (that was used in the implementation of a queue ) to omit the intermediate copying of elements? Consider this scenario where the first element that was pushed onto the stack goes into location 0, and every time a pop operation occurs top is incremented (unless the stack is empty) , and every time a push operation occurs top is decremented.

Justify your conclusion.

Write an algorithm which can be used to reverse the elements of a queue by using a stack. Accomplish this task by only using valid stack and queue operations.

Assuming you are required to write a c program that must use two separate stacks and five separate queues , what modifications would you need to make to the coded implementations that will already demonstrated in class.

Write the algorithm for the dequeue operation in a traditional queue with no wrap around, i.e every time an element is dequeued , all elements of are copied down one location such that location 0 in the array stores the new head of the queue.

© 2020  Vedesh Kungebeharry. All rights reserved. 

Implementation using flowgorithm

Download the file here: https://drive.google.com/file/d/1adiH9SG9vbXVNBydWC5tKR1_9i9y9ZPj/view?usp=sharing

Coded Implementation in C

Code is split into 3 files:

main.c

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

int main()
{
    char userInput[5];
    int data = -9999;



    puts("\nEnter a valid command: add, remove, peek , exit\n");
    scanf("%s", userInput);
    while(strcmp("exit",userInput)!=0)
    {
        if (strcmp("add",userInput)==0)
        {
            puts("\nEnter data to add to the end of the queue\n");
            scanf("%d", &data);
            enqueue(data);
        }
        else if (strcmp("remove",userInput)==0)
        {
            data = dequeue();
            printf("\nremoved %d from the front of the queue\n",data);
        }
        else if (strcmp("peek",userInput)==0)
        {
            data = peek();
            printf("\npeeking at front : %d\n",data);
        }
        else
        {
            puts("\nInvalid command entered. Ensure that your command is in lowercase\n");
        }

        puts("\nEnter a valid command: add, remove, peek , exit\n");
        scanf("%s", userInput);
    }
    puts("\nExiting Program...\n");



    return 0;
}

Queue.h

#include <stdio.h>
#ifndef QUEUE_H_INCLUDED
#define QUEUE_H_INCLUDED

void enqueue(int newData);
int dequeue();
int peek();



#endif // QUEUE_H_INCLUDED

Queue.c

#define MAX_SIZE 5

int sizeOfQueue = 0;
int head = 0;
int tail = -1;

int queueData[MAX_SIZE];



void enqueue(int newData)
{
    if (sizeOfQueue==MAX_SIZE)
        puts("Error in \"void enqueue(int newData)\". Queue is full" );
    else
    {
        queueData[++tail]= newData;
        sizeOfQueue++;
    }


}

int dequeue()
{
    int result=-999;
    if (sizeOfQueue==0)
        puts("error in \"int dequeue()\". Queue is empty, -999 returned");
    else
    {
        result=queueData[head++];
        sizeOfQueue--;
    }
    return result;

}

int peek()
{
    int result=-999;
    if (sizeOfQueue==0)
        puts("error in \"int peek()\". Queue is empty, -999 returned");
    else
        result=queueData[head];


    return result;

}

© 2020  Vedesh Kungebeharry. All rights reserved.