495. Implement Stack【easy】

Implement a stack. You can use any data structure inside a stack except stack itself to implement it.

Have you met this question in a real interview?

Example

push(1)
pop()
push(2)
top()  // return 2
pop()
isEmpty() // return true
push(3)
isEmpty() // return false

解法一：

 1 class Stack {
 2 public:
 3     struct Node {
 4         int val;
 5         Node *prev, *next;
 6         Node(int v) {
 7             val = v;
 8             prev = NULL;
 9             next = NULL;
10         }
11     };
12      
13     Node *dummy;
14     Node *tail;
15     Stack() {
16         dummy = new Node(0);
17         tail = dummy;
18     }
19     
20     ~Stack() {
21          
22     }
23     
24     void push(int x) {
25         tail->next = new Node(x);
26         tail->next->prev = tail;
27         tail = tail->next;
28     }
29  
30     // Pop the top of the stack
31     void pop() {
32         if (dummy->next == NULL) {
33             return;
34         }
35         Node *prev = tail->prev;
36         prev->next = NULL;
37         tail = prev;
38     }
39  
40     // Return the top of the stack
41     int top() {
42         if (dummy->next == NULL) {
43             return -1;
44         }
45         return tail->val;
46     }
47  
48     // Check the stack is empty or not.
49     bool isEmpty() {
50         if (dummy->next == NULL) {
51             return true;
52         }
53         return false;
54     }
55 };

用链表实现栈，因为栈pop出的是最后一个，如果用尾插法的单向链表明显不太方便，所以用双向链表。

参考@YI 的代码

https://yixuanwangblog.wordpress.com/2016/09/04/lintcode-495-implement-stack/

解法二：

 1 class ListNode{
 2     int val;
 3     ListNode next;
 4     public ListNode(int val) {
 5         this.val = val;
 6     }
 7 };
 8 
 9 public class Stack {
10     ListNode head;
11     public Stack(){
12        head = new ListNode(0);
13     }
14     
15     /*
16      * @param x: An integer
17      * @return: nothing
18      */
19     public void push(int x) {
20         ListNode node = new ListNode(x);
21         node.next = head.next;
22         head.next = node;
23     }
24 
25     /*
26      * @return: nothing
27      */
28     public int pop() {
29         ListNode top = head.next;
30         head.next = head.next.next;
31         return top.val;
32     }
33 
34     /*
35      * @return: An integer
36      */
37     public int top() {
38         return head.next.val;
39     }
40 
41     /*
42      * @return: True if the stack is empty
43      */
44     public boolean isEmpty() {
45         if (head.next == null) {
46             return true;
47         } else{
48             return false;
49         }
50     }
51 }

用链表实现栈，使用头插法。

参考@zhengyang2015 的代码

https://zhengyang2015.gitbooks.io/lintcode/implement_stack_495.html