Stacks and Queues

Objective

The goal of this lab is to gain experience with stack and queue data structures and their applications.

Introduction

In this lab, you will use stacks and queues to solve problems. To facilitate development, we will provide a dynamic array implementation of the Stack and Queue ADTs.

Download the lab starter files here:

Don't forget to download and customize your machine-specific makefile.

Here is a quick reference to the functions provided in dynarray.c:

typedef dynarray_t;                                     // dynamic array struct

/* Basic/common operations */

void   dynarray_init    (dynarray_t *a);                // initialize struct
void   dynarray_free    (dynarray_t *a);                // free struct
size_t dynarray_size    (dynarray_t *a);                // return element count
size_t dynarray_is_empty(dynarray_t *a);                // return true if empty

/* Stack operations */

void   dynarray_push(dynarray_t *a, data_t item);       // add to back
data_t dynarray_pop (dynarray_t *a);                    // remove from back
data_t dynarray_top (dynarray_t *a);                    // return back

/* Queue operations */

void   dynarray_enqueue(dynarray_t *a, data_t item);    // add to back
data_t dynarray_dequeue(dynarray_t *a);                 // remove from front
data_t dynarray_front  (dynarray_t *a);                 // return front

In addition, you may find the following functions from ctype.h useful in this lab:

  • int tolower(int c)

    Converts c to its lowercase equivalent. If no conversion is possible, the value returned is unchanged. NOTE: For the purposes of this lab, you may use this function as if it accepts and returns a char.

  • int isdigit(int c)

    Returns non-zero integer (true) if c is a decimal digit (0-9); otherwise it returns zero (false).

Part 1: Using Stacks and Queues

Write some code in the main method to accomplish the following tasks:

  1. Allocate and initialize a stack and queue. You may store these structures on either the stack or the heap, but make sure you free them appropriately.

  2. Add the letters 'a', 'b', 'c', and 'd' (in that order) to both the stack and the queue.

  3. Remove all items from the stack until it is empty and print them in the order that they are returned.

  4. Remove all items from the queue until it is empty and print them in the order that they are returned.

Compare the results from #3 and #4; how are they different?

Part 2: Palindromes

Use a stack and queue to implement a more powerful version of the is_palindrome() function from an earlier lab. As a reminder, this function implements simple palindome verification. Here is the signature and documentation for the function:

  • bool is_palindrome(char *text)

    Return true if text is a palindrome, false otherwise. A palindrome is a string that is identical to itself when reversed. For example, "madam", "dad", and "abba" are palindromes. Note: the empty string is a palindrome, as is every string of length one.

For this lab, you should make the function more flexible than the version you wrote for the earlier lab. Your new solution should ignore whitespace and punctuation, and all comparisons should be case-insensitive. Include some tests in your main function. Examples of valid palindromes:

  • ""
  • "a"
  • "aa"
  • "aaa"
  • "aba"
  • "abba"
  • "Taco cat"
  • "Madam, I'm Adam"
  • "A man, a plan, a canal: Panama"
  • "Doc, note: I dissent. A fast never prevents a fatness. I diet on cod."

Part 3: Postfix Evaluation

Postfix notation (sometimes called "Reverse Polish Notation" or "RPN") explicitly specifyies the operation order of a mathematical expression. Here are some examples of normal (infix) expressions followed by their postfix equivalents:

  • "1 + 2" == "1 2 +"
  • "3 - 1" == "3 1 -"
  • "2 * 3" == "2 3 *"
  • "3 + (4 * 5)" == "4 5 * 3 +"
  • "5 + ((1 + 2) * 4) - 3" == "5 1 2 + 4 * + 3 -"

Here is an algorithm for evaluating simple postfix expressions using a stack:

for each token in expression
    if token is a number
        push(token)
    if token is an operator <op>
        op2 = pop()
        op1 = pop()
        push(op1 <op> op2)
return pop()

Implement this algorithm for simple expressions (single-digit numbers only) by writing a function with the following signature:

  • int eval_postfix(char *expr)

    Return the value of evaluating 'expr' as a postfix expression. All operands should be one-digit decimal numbers, and three standard arithmetic operators (+, -, *) are supported. Operands and operators may be separated by spaces. If the the expression is invalid, the function should print an error and return -999.

HINT: You can convert a character c to its integer equivalent value using the following expression:

(int)(c-'0')

Include some tests in a main() function. Examples:

  • "1 2 +" = 3
  • "9 2 -" = 7
  • "2 3 *" = 6
  • "4 5 * 3 +" = 23
  • "5 1 2 + 4 * + 3 -" = 14

(Optional) Challenge Problem

Modify your eval_postfix function so that it works for multi-digit character literals.

HINT: You may wish to use the strtok function to split up the string around spaces, and the atoi function to convert strings to integers.