Assignment 2 – Stacks
Write pseudo-code not Java for problems requiring code. You are responsible for the
appropriate level of detail.
1. a) Use the operations push, pop, peek and empty to construct an operation which sets i to
the second element from the top of the stack, leaving the stack unchanged.
h = pop (s);
i = pop (s);
push (s, i);
push (s, h);
b) Use the operations push, pop, peek and empty to construct an operation which sets i to
the nth element from the top of the stack, leaving the stack without its top n elements. You are
given integer n.
for (elem = 1; elem < n; elem++)
pop (s);
i = pop (s);
2. Use the operations push, pop, peek and empty to construct an operation which sets i to the
bottom element of the stack, leaving the stack unchanged. (hint: use an auxiliary stack.)
(STACK s1, s2)
while (!empty (s1)) {
h = pop (s1);
push (s2, h);
}
i = h;
while (!empty (s2)) {
h = pop (s2);
push (s1, h);
}
b) Use the operations push, pop, peek and empty to construct an operation which sets i to
the third element from the bottom of the stack. The stack may be left changed.
(STACK s1, s2)
while (!empty (s1)) {
h = pop (s1);
push (s2, h);
}
for (elem = 1; elem <= 3; elem++)
i = pop (s2);
/* i will exit loop with value of 3rd element from bottom
of s1, the original stack */
, 3. Simulate the action of the algorithm for checking delimiters for each of these strings by
using a stack and showing the contents of the stack at each point. Do not write an algorithm.
a) {[A+B]-[(C-D)]
b) ((H) * {([J+K])})
4. Write an algorithm to determine whether an input character string is of the form
xCy
where x is a string consisting only of the letters ‘A’ and ‘B’ and y is the reverse of the x (i.e. if
x=”ABABBA” then y must equal “ABBABA”). At each point you may read only the next
character in the string, i.e. you must process the string on a left to right basis. You may not use
string functions.
while (char != C) {
push (stack, char);
char = nextchar;
Write pseudo-code not Java for problems requiring code. You are responsible for the
appropriate level of detail.
1. a) Use the operations push, pop, peek and empty to construct an operation which sets i to
the second element from the top of the stack, leaving the stack unchanged.
h = pop (s);
i = pop (s);
push (s, i);
push (s, h);
b) Use the operations push, pop, peek and empty to construct an operation which sets i to
the nth element from the top of the stack, leaving the stack without its top n elements. You are
given integer n.
for (elem = 1; elem < n; elem++)
pop (s);
i = pop (s);
2. Use the operations push, pop, peek and empty to construct an operation which sets i to the
bottom element of the stack, leaving the stack unchanged. (hint: use an auxiliary stack.)
(STACK s1, s2)
while (!empty (s1)) {
h = pop (s1);
push (s2, h);
}
i = h;
while (!empty (s2)) {
h = pop (s2);
push (s1, h);
}
b) Use the operations push, pop, peek and empty to construct an operation which sets i to
the third element from the bottom of the stack. The stack may be left changed.
(STACK s1, s2)
while (!empty (s1)) {
h = pop (s1);
push (s2, h);
}
for (elem = 1; elem <= 3; elem++)
i = pop (s2);
/* i will exit loop with value of 3rd element from bottom
of s1, the original stack */
, 3. Simulate the action of the algorithm for checking delimiters for each of these strings by
using a stack and showing the contents of the stack at each point. Do not write an algorithm.
a) {[A+B]-[(C-D)]
b) ((H) * {([J+K])})
4. Write an algorithm to determine whether an input character string is of the form
xCy
where x is a string consisting only of the letters ‘A’ and ‘B’ and y is the reverse of the x (i.e. if
x=”ABABBA” then y must equal “ABBABA”). At each point you may read only the next
character in the string, i.e. you must process the string on a left to right basis. You may not use
string functions.
while (char != C) {
push (stack, char);
char = nextchar;
