Я написал свои собственные реализации Stack и Queue , но я заставил их работать специально для целых чисел. Я хорошо знаю реализации Java java.util.Stack и java.util.Queue, но я делаю это как опыт обучения ... просто хочу узнать что-то новое. Как бы я сделал эти универсальные реализации такими, чтобы я мог хранить любой объект в моем стеке / очереди, а не только целые числа?
Ниже приведен код, но я также приветствую все критические замечания и предложения по улучшению. Я хотел бы знать, что я сделал хорошо и что я не сделал хорошо.
РЕАЛИЗАЦИЯ СТЕКОВОГО УЗЛА
public class StackNode {
public Integer value;
public StackNode() {
this.value = null;
}
public StackNode(StackNode node) {
this.value = node.value;
}
public StackNode(Integer data) {
this.value = data;
}
}
РЕАЛИЗАЦИЯ СТЕКА
/**
* Stack Data Structure.
*
* A Stack is a last in, first out (LIFO) data structure. A Stack can have any abstract data type as an element, but is
* characterized by two fundamental operations: push() and pop(). The push() operation adds an element to the top of the Stack,
* hiding any elements already on the Stack, or initializing the Stack if it is empty. The pop() operation removes an element
* from the top of the Stack, and returns this element's value to the caller. Elements are removed from the Stack in the reverse
* order to the order of their addition to the Stack; therefore, lower elements are those that have been on the Stack the
* longest, thus, the first element added to the Stack will be the last one to be removed.
*
* @author Hristo
*/
public class Stack {
private int size;
private int capacity;
private int topNodeIndex;
private Object[] theStack;
/**
* Default Constructor. Initalizes this Stack with initial size = 0 and capacity = 1.
*/
public Stack() {
this.size = 0;
this.capacity = 1;
this.topNodeIndex = -1;
this.theStack = new Object[capacity];
}
/**
* Constructor. Initializes a Stack to have the given capacity.
*
* @param capacity - the capacity of the Stack-to-be
*/
public Stack(int capacity) {
this.size = 0;
this.capacity = capacity;
this.topNodeIndex = -1;
this.theStack = new Object[capacity];
}
/**
* Returns the size of this Stack, i.e., how many elements are in this Stack.
*
* @return int - the size of this Stack
*/
public int size() {
return this.size;
}
/**
* Returns the capacity of this Stack, i.e., the maximum number of elements this Stack can hold.
*
* @return int - the capacity of this Stack
*/
public int capacity() {
return this.capacity;
}
/**
* Returns whether or not this Stack is empty, i.e., size == 0.
*
* @return boolean - true if this Stack is empty, false otherwise
*/
public boolean isEmpty() {
return ((this.topNodeIndex == -1) && (this.size == 0)) ? true : false;
}
/**
* Returns whether or not this Stack is full, i.e., size == capacity.
*
* @return boolean - true if this Stack is full, false otherwise
*/
public boolean isFull() {
return (this.size == this.capacity) ? true : false;
}
/**
* Pushes the given value onto the top of this Stack.
*
* @param value - the data to push
*/
public void push(Integer value) {
if (value == null) {
return;
} else {
if (isFull()) {
resize();
}
insert(value);
return;
}
}
/**
* Removes the top element of this Stack and returns the corresponding value.
*
* @return Integer - the value of the top element of this Stack
*/
public Integer pop() {
if (isEmpty()) {
return null;
} else {
return remove();
}
}
/**
* Returns the top element of this Stack without removing it.
*
* @return Integer - the top element of this Stack
*/
public Integer peek() {
return (isEmpty()) ? null : (((StackNode) theStack[this.topNodeIndex]).value);
}
/**
* Inserts the given value onto this Stack.
*
* @param value - the value to insert
*/
private void insert(Integer value) {
theStack[this.topNodeIndex + 1] = new StackNode(value);
this.topNodeIndex++;
this.size++;
return;
}
/**
* Removes the top element of this Stack and returns the corresponding value.
*/
private Integer remove() {
StackNode topNode = (StackNode) theStack[this.topNodeIndex];
theStack[this.topNodeIndex] = null;
this.topNodeIndex--;
this.size--;
return topNode.value;
}
/**
* Creates an array with double the size of the original and copies over the contents from the original.
*/
private void resize() {
Object[] doubleStack = new Object[this.capacity * 2];
for (int index = 0; index < this.size; index++) {
doubleStack[index] = theStack[index];
}
theStack = doubleStack;
capacity *= 2;
return;
}
}
ОСУЩЕСТВЛЕНИЕ ОЧЕРЕДНОГО УЗЛА
public class QueueNode {
public Integer value;
public QueueNode() {
this.value = null;
}
public QueueNode(QueueNode node) {
this.value = node.value;
}
public QueueNode(Integer data) {
this.value = data;
}
}
РЕАЛИЗАЦИЯ ОЧЕРЕДИ
/**
* Queue Data Structure.
*
* A Queue is a first in, first out (FIFO) data structure. A Queue can have any abstract data type as an element, but is
* characterized by two fundamental operations: enqueue() and dequeue(). The enqueue() operation adds an element to the front of
* the Queue, hiding any elements already in the Queue, or initializing the Queue if it is empty. The dequeue() operation
* removes an element from the front of the Queue, and returns this element's value to the caller. Elements are removed from the
* Queue in the same order to the order of their addition to the Queue; therefore, the first element added to the Queue will be
* the first one to be removed.
*
* @author Hristo
*/
public class Queue {
private int size;
private int capacity;
private int theEndIndex;
private int theFrontIndex;
private Object[] theQueue;
/**
* Default Constructor. Initalizes this Queue with initial size = 0 and capacity = 1.
*/
public Queue() {
this.size = 0;
this.capacity = 1;
this.theEndIndex = -1;
this.theFrontIndex = -1;
this.theQueue = new Object[this.capacity];
}
/**
* Constructor. Initializes a Queue to have the given capacity.
*
* @param capacity - the capacity of the Queue-to-be
*/
public Queue(int capacity) {
this.size = 0;
this.capacity = capacity;
this.theEndIndex = -1;
this.theFrontIndex = -1;
this.theQueue = new Object[capacity];
}
/**
* Returns the size of this Queue, i.e., how many elements are in this Queue.
*
* @return int - the size of this Queue
*/
public int size() {
return this.size;
}
/**
* Returns the capacity of this Queue, i.e., the maximum number of elements this Queue can hold.
*
* @return int - the capacity of this Queue
*/
public int capacity() {
return this.capacity;
}
/**
* Returns whether or not this Queue is empty, i.e., size == 0.
*
* @return boolean - true if this Queue is empty, false otherwise
*/
public boolean isEmpty() {
return ((this.theEndIndex == this.theFrontIndex) && (this.size == 0)) ? true : false;
}
/**
* Returns whether or not this Queue is full, i.e., size == capacity.
*
* @return boolean - true if this Queue is full, false otherwise
*/
public boolean isFull() {
return (this.size == this.capacity && this.theEndIndex == this.theFrontIndex) ? true : false;
}
/**
* Inserts the given value onto the end of this Queue.
*
* @param value - the data to insert
*/
public void enqueue(Integer value) {
if (value == null) {
return;
} else {
if (isEmpty()) {
this.theEndIndex = 0;
this.theFrontIndex = 0;
}
if (isFull()) {
resize();
}
insert(value);
return;
}
}
/**
* Removes the front element in this Queue and returns it.
*
* @return Integer - the front element in this Queue
*/
public Integer dequeue() {
if (isEmpty()) {
return null;
} else {
return remove();
}
}
/**
* Returns the front element of this Queue without removing it.
*
* @return Integer - the front element of this Queue
*/
public Integer peek() {
return (isEmpty()) ? null : (((QueueNode) theQueue[this.theFrontIndex]).value);
}
/**
* Inserts the given value into this Queue.
*
* @param value - the value to insert
*/
private void insert(Integer value) {
this.theQueue[this.theEndIndex] = new QueueNode(value);
/*
* 'theEndIndex' pointer indicates where to insert new QueueNodes in 'theQueue' array. If incrementing this pointer goes
* beyond the size of 'theQueue' array, then pointer needs to wrap around to the beggining of 'theQueue' array.
*/
this.theEndIndex++;
if (this.theEndIndex >= this.theQueue.length) {
this.theEndIndex = 0; // wrap around
}
this.size++;
return;
}
/**
* Removes the front element in this Queue and returns the corresponding value.
*/
private Integer remove() {
QueueNode node = (QueueNode) this.theQueue[this.theFrontIndex];
theQueue[this.theFrontIndex] = null;
/*
* 'theFrontIndex' pointer indicates where to remove QueueNodes from 'theQueue' array. If incrementing this pointer goes
* beyond the size of 'theQueue' array, then pointer needs to wrap around to the beggining of 'theQueue' array.
*/
this.theFrontIndex++;
if (this.theFrontIndex >= this.theQueue.length) {
this.theFrontIndex = 0; // wrap around
}
this.size--;
return node.value;
}
/**
* Creates an array with double the size of the original and copies over the contents from the original.
*/
private void resize() {
Object[] doubleQueue = new Object[this.capacity * 2];
int count = 0;
int iter = this.theFrontIndex;
while (count < this.size) {
doubleQueue[count] = (QueueNode) theQueue[iter];
iter++;
count++;
if (iter >= this.size && this.size > 1) {
iter = 0;
}
}
this.theQueue = doubleQueue;
this.capacity *= 2;
this.theEndIndex = this.size;
this.theFrontIndex = 0;
return;
}
}