Data Structure Java stack stack and queue Queue

Apr 29 posted in Java (RSS), comments.

Advertisements

My other blog on the image to the

Data Structure Java stack stack and queue Queue

Google found that most of the article are achieved through the LinkedList class, of course, there are built-in Stack class JDK

Recalling the set of JDK provided classes

Container (set) framework as follows:

Collections deposited in the java.util package. Collections are objects stored in a reference, rather than the object itself.

There are three kinds of collection types: set (set), list (list) and map (mapping).

Collection Interface

├ List Interface

│ ├ LinkedList list

│ ├ ArrayList order structure of dynamic array class

│ └ Vector Vector

│ └ Stack stack

Map Interface

├ Hashtable

├ HashMap

└ Set Interface

Collection <- Set <- HashSet

Collection <- Set <- HashSet <- LinkedHashSet

Collection <- Set <- SortedSet (also interfaces) <- TreeSet

LinkedList, access JDK

List interface linked list implementation. To achieve a list of all the optional operations, and allow all the elements (including null)

LinkedList class also the beginning and end of the list get, remove and insert elements to provide a unified naming. These operations allow linked lists for stacks, queues, or double-ended queue

Note that this implementation is not synchronized

JDK itself of the Stack class

Provide the usual push and pop operations, and the selection of the vertex stack peek method to test whether the stack empty empty method to find the items in the stack and determine the distance from the top of the stack, a total of five methods.

JDK itself to achieve this class this class inherits from Vector (since JDK1.0)

Stack data structure definition and basic operations

Stacks and queues are all linear structure, are two in operation subject to certain restrictions on the special linear form, they are simpler than the general linear form.

Stack (stack) is to limit the linear elements in the table insert and delete only the linear form of the same side for a special linear form. One end to allow insertion and deletion, known as the top of the stack (top), the other end is fixed at one end, called the bottom of the stack

Top of the stack, the stack bottom, empty stack, stack characteristics,

Return stack into the stack

Stack operations:

Initialize the stack, into the stack push, a stack pop,, take the stack elements (that is, see the next to a stack of elements, also called peek), check air

LinkedList stack used to achieve

Actually, the key is to achieve into the stack push, a stack pop,, elements of which are several ways to take the stack

package org.simoncook.examtest;

import java.util.LinkedList;

public class MyStack (

private LinkedList ll = new LinkedList ();

public void push (Object obj) (

/ / Insert the specified element at the beginning of this list.

ll.addFirst (obj);

)

public Object pop () (

/ / Removes and returns the first element of this list.

return ll.removeFirst ();

)

public Object peek () (

/ / Returns the first element of this list.

return ll.getFirst ();

)

public boolean empty () (

return ll.isEmpty ();

)

)

Queue data structure

Reference

http://blogger.org.cn/blog/more.asp?name=eaglebetter&id=17232

Queue (Queue) definition

Examples of the characteristics of the queue queue queue basic operations (1) into the team operation: InQueue (q, x)
(2) a team operation: OutQueue (q, x)
(3) reading the first element of team: ReadFront (q, x)
(4) shows the queue element ShowQueue (q)
(5) sub-team air operations: QEmpty (q)
(6) sub-team full operation: QFull (q)
(7) Find the queue length Qlen (q)

Implementation code:
package com.gc.list;
import java.util .*;
public class MyQueue (

private LinkedList ll = new LinkedList ();
/ / Enqueue operation
public void put (Object o) (
ll.addLast (o);
)
/ / Use removeFirst () method returns the first data queue, and then remove it from the queue
/ / A team operation
public Object get () (
return ll.removeFirst ();
)

public boolean empty () (
return ll.isEmpty ();
)