기본 데이터 구조의 설명 (2)
6536 단어 데이터 구조
스 택 이란 최소 두 개의 기본 작업 을 포함 하 는 추상 적 인 데이터 형식 입 니 다. 새로운 요 소 를 삽입 합 니 다.최근 시간 에 삽 입 된 요 소 를 삭제 합 니 다. FILO (First in, last out, 선진 후 출) 의 원칙 을 따른다.
대기 열 이란 최소 두 개의 기본 동작 을 포함 하 는 추상 적 인 데이터 형식 이기 도 합 니 다. 새로운 요 소 를 삽입 합 니 다.가장 오래 삽 입 된 요 소 를 삭제 합 니 다. FIFO (First in, first out, 선진 선 출) 의 원칙 을 따른다.
창고 와 대열 의 구체 적 인 실현 에 대해 우 리 는 수조 에 의존 할 수도 있 고 체인 테이블 로 실현 할 수도 있다.
1) 스 택 의 배열 구현 방식
public class MyStack<E> {
public int count;
public Object [] items;
public boolean isEmpty(){
return count==0;
}
public MyStack (){
items=new Object[20];
count=0;
}
public MyStack (int len){
items=new Object[len];
count=0;
}
/**
**/
private void resize(int size){
Object [] newItems=new Object[size];
for(int i=0;i<count;i++){
newItems[i]=items[i];
}
items=newItems;
}
public void push(E e){
if(count==items.length) resize(2*items.length);
items[count++]=e;
}
public E pop(){
if(count==0) return null;
E item=(E)items[count-1];
items[count-1]=null;
count--;
if(count>0&&count<=items.length/4) resize(items.length/2);
return item;
}
public E peek(){
if(count==0) return null;
E item=(E)items[count-1];
return item;
}
}
2) 창고 의 체인 실현 방식
public class MyStack<E> {
private class Node{
E item;
Node next;
}
Node head;
public boolean isEmpty(){
return head==null;
}
public void push(E t){
Node node=new Node();
node.item=t;
node.next=head;
head=node;
}
public E pop(){
if(head==null)
return null;
E t=head.item;
head=head.next;
return t;
}
public E peek(){
if(head==null)
return null;
else
return head.item;
}
}
3) 대기 열의 배열 구현
public class ArrayQueue<E> {
private int front;
private int rear;
private int count;
private int capacity;
private int capacityIncrement;
private Object[] itemArray;
public ArrayQueue(){
front=0;
rear=0;
count=0;
capacity=10;
capacityIncrement=5;
itemArray=new Object[capacity];
}
public boolean empty(){
return count==0;
}
public void insert(E e){
if(count==capacity){
capacity+=capacityIncrement;
Object [] newArray=new Object[capacity];
// for(int i=0;i<count;i++){
// newArray[i]=itemArray[i];
// }
if(front<rear){
// itemArray[front:rear-1]
for(int i=front;i<rear;i++){
newArray[i]=itemArray[i];
}
}else{
// ,
// 1:itemArray[0:rear-1]
for(int i=0;i<rear;i++){
newArray[i]=itemArray[i];
}
// 2:itemArray[front:count-1]
for(int i=front;i<count;i++){
newArray[i]=itemArray[i];
}
front+=capacityIncrement;// , front
}
itemArray=newArray;
}
itemArray[rear]=e;
rear=(rear+1)%capacity;
count++;
}
public E remove(){
if(count==0){
return null;
}
else{
E temp=(E) itemArray[front];
itemArray[front]=null;
front=(front+1)%capacity;
count--;
return temp;
}
}
}
배열 의 또 다른 간단 한 실현 방식:
import java.util.NoSuchElementException;
public class ArrayQueue {
protected Object [] data;
protected int size,
head,
tail;
public ArrayQueue(){
final int INITIAL_LENGTH=100;
data=new Object[INITIAL_LENGTH];
size=0;
head=0;
tail=-1;
}
public int size(){
return size;
}
public boolean isEmpty(){
return size==0;
}
public Object front(){
if(size==0)
throw new NoSuchElementException();
return data[head];
}
public void enqueue(Object element){
if(size==data.length){
//double the length of data
Object [] oldData=data;
data=new Object[data.length*2];
//copy oldData[head...OldData.length-1]
//to data[0... OldData.length-1-head]
System.arraycopy(oldData, head,data , 0, oldData.length-head);
if(head>0)
//copy oldData[0...tail] to data [head+1 .. oldlenght-1]
System.arraycopy(oldData, 0, data, head+1, tail+1);
head=0;
tail=oldData.length-1;
}
tail=(tail+1)%data.length;
size++;
data[tail]=element;
}
public Object dequeue(){
if(size--==0){
throw new NoSuchElementException();
}
Object element=data[head];
head=(head+1)%data.length;
return element;
}
}
4) 대기 열의 체인 실현 방식
public class ListQueue<E> {
private class Node<E>{
E item;
Node<E> link;
}
private Node<E> front,rear;
private int count;
public boolean empty(){
return count==0;
}
public void insert(E e){
//
Node<E> newNode=new Node<E>();
newNode.item=e;
if(rear==null){
front=rear=newNode;
}else{
rear.link=newNode;
rear=newNode;
}
count++;
}
public E remove(){
if(count==0){
return null;
}else{
E e=front.item;
front=front.link;
if(front==null){
rear=null;
}
count--;
return e;
}
}
public ListQueue<E> clone(){
ListQueue<E> Q=new ListQueue<E>();
for(Node<E> t=front;t!=null;t=t.link)
Q.insert(t.item);
return Q;
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.