Stack.java
6.57 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
/******************************************************************************
* Compilation: javac Stack.java
* Execution: java Stack < input.txt
* Dependencies: StdIn.java StdOut.java
* Data files: http://algs4.cs.princeton.edu/13stacks/tobe.txt
*
* A generic stack, implemented using a singly-linked list.
* Each stack element is of type Item.
*
* This version uses a static nested class Node (to save 8 bytes per
* Node), whereas the version in the textbook uses a non-static nested
* class (for simplicity).
*
* % more tobe.txt
* to be or not to - be - - that - - - is
*
* % java Stack < tobe.txt
* to be not that or be (2 left on stack)
*
******************************************************************************/
package edu.princeton.cs.algs4;
import java.util.Iterator;
import java.util.NoSuchElementException;
/**
* The {@code Stack} class represents a last-in-first-out (LIFO) stack of generic items.
* It supports the usual <em>push</em> and <em>pop</em> operations, along with methods
* for peeking at the top item, testing if the stack is empty, and iterating through
* the items in LIFO order.
* <p>
* This implementation uses a singly-linked list with a static nested class for
* linked-list nodes. See {@link LinkedStack} for the version from the
* textbook that uses a non-static nested class.
* The <em>push</em>, <em>pop</em>, <em>peek</em>, <em>size</em>, and <em>is-empty</em>
* operations all take constant time in the worst case.
* <p>
* For additional documentation,
* see <a href="http://algs4.cs.princeton.edu/13stacks">Section 1.3</a> of
* <i>Algorithms, 4th Edition</i> by Robert Sedgewick and Kevin Wayne.
*
* @author Robert Sedgewick
* @author Kevin Wayne
*
* @param <Item> the generic type of an item in this stack
*/
public class Stack<Item> implements Iterable<Item> {
private Node<Item> first; // top of stack
private int n; // size of the stack
// helper linked list class
private static class Node<Item> {
private Item item;
private Node<Item> next;
}
/**
* Initializes an empty stack.
*/
public Stack() {
first = null;
n = 0;
}
/**
* Returns true if this stack is empty.
*
* @return true if this stack is empty; false otherwise
*/
public boolean isEmpty() {
return first == null;
}
/**
* Returns the number of items in this stack.
*
* @return the number of items in this stack
*/
public int size() {
return n;
}
/**
* Adds the item to this stack.
*
* @param item the item to add
*/
public void push(Item item) {
Node<Item> oldfirst = first;
first = new Node<Item>();
first.item = item;
first.next = oldfirst;
n++;
}
/**
* Removes and returns the item most recently added to this stack.
*
* @return the item most recently added
* @throws NoSuchElementException if this stack is empty
*/
public Item pop() {
if (isEmpty()) throw new NoSuchElementException("Stack underflow");
Item item = first.item; // save item to return
first = first.next; // delete first node
n--;
return item; // return the saved item
}
/**
* Returns (but does not remove) the item most recently added to this stack.
*
* @return the item most recently added to this stack
* @throws NoSuchElementException if this stack is empty
*/
public Item peek() {
if (isEmpty()) throw new NoSuchElementException("Stack underflow");
return first.item;
}
/**
* Returns a string representation of this stack.
*
* @return the sequence of items in this stack in LIFO order, separated by spaces
*/
public String toString() {
StringBuilder s = new StringBuilder();
for (Item item : this) {
s.append(item);
s.append(' ');
}
return s.toString();
}
/**
* Returns an iterator to this stack that iterates through the items in LIFO order.
*
* @return an iterator to this stack that iterates through the items in LIFO order
*/
public Iterator<Item> iterator() {
return new ListIterator<Item>(first);
}
// an iterator, doesn't implement remove() since it's optional
private class ListIterator<Item> implements Iterator<Item> {
private Node<Item> current;
public ListIterator(Node<Item> first) {
current = first;
}
public boolean hasNext() {
return current != null;
}
public void remove() {
throw new UnsupportedOperationException();
}
public Item next() {
if (!hasNext()) throw new NoSuchElementException();
Item item = current.item;
current = current.next;
return item;
}
}
/**
* Unit tests the {@code Stack} data type.
*
* @param args the command-line arguments
*/
public static void main(String[] args) {
Stack<String> stack = new Stack<String>();
while (!StdIn.isEmpty()) {
String item = StdIn.readString();
if (!item.equals("-"))
stack.push(item);
else if (!stack.isEmpty())
StdOut.print(stack.pop() + " ");
}
StdOut.println("(" + stack.size() + " left on stack)");
}
}
/******************************************************************************
* Copyright 2002-2016, Robert Sedgewick and Kevin Wayne.
*
* This file is part of algs4.jar, which accompanies the textbook
*
* Algorithms, 4th edition by Robert Sedgewick and Kevin Wayne,
* Addison-Wesley Professional, 2011, ISBN 0-321-57351-X.
* http://algs4.cs.princeton.edu
*
*
* algs4.jar is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, either version 3 of the License, or
* (at your option) any later version.
*
* algs4.jar is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with algs4.jar. If not, see http://www.gnu.org/licenses.
******************************************************************************/