how to design a stack without using java library or using list [closed]

A stack is really just an interface, which provides at least the following operations:

• push a new element onto the stack
• pop an element off the stack

The underlying implementation can be anything that satisfies these operations. Arrays and lists are common implementations for stacks, but you could create an (inefficient) stack using a hash table, or files on disk, or even numbered pieces of paper scattered around a room. As long as the ability to push and pop are available somehow, it's a stack.

You dont have to use an array or a list, you can create a simple stack by doing the following:

• create a class called StackEntry, which contains a reference to the next stack entry only.

• create a class called MyStack, which contains the last stack entry, and two functions:

  push(value):

  • creates a new stack entry.
  • sets it to refer to the current stack entry,
  • and set it to be the current replacing the existing one.

  pop:

  • uses the current stack entry and gets its referenced stack entry,
  • sets the current to be the referenced stack entry
  • returns the old "current" entry

Since you tag the question as java we solve the question with.....Objects! We're actually pretty much going to be implementing a singularly linked list. A stack can either be empty (which is really easy to write), or it can not be empty in which case it has a top item and a pointer to the rest of the stack.

Below is code for an immutable stack (one in which pushing or popping returns a new stack instead of modifying the existing one). You'll have to forgive the formatting, I don't know how to correctly enter the code into the editor here.

First you have an interface saying what constitutes a stack

public interface IStack<A> {

public boolean isEmpty();

public A peek();

public IStack<A> push(A a);

public IStack<A> pop();
}

There are 2 kinds of IStacks. Those which are empty, and those which aren't. Let's look at the EmptyStack first because it's easier.

import java.util.EmptyStackException;

public class EmptyStack<A> implements IStack<A> {

//Since all empty stacks are the same, you would want it to follow the singleton pattern instead of relying on the default constructor

public boolean isEmpty() {
    return true;
}

public A peek() {
    throw new EmptyStackException();
}

public IStack<A> push(A a) {
    return new Stack<A>(this, a);
}

public IStack<A> pop() {
    throw new EmptyStackException();
}
}

Now let's look at a Stack which isn't empty.

public class Stack<A> implements IStack<A>{

private IStack<A> _stack;
private A _a;

public Stack(IStack<A> stack, A a) {
    _stack = stack;
    _a = a;
}

public boolean isEmpty() {
    return false;
}

public A peek() {
    return _a;
}

public IStack<A> push(A a) {
    return new Stack<A>(this, a);
}

public IStack<A> pop() {
    return _stack;
}
}

Let's try using it

public class Test {

public static void printInfo(String stackName, IStack<?> stack){
    System.out.println("-----------");
    System.out.println(stackName + ":");
    boolean isEmpty = stack.isEmpty();
    System.out.println("Is Empty: " + isEmpty);
    if(!isEmpty){
        System.out.println("Item: " + stack.peek());
    }
}

public static void main(String[] args) {
    IStack<Character> empty1 = new EmptyStack<Character>();
    IStack<Character> aStack1 = empty1.push('a');
    IStack<Character> abStack = aStack1.push('b');
    IStack<Character> aStack2 = abStack.pop();
    IStack <Character> empty2 = aStack2.pop();

    printInfo("empty1", empty1);
    printInfo("aStack1", aStack1);
    printInfo("abStack", abStack);
    printInfo("aStack2", aStack2);
    printInfo("empty2", empty2);
}
}

Output from the test is

-----------
empty1:
Is Empty: true
-----------
aStack1:
Is Empty: false
Item: a
-----------
abStack:
Is Empty: false
Item: b
-----------
aStack2:
Is Empty: false
Item: a
-----------
empty2:
Is Empty: true

Conceptually speaking, a stack is a linked list without random access and only one point of entry: the top, whereas a list often has random access and two points of entry: the front and the back. While there usually is a T peek(), peek can't be used for manipulation of the contents. Random access is usually explained as the ability to manipulate at any given point in the collection.

So if you're saying without using a list, do you mean without using a Java API List class as a basis for your work, or really not using a list? The latter is almost impossible, as it basically is a list, and implementing in another manner would be an exercise comparable to making a Rube Goldberg machine.