Exercise 13.3 (Completed)

1. (Review) State whether a stack is appropriate for each of the following tasks, and indicate why
or why not:
a. A word-processing program must remember a line of up to 80 characters. Pressing the
Backspace key deletes the previous character, and pressing Ctrl+Backspace deletes the
entire line. Users must be able to undo deletion operations.

Yes, because the program can remove character and lines in a LIFO fashion.

b. Customers must wait one to three months for delivery of their new cars. The dealer creates
a list to determine the “fair” order in which customers should get their cars; the list is prepared
in the order in which customers placed their requests for a new car.

No, a because this program works in a FIFO fashion.

c. You’re required to search downward in a pile of magazines to locate the issue for last
January. Each magazine was placed on the pile as soon as it was received.

Yes, because the stack can be used in the LIFO fashion.

d. A programming team accepts jobs and prioritizes them on the basis of urgency.

Yes, because the jobs can be stacked after being prioritized.

e. A line forms at a bus stop.

No, because a line for a bus stop works like in a FIFO fashion.

2. (Practice) Enter and run Program 13.3.

//Done!!

#include <iostream>
#include <deque>
#include <string>
#include <cctype>
using namespace std;
int main()
{
  string name;
  deque<string> stack;
  cout << “Enter as many names as you want, one per line” << endl;
  cout << “To stop enter a single x” << endl;
  while(true)
  {
    cout << “Enter a name (or x to stop): “;
    getline(cin, name);
    if (tolower(name.at(0)) == 'x') break;
    stack.push_front(name);
  }
  cout << “\nThe names in the stack are:\n”;
  // pop names from the stack
  while(!stack.empty())
  {
    name = stack.front();  // retrieve the name
    stack.pop_front();     // pop name from the stack
    cout << name << endl;
  }
  return 0;
}

3. (Modify) Modify Program 13.3 to implement a stack of integers rather than a stack of strings.

#include "stdafx.h" 
#include <iostream>
#include <string>
#include <deque>
#include <cctype>
using namespace std;
int main()
{
	int num;
	deque<int> stack;
	cout << "Enter as many names as you want, one per line" << endl;
	cout << "To stop enter a single x" << endl;
	while (true)
	{
		cout << "Enter a name(or x to stop) : ";
		cin >> num;
		if (num == 100) break;
		stack.push_front(num);
	}
	cout << "\nThe names in the stack are : \n";
	// pop names from the stack
	while (!stack.empty())
	{
		num = stack.front();  // retrieve the name
		stack.pop_front();     // pop name from the stack
		cout << num << endl;
	}
	system("PAUSE");
	return 0;
}

4. (Modify) Modify Program 13.3 to instantiate three stacks of digits named digits1, digits2,
and digits3. Initialize digits1 to contain the digits 9, 8, 5, and 2, which is the number 2589
in reverse order. Similarly, the digits2 stack should be initialized to contain the digits 3, 1, 5,
and 7, which is the number 7513 in reverse order. Calculate and place the sum of these two
numbers in the digits3 stack. This sum should be obtained by popping objects from
digits1 and digits2 and adding them together with a variable named carry, which is initialized
to 0. If the sum of the two popped objects and carry doesn’t exceed 10, the sum
should be pushed onto digits3 and carry should be set to 0; otherwise, carry should be set
to 1, and the units digit of the sum should be pushed onto the digits3 stack.

#include "stdafx.h" 
#include <iostream>
#include <deque>
#include <string>
#include <cctype>
#include <stack>
using namespace std;

int add(int a, int b);

int main()
{
	int a, b, c;
	stack<int> digits1, digits2, digits3;
	stack<char> operand;
	digits1.push(9);
	operand.push('+');
	digits1.push(8);
	operand.push('+');
	digits1.push(5);
	operand.push('+');
	digits1.push(2);

	digits2.push(3);
	digits2.push(1);
	digits2.push(5);
	digits2.push(7);

	while (!digits1.empty()){

		if (operand.top() == '+'){
			a = digits1.top();
			digits1.pop();
			b = digits2.top();
			//cout << a << '+' << b << endl;
			c = add(a, b);
			if (c > 10){
				int carry = 1;
			digits3.push(c + carry);
		}
			else if(c < 10){
				digits3.push(c);
			}
		cout << digits3.top() << endl;
	}
}
	system("PAUSE");
	return 0;
}
	
int add(int a, int b){
	int x;
	x = a + b;
	return x;
}


5. (Program) Write a C++ program that allows a user to enter a maximum of 100 integers in a
stack object. Then have the program do the following:
a. Reverse the stack’s contents into a second stack of integers.
b. Using two additional stacks, reverse the contents in the original stack. For example, if the
original stack contains the integers 1, 2, 3, and 4, it should contain the integers 4, 3, 2, and 1
at the end of the program.

#include "stdafx.h" 
#include<stdio.h>
#include<stdlib.h>
#include <iostream>
#define bool int

using namespace std;
/* structure of a stack node */
struct sNode
{
	char data;
	struct sNode *next;
};

/* Function Prototypes */
void push(struct sNode** top_ref, int new_data);
int pop(struct sNode** top_ref);
bool isEmpty(struct sNode* top);
void print(struct sNode* top);

