Day 15: Stacks

Introduction

Want to learn more about stacks, click here!

Warmup Question

More Palindromes!: use a stack to determine if a string is a pailindrome

Input: abracadabra

Output: yes

Constraints:

• ???
• ??

      public boolean isPalindrome(String str) {
          Stack<Character> stack = new Stack<Character>();
          int n = str.length();
          for (int i = 0; i < n; i++) 
              stack.push(str.charAt(i));
        
          StringBuilder reversed = new StringBuilder();

          while (!stack.isEmpty())
               reversed.append(stack.pop());
          
          return (str.equals(reversed));
      }

Discussion

Question 1

Linked list and Stack: print reversed linkedlist using stack

Input: 1->2->3->4

Output: 4 3 2 1

Constraints:

• ???
• ??

      class Node {
          int data;
          Node next;

          Node(int data, Node next) {
              this.data = data;
              this.next = next;
          }
      }
      

      public void linkedStackPrinter(Node head) {
          Stack<Integer> stack = new Stack<Integer>();
          while (head != null) {
               stack.push(head.data);
               head = head.next;
          }

          while (!stack.isEmpty())
               System.out.print(stack.pop());
      }

Discussion

Question 2

Trees and Stack:

Input: 1->2->3->4

Output: 4 3 2 1

Constraints:

• ???
• ??

      class Node 
      {
          int data;
          Node left, right;

          Node(int data) {
            this.data = data;
          }
      }

      public void treeStackPrinter(Node head) {
          Stack<Node> first = new Stack<>();
          Stack<Node> second = new Stack<>();
          first.push(head);
          while (first != null || second != null) {
              while (first != null) {
                  Node cur = first.pop();
                  System.out.print(cur.data);
                  second.push(head.left);
                  second.push(head.right);
              }
              while (second != null) {
                  Node cur = second.pop();
                  first.push(cur);
            }

          while (!stack.isEmpty())
               System.out.print(stack.pop());
      }

Discussion

---

Previous:
Day 14: Hashmaps Part 2

Next Post:
Day 16: Stacks Continued

return to archives