Shulou(Shulou.com)06/01 Report--

Let's start with what a stack is:

1. LIFO 2. All operations on the data can only be performed on a fixed end, not on the middle or the other end.

A class (object) that stores data that meets the above two points is called a stack.

It is important to note that stacks are all data structures that meet the above two characteristics can be called stacks, no matter what basic container they are implemented in.

Let's talk about how to achieve:

You can use arrays or linked lists to implement the stack, and when using linked lists, you should mask some of the features of the linked list: manipulating data in the middle of the linked list, and so on.

Take a look at the stack that comes with jdk:

Notice in Stack (figure 1): Stack inherits from Vactor Stack's own method type

In Vector (figure 2): methods in Vector

Stack inherits from Vactor, so Stack can call set (int index, E element), insertElementAt (E obj, int index) and other operations in the parent class, which contradicts the characteristics of the stack. I don't have a thorough understanding of this point, is the second feature that needs to be removed? I hope some friends can give me some advice after they see it. Thank you!

Figure 1: Stack.java

Figure 2: Vector.java

Since jdk has its own stack, what else do we know about him?

In some special cases, you need to encapsulate your own stack according to the actual situation.

Here are two self-made examples, one using an array and the other using a linked list.

Array implementation:

Package com.datastructure;/** * @ author Perkins .Zhu * @ date: 9:13:01 * @ version on July 17, 2016: 1.1 * * / public class ArrayStack implements Stack {private int maxSize; private Object [] myStack; private int top =-1 Bandbank / pointing to the last object in the stack private final int DEFAULT_SIZE = 100; private boolean canExpendSize = true;// whether to allow expansion private int multiple = 2 / / expansion multiple public ArrayStack () {myStack = new object [default _ SIZE];} public ArrayStack (int size, boolean canExpendSize) {if (size < 1) {size = DEFAULT_SIZE;} myStack = new Object [size]; this.canExpendSize = canExpendSize } @ Override public void push (Object obj) {if (top = = myStack.length-1) {if (canExpendSize) {exspandSize ();} else {move ();}} myStack [+ + top] = obj } / / Delete the elements at the bottom of the stack, all elements are moved backward by one bit, and top points to myStack.length-2 private void move () {for (int I = 0; I < myStack.length- 1; iSuppli +) {myStack [I] = myStack [I + 1];} top = myStack.length-2 } / / expand private void exspandSize () {Object [] temp = new Object [multiple * myStack.length]; for (int I = 0; I < myStack.length; iTunes +) {temp [I] = myStack [I];} top = myStack.length-1; myStack = temp } @ Override public Object pop () {if (top = =-1) return null; return myStack [top--];} @ Override public boolean isEmpty () {return top = =-1;}}

Linked list implementation: (only basic functions have been realized, parameters or methods can be added according to actual needs)

Package com.datastructure;import java.util.LinkedList;/** * @ author Perkins .Zhu * @ date: 1:16:26 * @ version / public class LinkStack implements Stack {private Node top; private class Node {private Object obj; private Node nextNode; public Node (Object obj, Node node) {this.obj = obj; this.nextNode = node } public void push (Object obj) {if (top! = null) {top = new Node (obj, top);} else {top = new Node (obj, null);}} public Object pop () {Node res = top; top = top.nextNode;= top = =

Give another test class:

Package com.datastructure;import org.junit.Test;/** * @ author Perkins .Zhu * @ date: 9:16:50 * @ version / public class StackTest {@ Test public void testArrayStack () {ArrayStack stack = new ArrayStack (100, false); int loop = 0; while (loop < 150am) {stack.push (loop++) } print (stack);} public void print (Object obj) {if (obj instanceof Stack) {Stack stack = (Stack) obj; while (! stack.isEmpty ()) {System.out.print (stack.pop () + ");}} System.out.println () } @ Test public void testLinkStack () {LinkStack stack = new LinkStack (); int loop = 0; while (loop < 150) {stack.push (loop++);} print (stack);}}

Several problems encountered:

1. Is there an official standard definition of stack?

As long as the data structure conforms to last-in, first-out (last in first off,LIFO), it is a stack.

2. What is the difference between generic T and object, and what is the difference when receiving parameters?

A: constrains that only one type of data can be stored in this container.

B: there is no need for type reversal when fetching an object from the container, the container already knows (because the storage object type has been defined in the new container) what type you store, but object needs to do a type override.

3. Do you want to delete, insert and find the stack?

The stack does not need these methods, and the existence of these methods is meaningless. Ruin the effect by adding sth. Superfluous.

4. Is there any other stack implementation besides using arrays and linked lists?

I don't think so, right?

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.