Algorithm/Algorithm_full_features/LinkedStack.java at master · shellteo/Algorithm · GitHub

History

153 lines (130 loc) · 3.37 KB

Raw

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

/**

* A generic stack, implemented using a linked list. Each stack element is of type Item.

import java.util.Iterator;

import java.util.NoSuchElementException;

/**

* The class represents a last-in-first-out(LIFO) stack of generic items.

* It supports the usual `push` and `pop` operations, along with methods

* for peeking at the top item, testing if the stack is empty, and iterating

* through the items in LIFO order.

* This implementation uses a singly linked list with a non-static nested

* class for linked-list nodes.

public class LinkedStack<Item> implements Iterable<Item> {

private int n; // size of the stack

private Node first; // top of stack

// helper linked list class

private class Node{

private Item item;

private Node next;

}

// Initializes an empty stack.

public LinkedStack() {

first = null;

n = 0;

assert check();

}

// Is this stack empty?

public boolean isEmpty() {

return first == null;

}

// returns the number of items in the stack.

public int size() {

return n;

}

// Adds the item to this stack.

public void push(Item item) {

Node oldfirst = first;

first = new Node();

first.item = item;

first.next = oldfirst;

n++;

assert check();

}

// removes and returns the item most recently added to this stack.

public Item pop() {

if(isEmpty())

throw new NoSuchElementException("Stack underflow");

Item item = first.item; // save item to return

first = first.next;

n--;

assert check();

return item; // return the saved item

}

// returns the item most recently added to this stack.

public Item peek() {

if(isEmpty())

throw new NoSuchElementException("Stack underflow");

return first.item;

}

// returns a string representation of this stack.

public String toString() {

StringBuilder s = new StringBuilder();

for(Item item : this)

s.append(item + " ");

return s.toString();

}

// returns an iterator to this stack that iterates through the items in LIFO order.

public Iterator<Item> iterator() {

return new ListIterator();

}

// an iterator, doesn't implement remove() since it's optional

private class ListIterator implements Iterator<Item> {

private Node 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;

}

// check internal invariants.

private boolean check() {

if(n < 0)

return false;

if(n == 0)

if(first != null)

return false;

else if(n == 1) {

if(first == null)

return false;

if(first.next != null)

return false;

} else {

if(first == null)

return false;

if(first.next == null)

return false;

}

// check internal consistency of instance variable n

int numberOfNodes = 0;

for(Node x = first; x != null && numberOfNodes <= n; x = x.next) {

numberOfNodes++;

}

if(numberOfNodes != n)

return false;

return true;

}

// test

public static void main(String[] args) {

LinkedStack<String> stack = new LinkedStack<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)");

}

Algorithm/Algorithm_full_features/LinkedStack.java at master · shellteo/Algorithm · GitHub

Expand file tree

Breadcrumbs

LinkedStack.java

Latest commit

History

Breadcrumbs

LinkedStack.java

File metadata and controls