Post date: Jan 30, 2019 4:14:9 AM
Chapter 4 Stacks:
Stacks
Lab 4 – Stack
Objectives:
Learn How to Implement Stack using Doubly Linked List
Learn How to Use Stack
Examples:
1- Class TestIntegerLLStack shows how to use the LLStack implemented in the Lecture. It performs the following operations:
Push an element
Pop an element and print it
Get top element and print it
Print all elements in the stack
Clear the stack
Quit
2- Class ReverseString shows how you may use a stack to reverse a string
3- Class AddLargeIntegers shows how you may use stack to add large integers as discussed in the lecture
4- Class TestDelimiterMatching showa how stack can be used to check is an expression has matching brackets, ( ), [ ] or { }.
Tasks:
1. The given file DLL.java implements generic linked list as we saw in Lab03. It has been updated to include additional methods needed for Stack/Queue implementation: getLast(), and toString(). Similarly SLL.java from lab01 implements a Singly Linked List.
(a) Using these classes, implement two (2) classes, SLLStack and DLLStack, that represents a stack for processing any types of values using Singly Linked List and Doubly Linked List classes SLL and DLL. Note that the SLL class can be found in the lab 1.
(b) Write a test class, TestDoubleStack, that allows a user to perform the same operations as TestIntegerLLStack but using Double data type and the class DLL instead of java.utils.LinkedList.
(c) Write a test class, TestStudentStack, that allows a user to perform the same operations as in (b) above but using objects of type Student.
2. A simple algorithm to check if a string is a palindrome (reads the same either from left or from right: e.g: Madam) is as follows:
Scan through the string and store each character in a stack
Scan through the string the second time comparing each character with the next character pop off from the stack. If there is a mismatch at any point, the string is NOT a palindrome, otherwise it is a palindrome.
Use the DLLStack to write a program that reads a string from a user and displays a message indicating whether the string is a palindrome or not.
Assuming that a postfix expression consists of operands of single digits (0,1, .., 9), the binary operators *, /, %, +, and -, and possibly white-space characters. An algorithm to evaluate the postfix expression is given below:
Create an empty stack of Integer type.
Read postfix expression as a string ;
while(there are more characters in the string){
if(current character is an operand)
covert character to int and push in the stack;
else if(current character is an operator oprt){
operand1 = pop stack;
operand2 = pop stack;
result = operand2 oprt operand1;
push result in the stack;
}
}
pop result from the stack and print it;
Write a Java program that prompts for, and reads a postfix expression. It then uses the above algorithm to evaluate and print the value of the postfix expression.
Additional Exercises:
Reverse the order of elements on stack S
Using 2 additional stacks
Using 1 additional stack
using one additional stack and some additional non-array variables
Put the elements on the stack S in ascending order using 1 additional stack and some additional non-array variables
Transfer elements from stack S1 to stack S2 so that the elements from S2 are in the same order as on S1:
Using 1 additional stack
Using no additional stack but only some additional non-array variables