데이터 구조 (2) - 스 택, 대기 열
12951 단어 데이터 구조
스 택 은 후진 선 출 데이터 구조 로 Last In First Out (LIFO) 이 라 고도 부른다.
(a) 1.
2. ，
3. ， ，
（b） 1. Undo （ ）
2.
3.
3. Demo
package cn.data.Stack;
import java.util.Stack;
public class Solution {
/**
* ： Stack ， Java
* import java.util.Stack
* Stack stack = new Stack<>();
* ：ArrayStack stack = new ArrayStack<>();
* */
public boolean isValid(String s){
ArrayStack stack = new ArrayStack<>();
//Stack stack = new Stack<>();
for(int i=0;i
：
true
false
（c） 5 1.void push(E)
2.E pop()
3.E peek()
4.int getSize()
5.boolean isEmpty() ， ， ， ，
(d) 대기 열의 실현: 인터페이스 Queue (Array Queue 이 인터페이스 구현)
1. package cn.data.Stack;
public interface Stack {
int getSize(); // O(1)
boolean isEmpty(); // O(1)
E pop(); // resize ， O(1)
void push(E e); // resize ， O(1)
E peek(); // O(1)
}
2. ， ArrayStack package cn.data.Stack;
import cn.data.Array;
public class ArrayStack implements Stack {
Array array;
// ，
public ArrayStack(int capacity){
array = new Array<>(capacity);
}
// ，
public ArrayStack(){
array =new Array<>();
}
@Override
public int getSize(){
return array.getSize();
}
@Override
public boolean isEmpty(){
return array.isEmpty();
}
public int getCapacity(){
return array.getCapacity();
}
@Override
public void push(E e){
array.addLast(e);
}
@Override
public E pop(){
return array.removeLast();
}
@Override
public E peek(){
return array.getLast();
}
@Override
public String toString(){
StringBuilder res = new StringBuilder();
res.append("Stack:");
res.append("[");
for(int i=0;i
3. ， ArrayStack package cn.data.Stack;
public class Main {
public static void main(String[] args) {
ArrayStack stack = new ArrayStack<>();
for(int i=0;i<5;i++){
stack.push(i);
System.out.println(stack);
}
stack.pop();
System.out.println(stack);
}
}
：
Stack:[0] top
Stack:[0, 1] top
Stack:[0, 1, 2] top
Stack:[0, 1, 2, 3] top
Stack:[0, 1, 2, 3, 4] top
Stack:[0, 1, 2, 3] top ，
(2) 대열
대기 열 은 먼저 나 온 데이터 구조 (선착순) First In First Out (FIFO) 입 니 다.（a） （Queue）
1.
2. ，
3. （ ） ， （ ）
（b） 5
void enqueue(E)
E dequeue()
E getFront()
int getSize()
boolean isEmpty()
（c） ： Interface Queue（ArrayQueue ）
1.
package cn.data.Queue;
public interface Queue {
int getSize();
boolean isEmpty();
void enqueue(E e);
E dequeue();
E getFront();
}
2. （ArrayQueue）
package cn.data.Queue;
import cn.data.Array;
public class ArrayQueue implements Queue{
private Array array;
// ，
public ArrayQueue(int capacity){
array = new Array<>(capacity);
}
// ，
public ArrayQueue(){
array = new Array<>();
}
// O(1)
@Override
public int getSize(){
return array.getSize();
}
// O(1)
@Override
public boolean isEmpty(){
return array.isEmpty();
}
public int getCapacity(){
return array.getCapacity();
}
//
// O(1)
@Override
public void enqueue(E e){
array.addLast(e);
}
//
// ， ， O(n)
// ，
@Override
public E dequeue(){
return array.removeFirst();
}
// O(1)
@Override
public E getFront(){
return array.getFirst();
}
// Object toString
@Override
public String toString(){
StringBuilder res = new StringBuilder();
res.append("Queue:");
res.append("front[");
for(int i=0;i queue = new ArrayQueue<>();
for(int i=0;i<10;i++){
//
queue.enqueue(i);
System.out.println(queue);
if(i%3==2){
// （ ）
queue.dequeue();
System.out.println(queue);
}
}
}
}
：
Queue:front[0] tail
Queue:front[0, 1] tail
Queue:front[0, 1, 2] tail
Queue:front[1, 2] tail
Queue:front[1, 2, 3] tail
Queue:front[1, 2, 3, 4] tail
Queue:front[1, 2, 3, 4, 5] tail
Queue:front[2, 3, 4, 5] tail
Queue:front[2, 3, 4, 5, 6] tail
Queue:front[2, 3, 4, 5, 6, 7] tail
Queue:front[2, 3, 4, 5, 6, 7, 8] tail
Queue:front[3, 4, 5, 6, 7, 8] tail
Queue:front[3, 4, 5, 6, 7, 8, 9] tail
3. （LoopQueue）
package cn.data.Queue;
public class LoopQueue implements Queue {
private E[] data;
private int front,tail;
private int size;
//
public LoopQueue(int capacity){
//
data =(E[]) new Object[capacity+1];
front = 0;
tail = 0;
size = 0;
}
//
public LoopQueue(){
this(10);
}
//
public int getCapacity(){
return data.length-1;
}
@Override
public boolean isEmpty(){
return front==tail;
}
@Override
public int getSize(){
return size;
}
//
@Override
public void enqueue(E e){
//
if((tail+1)%data.length==front){
// ， . 2
resize(getCapacity()*2);
}
data[tail]=e;
// ，
tail = (tail+1)%data.length;
size++;
}
//
// ， O(n) O(1).
@Override
public E dequeue(){
//
if(isEmpty()){
throw new IllegalArgumentException("Cannot dequeue from an empty queue");
}
E ret = data[front];
data[front] = null;
// front size
front = (front+1)%data.length;
size--;
// ， ，
// ，
if(size==getCapacity()/4 && getCapacity()/2!=0){
resize(getCapacity()/2);
}
return ret;
}
//
@Override
public E getFront(){
if(isEmpty()){
throw new IllegalArgumentException("Queue is empty");
}
return data[front];
}
private void resize(int newCapacity){
E[] newData =(E[])new Object[newCapacity+1];
// newData
for(int i=0;i queue = new LoopQueue<>();
for(int i=0;i<10;i++){
//
queue.enqueue(i);
System.out.println(queue);
if(i%3==2){
// （ ）
queue.dequeue();
System.out.println(queue);
}
}
}
}
:
front==tail，
(tail+1)%c==front c=8
front ，tail
，capacity ， ，
：
Queue:size = 1,capacity = 10 front[0] tail 10
Queue:size = 2,capacity = 10 front[0, 1] tail
Queue:size = 3,capacity = 10 front[0, 1, 2] tail
Queue:size = 2,capacity = 5 front[1, 2] tail ， ，
Queue:size = 3,capacity = 5 front[1, 2, 3] tail
Queue:size = 4,capacity = 5 front[1, 2, 3, 4] tail
Queue:size = 5,capacity = 5 front[1, 2, 3, 4, 5] tail
Queue:size = 4,capacity = 5 front[2, 3, 4, 5] tail
Queue:size = 5,capacity = 5 front[2, 3, 4, 5, 6] tail ， ， ，
Queue:size = 6,capacity = 10 front[2, 3, 4, 5, 6, 7] tail
Queue:size = 7,capacity = 10 front[2, 3, 4, 5, 6, 7, 8] tail
Queue:size = 6,capacity = 10 front[3, 4, 5, 6, 7, 8] tail
Queue:size = 7,capacity = 10 front[3, 4, 5, 6, 7, 8, 9] tail
dequeue() ， O(n) O(1).
4. ArrayQueue LoopQueue
package cn.data.Queue;
import java.util.Random;
public class Main {
// q opCount enqueue dequeue ， ：
private static double testQueue(Queue q,int opCount){
//nanoTime
long startTime = System.nanoTime();
Random random = new Random();
for(int i=0;i arrayQueue = new ArrayQueue<>();
double time1 = testQueue(arrayQueue,opCount);
System.out.println("ArrayQueue,time:"+time1+"s");
LoopQueue loopQueue = new LoopQueue<>();
double time2 = testQueue(loopQueue,opCount);
System.out.println("LoopQueue,time:"+time2+"s");
}
}
：
Exception in thread "main" java.lang.IllegalArgumentException: AddLast failed,Array is full
at cn.data.Array.addLast(Array.java:35)
at cn.data.Queue.ArrayQueue.enqueue(ArrayQueue.java:37)
at cn.data.Queue.Main.testQueue(Main.java:14)
at cn.data.Queue.Main.main(Main.java:30)
： ：addLast ， Array 。 ，ArrayQueue LoopQueue Queue ，ArrayQueue LoopQueue Array ， Array addLast 。
： //
// ， ，
/*public void addLast(E e){
// ，
if(size == data.length){
throw new IllegalArgumentException("AddLast failed,Array is full");
}
data[size] = e;
size++;
}
：
public void addLast(E e){
// add
add(size,e);
}
：
[Ljava.lang.Object;@4554617c
[Ljava.lang.Object;@74a14482
[Ljava.lang.Object;@1540e19d
[Ljava.lang.Object;@677327b6
[Ljava.lang.Object;@14ae5a5
[Ljava.lang.Object;@7f31245a
[Ljava.lang.Object;@6d6f6e28
[Ljava.lang.Object;@135fbaa4
[Ljava.lang.Object;@45ee12a7
[Ljava.lang.Object;@330bedb4
[Ljava.lang.Object;@2503dbd3
[Ljava.lang.Object;@4b67cf4d
[Ljava.lang.Object;@7ea987ac
[Ljava.lang.Object;@12a3a380
[Ljava.lang.Object;@29453f44
[Ljava.lang.Object;@5cad8086
ArrayQueue,time:4.819054826s
LoopQueue,time:0.019589191s
， （O(n) O(1)）
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 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에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