// Below is a recursive function that inserts an element
// at the bottom of a stack.
void insertAtBottom(struct sNode** top_ref, int item)
{
	if (isEmpty(*top_ref))
		push(top_ref, item);
	else
	{
		int temp = pop(top_ref);
		insertAtBottom(top_ref, item);

	
		push(top_ref, temp);
	}
}

// Below is the function that reverses the given stack using
// insertAtBottom()
void reverse(struct sNode** top_ref)
{
	if (!isEmpty(*top_ref))
	{
	
		int temp = pop(top_ref);
		reverse(top_ref);

		insertAtBottom(top_ref, temp);
	}
}

/* Driveer program to test above functions */
int main()
{
	int j = 0;
	struct sNode *s = NULL;
	int MAX;
	cout << "Enter MAX number of elements" << endl;
	cin >> MAX;
	for (int i = 0; i < MAX; i++){
		if (MAX > 100){
			cout << "Not possible" << endl;
			break;
		}
		cin >> i;
		push(&s, i);
	
}

	printf("\n Original Stack ");
	print(s);
	reverse(&s);
	printf("\n Reversed Stack ");
	print(s);
	return 0;
}

/* Function to check if the stack is empty */
bool isEmpty(struct sNode* top)
{
	return (top == NULL) ? 1 : 0;
}

/* Function to push an item to stack*/
void push(struct sNode** top_ref, int new_data)
{
	
	struct sNode* new_node =
		(struct sNode*) malloc(sizeof(struct sNode));

	if (new_node == NULL)
	{
		printf("Stack overflow \n");
		exit(0);
	}

	new_node->data = new_data;

	new_node->next = (*top_ref);

	(*top_ref) = new_node;
}

/* Function to pop an item from stack*/
int pop(struct sNode** top_ref)
{
	char res;
	struct sNode *top;

	if (*top_ref == NULL)
	{
		printf("Stack overflow \n");
		exit(0);
	}
	else
	{
		top = *top_ref;
		res = top->data;
		*top_ref = top->next;
		free(top);
		return res;
	}
}

void print(struct sNode* top)
{
	printf("\n");
	while (top != NULL)
	{
		printf(" %d ", top->data);
		top = top->next;
	}
	system("PAUSE");
}

6. (Program) Write a C++ program that allows a user to enter a maximum of 50 characters in a
stack object. Then have the program sort the stack contents in increasing order. For example,
if the stack’s contents are initially D, E, A, and B, its final contents are A, B, D, and E.

#include "stdafx.h" 
#include <stdio.h>
#include <stdlib.h>
#include <iostream>

// Stack is represented using linked list
typedef struct stack
{
	char data;
	struct stack *next;
};

// Utility function to initialize stack
void initStack(struct stack **s)
{
	*s = NULL;
}

// Utility function to chcek if stack is empty
char isEmpty(struct stack *s)
{
	if (s == NULL)
		return 1;
	return 0;
}

// Utility function to push an item to stack
void push(struct stack **s, char x)
{
	struct stack *p = (struct stack *)malloc(sizeof(*p));

	if (p == NULL)
	{
		fprintf(stderr, "Memory allocation failed.\n");
		return;
	}

	p->data = x;
	p->next = *s;
	*s = p;
}

// Utility function to remove an item from stack
char pop(struct stack **s)
{
	char x;
	struct stack *temp;

	x = (*s)->data;
	temp = *s;
	(*s) = (*s)->next;
	free(temp);

	return x;
}

// Function to find top item
char top(struct stack *s)
{
	return (s->data);
}

// Recursive function to insert an item x in sorted way
void sortedInsert(struct stack **s, char x)
{
	// Base case: Either stack is empty or newly inserted
	// item is greater than top (more than all existing)
	if (isEmpty(*s) || x < top(*s))
	{
		push(s, x);
		return;
	}

	// If top is greater, remove the top item and recur
	char temp = pop(s);
	sortedInsert(s, x);

	// Put back the top item removed earlier
	push(s, temp);
}

// Function to sort stack
void sortStack(struct stack **s)
{
	// If stack is not empty
	if (!isEmpty(*s))
	{
		// Remove the top item
		char x = pop(s);

		// Sort remaining stack
		sortStack(s);

		// Push the top item back in sorted stack
		sortedInsert(s, x);
	}
}

// Utility function to prchar contents of stack
void printStack(struct stack *s)
{
	while (s)
	{
		printf("%c ", s->data);
		s = s->next;
	}
	printf("\n");
}

// Driver Program
int main(void)
{
	struct stack *top;

	initStack(&top);
	
	int MAX;
	char letter;
	std::cout << "Enter MAX number of elements" << std::endl;
	std::cin >> MAX;

	for (int i = 0; i < MAX; i++){

		if (MAX > 50){
			std::cout << "Not possible" << std:: endl;
			break;
		}

		std::cin >> letter;
		push(&top, letter);
	}

	printf("Stack elements before sorting:\n");
	printStack(top);
	sortStack(&top);
	printf("\n\n");

	printf("Stack elements after sorting:\n");
	printStack(top);

	system("PAUSE");
	return 0;
}