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. 

Implement a Queue with a maximum size of 5 elements using flowgorithm or a C program. The program must continuously prompt the user for an option:

add -if the user enters add, prompt the user to enter an integer and add it to the back of the queue.

remove -if the user enters remove, display the integer at the front of the queue and remove it

peek – If the user enters peek, display the integer at the front of the queue

exit – exits the program.

Use the following template in flowgorithm if necessary:

https://drive.google.com/file/d/1wFmReWDQbIYKV8z4kNXYvs9XarPIvnoo/view?usp=sharing

© 2020  Vedesh Kungebeharry. All rights reserved. 

Palindromes are words that are spelt the same way backward as they are forward.

Task

Create a program which accepts a string of text from the user and outputs whether or not the string is a palindrome. You may assume that the user always enters a single word for input, i.e no spaces are entered.

below are two examples of running the program. (User input is bolded)

You may use the code found in this post Stacks Implementations and Variations. A suitable example of a stack can be found in the zipped folder 05 U2 M1 S2 Stack-String ReversalErrorChecks.

Requirements

1. Create a stack which uses the datatype char and is managed by a variable top which stores the index of the top of the stack.
   
2. Use the stack to determine if an input string is a palindrome by first pushing all the characters of the string onto the stack, and then popping from the stack one at a time comparing each popped character to each character in the original string.
   
   That is, compare your first popped character to the 1st character of the string, your 2nd popped character to the 2nd character of the string….and so on until all characters are compared. If any comparison fails, then the string is not a palindrome. If all passes , then the word is a palindrome.
   

© 2020  Vedesh Kungebeharry. All rights reserved. 

NB: This post is intended for use within our class. It serves as a rough guide for our discussion on the implementation and use of a stack.

For this post there are 2 important requirements:

1. The prerequisite post which was an exercise in creating a stack from previously supplied code. It is imperative that you complete the tasks from that post found here: Stack Operations (Exercise)
   
2. A Code Packet that you must scrutinize. You can download it from the file link : U2 M1 S02 – Stack Implementations-CodeBackup.zip

Guide

Step 1

Assumption: Attempts were made to complete the tasks in Stack Operations (Exercise)

We now look at a sample attempt in flowgorithm (Flowcharting graphical programming language) found within 02 Flowgorithm Stack Exercise of the code packet labeled U2 M1 S2 – StackOperations-01 using size to keep track of top.

Note that this attempt does not use a pointer to the top of the stack; instead we keep track of the size of the stack , much like our implementation found here : Stacks.

It is important to recognize that keeping track of the size of a stack is NOT THE MOST POPULAR implementation.

Still, take some time (~10-15 mins) to observe how the operations for push, pop and peek are accomplished

Step 2

Look at a sample attempt in flowgorithm (Flowcharting graphical programming language) found within 02 Flowgorithm Stack Exercise of the code packet labeled U2 M1 S2 – StackOperations-02 using top instead of size.

In this attempt, we keep track of the index of the item stored at the top of the stack.

Keeping track of top is the most popular accepted way to implement a stack.

Take some time (~10-15 mins) to observe how the operations for push, pop and peek are accomplished, and observe the differenced from the previous sample attempt.

Step 3 – Coded attempt in C (Sample)

Scrutinize the code and run the program found in 03 U2 M1 S2 Stack SimpleExercise. Note that error checking is minimal, and when edge cases are encountered dummy values are returned, e.g as in when we try pushing to an already full stack ( see the push function from more detail )

Although this method works, it’s not the most elegant solution.

Step 4 – Simple Error checking/handling based on Step 3

If we scrutinize the code found in 03.1 U2 M1 S2 Stack SimpleExerciseErrorChecks we find that error messages are added to our push operation and we added the ability for our push operation to return a boolean value. Previously no values were returned, push was void.

However, we now return true if a successful push was made and false (along with an error message) if a failed push was made (e.g our stack was already full when push is called).

Note that peek and pop will always need to return data, and in this case dummy values in error conditions will suffice , but we ensure that error messages are also displayed.

Step 5

Moving on from our exercise we consider the following problem:

Create a program which demonstrates a function which reverses a string (character array) in place , i.e the data of the character array is directly manipulated. Prompt the user to enter a string and output the string in reverse.

The solution to this problem can be found in 04 U2 M1 S2 Stack-String Reversal.

Examine how the code in the main function works. Note that it uses push and pop only to achieve it’s task.

The stack used to implement the solution to this problem is similar to our simple stack with minimal error handling ; only this time our datatype is set to char.

Step 6

if we observe the code in 05 U2 M1 S2 Stack-String ReversalErrorChecks we see that the overall logic for data processing remains the same , only this time we implement some basic error handling techniques.

Previously Recorded Classes on this Topic

Stack Implementations and Variations (Live Class – 2025-09-11_09-59-29)

Updates to this post:

2025-09-17: Added section for “Previously Recorded Classes”

© 2020  Vedesh Kungebeharry. All rights reserved.