Implement Stack 495

Question

实现一个栈，可以使用除了栈之外的数据结构。实现栈的基本功能：push, pop, top, isEmpty。

Example:

push(1)

pop()

push(2)

top() // return 2

pop()

isEmpty() // return true

push(3)

isEmpty() // return false

Solution

使用LinkedList实现stack。

代码如下：

class ListNode{
    int val;
    ListNode next;
    public ListNode(int val){
        this.val = val;
    }
}

class Stack{
    ListNode head;
    public Stack(){
        head = new ListNode(0);
    }

    public void push(int value){
        ListNode node = new ListNode(value);
        node.next = head.next;
        head.next = node;
    }

    public int pop(){
        ListNode top = head.next;
        head.next = head.next.next;
        return top.val;
    }

    public int top(){
        return head.next.val;
    }

    public boolean isEmpty(){
        if(head.next == null){
            return true;
        }else{
            return false;
        }
    }
}

Related Question

Implement stack by two queues 494