2

I have a question how to design a stack without using list or array?

This is one question that I want to think about as I want to better understand stack.

3

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. To implement a stack without using java library,

  • create a class called Node, which contains a pointer reference to the next stack entry only.
  • create a class called MyStack, which contains the last stack entry. You also want to include these two functions:

    push(value):

    pop:

  • 4
    This implementation is a singly linked list, but the original question asked about implementing a stack without using a list. – Greg Hewgill Apr 10 '14 at 1:01
10

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.

  • 1
    As long as the ability to push and pop are available somehow, it's a stack. If you want to be really pedantic, you need to ensure the thing you pop is the last thing that was pushed in! ;) – Doval Apr 9 '14 at 22:35
  • This concept even has a name: LIFO which stands for "last-in, first-out". – Allan Apr 10 '14 at 4:11
7

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
0

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
  • 1
    When you link StackEntry objects, you are creating a linked list. – Bart van Ingen Schenau Apr 9 '14 at 6:39
0

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.

Not the answer you're looking for? Browse other questions tagged or ask your own question.