An ordered stack is a data structure that stores a sequence of items and support

Question

An ordered stack is a data structure that stores a sequence of items and supports the following operations. ORDERPUSH(x) removes all items smaller than x from the beginning of the sequence and then adds x to the beginning of the sequence. Pop deletes and returns the first item in the sequence (or NULL if the sequence is empty). Suppose we implement an ordered stack with a simple linked list, using the obvious ORDERPUSH and Pop algorithms. Prove that if we start with an empty data structure, the amortized cost of each ORDERPUSH or Pop operation is O(1).

Explanation / Answer

Here is solution as per the given criteria, please go through it thoroughly:-

=====================================

class LinkList<T> {

private static class Node<T> {

private final T data;
private final Node<T> next;

public Node(T data) {
this.data = data;
}

@Override
public String toString() {
return data.toString();
}
}

private Node<T> first = null;

public void addFirst(T data) {
Node<T> newFirst = new Node<T>

(data);
newFirst.next = first;
first = newFirst;
}

public T removeFirst() {
Node<T> oldFirst = first;
first = first.next;
return oldFirst.data;
}

@Override
public String toString() {
StringBuilder builder = new

StringBuilder();
Node current = first;
while (current != null) {
builder.append(current).append("

");
current = current.next;
}
return builder.toString();
}

public boolean isEmpty() {
return first == null;
}

}

class LinkListStack<T> {

private final LinkList<T> linkedList =

new LinkList<>();

public void push(T data) {
linkedList.addFirst(data);
}

public T pop() {
return linkedList.removeFirst();
}

public boolean isEmpty() {
return linkedList.isEmpty();
}

@Override
public String toString() {
return linkedList.toString();
}
}
====================================
@Test
public void testPushAndPop() {
LinkListStack<Integer> st = new LinkListStack<>();
st.push(50);
st.push(70);
st.push(190);
assertEquals("190 70 50", st.toString());
assertEquals(190, (int) st.pop());
assertEquals("70 50", st.toString());
}

@Test
public void testPopUntilEmpty() {
List<Integer> values = Arrays.asList(50, 70, 190, 20);
LinkListStack<Integer> st = new LinkListStack<>();
assertTrue(st.isEmpty());
for (Integer value : values) {
st.push(value);
}
assertFalse(st.isEmpty());
for (int i = values.size(); i > 0; --i) {
assertEquals(values.get(i - 1), st.pop());
}
assertTrue(st.isEmpty());
}

Run these codes into your window and check out the output

The time complexity of push and pop operations should be O(1)
Normally, the pop operation on a stack should return the most recently added value. That's O(1) time

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.