How do I determine the size, first STACK in java and delete data in between the STACK

Question

I have 3 books from "A" to "C". How do I display them using a Stack, and then display its size. Also how do I delete book "B" and then be able to display the size again?

This is my code so far:

import java.util.*;
public class test_stack {
    public static void main (String[] args){

        Stack<String> stack = new Stack<String>();
        stack.push(“a”);
        printStack(stack);
        stack.push(“b”);
        printStack(stack);
        stack.push(“c”);
        printStack(stack);

        stack.pop();
        printStack(stack);
        stack.pop();
        printStack(stack);
        stack.pop();
        printStack(stack);
    }

    private static void printStack(Stack<String> s){
        if(s.isEmpty())
            System.out.printIn(“empty stack”);
        else
            System.out.printf(“% s TOP\n”, s);
    }

}

The output I'm getting is :

[a] TOP
[a, b] TOP
[a, b, c] TOP
[a, b] TOP
[a] TOP
empty stack

I want to achieve:

[a,b,c] TOP
[a,c] TOP
empty stack

Answer 1

Here is the implementation of Stack using LinkedList using adapter design pattern, you have to both push/pop at either head or tail to get Stack

public class StackLL<E> {

    private LinkedList<E> list;

    public StackLL() {
        list = new LinkedList<>();
    }

    public void push(E e) {
        list.addFirst(e);
    }

    public E pop(E e) {
        Iterator<E> it = list.descendingIterator(); // list.iterator()
        while (it.hasNext()) {
            E ele = it.next();
            if (ele == e) {
                it.remove();
                break;
            }
        }
        return null;
    }

    public E pop() {
        return list.removeFirst();
    }

    public int size() {
        return list.size();
    }

    public void print() {
        System.out.println(list);
    }
}

In this implementation the underlying data structure is still a double linked list, so you can have your custom methods to do some special operations, in your case it is to search and delete an element, so I have overloaded pop method with an element which is to be deleted, it does an iteration and deletes the matching one element else returns null.

public static void main(String[] args) {
    StackLL<String> stack = new StackLL<>();
    stack.push("a");
    stack.push("b");
    stack.push("c");
    stack.print();
    stack.pop("b");
    stack.print();
    stack.pop("b");
}

Output

[c, b, a]
[c, a]

In case if you want to delete mid element, you can simply have an Element as member variable, after every 2 pushes you can increment it one position up also after every 2 pops you can decrement one position down with just O(1) complexity.

Answer 2

You can create a second temporary stack to hold the values above the element you want to remove:

Stack<String> stack = new Stack<String>();
stack.push("a");
stack.push("b");
stack.push("c");

// Pop the elements from the original stack onto
// the temporary stack.
Stack<String> temp = new Stack<String>();
while (!stack.isEmpty()) {
    String top = stack.pop();
    if (top.equals("b")) {
        break;
    }
    temp.push(top);
}

// Pop the elements from the temporary stack
// back into the original stack. This preserves
// the original order.
while (!temp.isEmpty()) {
    stack.push(temp.pop());
}

Answer 3

Though I would recommend you to use a different data structure like linked list if you want to delete from middle because that's what linked lists are for. You should NOT AT ALL use stacks if the requirement is to delete an element from middle. But since the question asks for it, then you can introduce a method deleteFrom() as displayed below.

This method will take two arguments, the stack and the object to be deleted and if that object is present in the stack, then it would be deleted.

Output

[a] TOP
[a, b] TOP
[a, b, c] TOP

After calling deleteFrom(stack, "b")
[a, c] TOP

deleteFrom() method code:

public static Stack<String> deleteFrom(Stack<String> stack, String obj) {
    if (stack.search(obj) == -1) {
        System.out.println("Element doesn't exists in stack.");
        return stack;
    }
    Stack<String> stack2 = new Stack<String>();
    while (stack.search(obj) != -1)
        stack2.push(stack.pop());
    stack2.pop();
    while (stack2.size() != 0)
        stack.push(stack2.pop());
    return stack;
}

---

The final code would look like:

import java.util.*;

public class HelloWorld {

    public static void main(String[] args) {

        Stack<String> stack = new Stack<String>();
        stack.push("a");
        printStack(stack);
        stack.push("b");
        printStack(stack);
        stack.push("c");
        printStack(stack);

        stack = deleteFrom(stack, "b");
        System.out.println("After calling deleteFrom(stack, \"b\")");
        printStack(stack);
    }

    private static void printStack(Stack<String> s) {
        if (s.isEmpty()) {
            System.out.println("empty stack");
        } else {
            System.out.printf("%s TOP\n", s);
        }
    }

    public static Stack<String> deleteFrom(Stack<String> stack, String obj) {
        if (stack.search(obj) == -1) {
            System.out.println("Element doesn't exists in stack.");
            return stack;
        }
        Stack<String> stack2 = new Stack<String>();
        while (stack.search(obj) != -1)
            stack2.push(stack.pop());
        stack2.pop();
        while (stack2.size() != 0)
            stack.push(stack2.pop());
        return stack;
    }

}

Answer 4

In order to remove b from your stack, you would need to pop all the books off the stack and push them onto a temporary stack until you got to b, then pop all the books off the temporary stack and push them back on the main stack.

For example:

import java.util.*;
public class test_stack {
    public static void main (String[] args){

        // put a, b and c on the stack
        Stack<String> stack = new Stack<String>();
        stack.push(“a”);
        stack.push(“b”);
        stack.push(“c”);
        printStack(stack);

        // pop items off the stack until we reach b (and push non b items onto temporary stack)
        Stack<String> temporaryStack = new Stack<String>();
        String currentItem;
        do {
            currentItem = stack.pop();
            if(!currentItem.equals("b")) {
                temporaryStack.push(currentItem);
        } while(!currentItem.equals("b"));

        // push temporary stack back onto main stack
        while(!temporaryStack.isEmpty()) {
            stack.push(temporaryStack.pop());
        }
        printStack(stack);
    }

    private static void printStack(Stack<String> s){
        if(s.isEmpty())
            System.out.printIn(“empty stack”);
        else
            System.out.printf(“% s TOP\n”, s);
    }

}

Answer 5

I don't think that this can be done using general stack operations of push and pop. Remember stack is LIFO. So in order to remove(POP) b, you have to remove(POP) c. And then again you have to push c.

Edit: If you manage to accomplish the required goal, be rest assured that you did not use the concept of stacks. Happy Coding!! :)

Answer 6

This cannot be done using Stack because that violates the whole concept of Stack operations. Even if we come up with a function that would remove an element from the middle of stack, then behind the scenes, it would be removing all the above elements > remove the required element > Push back the above elements again. And definitely this isn't a good approach.

The concept that stack uses is different. But if you have a scenario where you've to delete an element from middle, then you should be using LinkedList instead of Stack. That's what LinkedList basically is for.

package com.tutorialspoint;

import java.util.*;

public class LinkedListDemo {

   public static void main(String[] args) {
       // create a LinkedList
       LinkedList list = new LinkedList();

       // add some elements
       list.add("A");
       list.add("B");
       list.add("C");

       // print the list
       System.out.println("LinkedList:" + list);
       System.out.println("size:" + list.size());

       // remove "B" Element from the list
       list.remove("B");

       // print the list
       System.out.println("LinkedList:" + list);
       System.out.println("size:" + list.size());
   }
}

Output

LinkedList:[A, B, C]
size: 3
LinkedList:[A, C]
size: 2