Question

Stacks

There are two main operations associated with stacks;

1) putting things on the stack which is referred to as push,

2) taking things from the stack which is referred to as pop.  

We can create a stack using linked lists if we force ourselves to insert and remove nodes only at the top of the list. One use of a stack is when you want to write a word backward. In that case, you will read the letters of the word one-by-one and as you read them will push them onto a stack. Once all letters are pushed onto the stack, then pop them back one-by-one. This will produce the letters of the word in reverse order.

Give the definition of the member function push of the class Stack.

Given the definition of the copy constructor for the class Stack.

Write a program that implements a stack. Your program will ask users to input a word letter-by-letter and then displays the word backward. Please note that you are working with letters to build the stack, thus when you read the word, you will push the letters onto the stack and when you write them, you will pop those letters one-by-one.

Answer 1

C++ Program:

/* C++ Program that implements Stack using Linked List */
#include <iostream>

using namespace std;

//class definition
class Node
{
    private:
        //Data variables
        char data;
        Node *head;
        Node *next;

    public:

        //Constructor
        Node()
        {
            data = 0;
            next = NULL;
            head = NULL;
        }

        //Push operation
        void push(char ch)
        {
            Node *temp, *current;

            //If list is empty
            if(head == NULL)
            {
                //Creating a new node and naming it as head
                head = new Node();
                head->data = ch;
                head->next = NULL;
            }
            else
            {
                temp = head;

                //Moving till end of list
                while(temp->next!=NULL)
                    temp = temp->next;

                //Adding new node at the end of the list
                current = new Node();
                current->data = ch;
                current->next = NULL;

                temp->next = current;
            }
        }

        //Function that removes an element from list
        char pop()
        {
            char popped;
            Node *temp, *prev;

            temp = head;

            //Only one element
            if(temp == NULL)
            {
                //Updating pointers
                head = NULL;
                delete head;
            }
            //More than one node
            else
            {
                //Iterate till end of list
                while(temp->next != NULL)
                {
                    //Holding reference of previous node
                    prev = temp;

                    //Moving to next node
                    temp = temp->next;
                }

                //Data that is going to be popped
                popped = temp->data;

                //Updating pointers
                prev->next = NULL;

                //Deleting node
                if(temp != NULL)
                    delete temp;
            }

            return popped;
        }
};

//Main function
int main()
{
    char ch = ' ';

    int cnt = 0;

    Node stackObj;

    //Prompting user
    cout << "\n Enter word character by character (Type : to mark end of string): ";

    //Reading character
    cin >> ch;

    //Reading character by character
    while(ch != ':')
    {
        //Pushing elements to stack
        stackObj.push(ch);

        cnt++;

        //Reading character
        cin >> ch;
    }

    cout << "\n In reverse order: ";

    //Popping elements from stack
    while(cnt > 0)
    {
        //Printing popped element
        cout << stackObj.pop();

        //Decrementing count
        cnt --;
    }

    cout << endl << endl;
    return 0;
}

__________________________________________________________________________________________________

Sample Output:

CATClstackLinkedList bin DebugistackLinkedList.exe Enter word character by character (Typeto mark end of string): computers: In reverse order: sretupmoc Process returned o (oxo) execution time 5.597 S Press any key to continue.