Какво е стекова структура на данните
Първо, нека да разгледаме набързо Howво представлява стековата структура от данни. Това е линейна структура от данни, която се основава на принципа „Последен влязъл, първи излязъл“ (LIFO). Това е нещо като анти-опашка. Представете си тесте карти or купчина книги в кутия. Книгата, която поставите първа в стека, е най-отдолу, а първата, която ще извадим от кутията, е книгата, която е била най-отгоре - тоест тази, която е попаднала в кутията последна. Ето gif снимка, за да демонстрирате този принцип.
За Howво е структурата на данните Stack?
Едно от най-важните applications на стека е организирането на извиквания на подпрограми. Точката на повикване в стека съхранява address за връщане от подпрограмата след нейното приключване (и евентуално предадените параметри). С всяко вложено (включително рекурсивно) извикване на подпрограми към стека се добавят нови addressи за връщане. При всяка операция за връщане от подпрограмата (return), addressът за връщане се премахва от стека и управлението се прехвърля към него. Това приложение е толкова важно за програмирането, че в повечето процесори обратният стек е имплементиран хардуерно в набора от инструкции. В други случаи обаче стекът трябва да се моделира върху по-общи структури от данни.Java Stack Class of Collection Framework
В Java Stack Class е клас от рамката на колекцията, който имплементира интерфейс List и разширява векторния клас. Той също така прилага интерфейси Collection, Iterable, Cloneable, Serializable. Както вероятно вече се досещате, този клас представлява LIFO стека от обекти. Ето извикването на конструктора на класа Stack , тоест създаването на обект от този клас.
Stack<E> stack = new Stack<E>();
Където E е типът на обекта.
Java стекови методи
Този клас има само един конструктор по подразбиране и всички методи на класа Vector . Освен това Stack има свои собствени 5 метода:-
boolean empty() методът проверява дали стекът е празен or не. Връща true , ако стекът е празен, false , ако не е.
-
Object peek() методът връща елемента, който е в горната част на стека.
-
Object pop() методът връща елемента, който е в горната част на стека и го премахва.
-
Object push(Object element) методът добавя посочения елемент в горната част на стека.
-
int search(Object element) методът търси в стека посочения елемент. Ако търсеният елемент бъде намерен, се връща неговото „разстояние“ от върха (сериен номер). Ако елементът не бъде намерен, се връща -1.
Пример за стеков code
Нека създадем примерна програма, която работи като gif снимката по-горе. Ще поставим три „топки“, оранжева, лилава и зелена, върху стека. Нека проверим стека за празнота. След това ще извадим топки от стека, докато стекът се изпразни.
import java.util.Stack;
public class myStackTest2 {
public static void main(String[] args)
{
Stack myStack= new Stack<>();
System.out.println("Is my stack empty? " + myStack.empty());
// pushing elements into stack
myStack.push("Orange Ball");
myStack.push("Violet Ball");
myStack.push("Green Ball");
//prints elements of the stack
System.out.println("Elements in Stack: " + myStack);
System.out.println("Is my stack empty? " + myStack.empty());
while (!myStack.isEmpty()) {
myStack.pop();
System.out.println("Elements in Stack: " + myStack);
System.out.println("Is my stack empty? " + myStack.empty());
}
}
}
Ето резултата от тази програма:
import java.util.Stack;
public class myStackTest2 {
public static void main(String[] args)
{
Stack myStack= new Stack<>();
System.out.println("Is my stack empty? " + myStack.empty());
// pushing elements into stack
myStack.add("Orange Ball");
myStack.add("Violet Ball");
myStack.add("Green Ball");
//prints elements of the stack
System.out.println("Elements in Stack: " + myStack);
System.out.println("Is my stack empty? " + myStack.empty());
while (!myStack.isEmpty()) {
myStack.pop();
System.out.println("Elements in Stack: " + myStack);
System.out.println("Is my stack empty? " + myStack.empty());
}
}
}
Резултатът от работата на програмата, разбира се, ще бъде абсолютно същият.
Какво ще кажете за вашата собствена реализация на Stack?
Можете да създадете своя собствена стекова структура от данни в Java, като използвате масиви or класове от свързани списъци. В първия случай се разпределя непрекъснат масив от клетки за съхраняване на стойности в паметта, които се използват при необходимост. Във втория за всеки елемент от стека се подрежда блок памет, достатъчен за съхраняване на стойността и препратките към предишния и следващия елемент на стека. Реализацията, базирана на масив, е по-проста, по-ефективна и с по-голяма ефективност на паметта, но изисква предварително познаване на ограничението за размера на стека и може да доведе до трудни за намиране грешки. Базираното на списък изпълнение е по-стабилно, но по-малко ефективно. Нека направим проста реализация на стека, базирана на масив. Той ще включва функции.-
push — метод, който ще гарантира добавянето на елемент (в най-горната позиция)
-
pop — метод, който ще осигури премахването на елемент (от най-горната позиция)
-
readTop — метод, който ще върне стойността на елемента, който е в горна позиция
-
sEmpty — метод, който ще проверява стека за празнота
-
isFull — метод, който ще провери дали нашият масив, в който съхраняваме стека, не е пълен
import java.util.Arrays;
public class MyStack {
private int maxSize;
private String[] stackArray;
private int top;
public MyStack(int size) {
this.maxSize = size;
stackArray = new String[maxSize];
top = -1;
}
public String push (String element) {
return stackArray[++top] = element;
}
public String pop (String element) {
if (isEmpty())
{
System.out.println("Underflow\nProgram Terminated");
System.exit(-1);
}
System.out.println("Removing " + readTop());
return stackArray[top--];
}
public String readTop() {
return stackArray[top];
}
public boolean isEmpty() {
return (top == -1);
}
public boolean isFull() {
return (top == maxSize - 1);
}
public void printStack(){
System.out.println(Arrays.toString(stackArray));
}
}
Сега нека приложим пример с три топки на базата на нашия стак:
public class myStackTest {
public static void main(String[] args) {
MyStack myStack = new MyStack(3);
System.out.println("Is my stack empty? " + myStack.isEmpty());
myStack.push("Orange Ball");
myStack.push("Violet Ball");
myStack.push("Green Ball");
myStack.printStack();
System.out.println("Is my stack empty? " + myStack.isEmpty());
while (!myStack.isEmpty()) {
myStack.pop(myStack.readTop());
System.out.println("Is my stack empty? " + myStack.isEmpty());
}
}
}
Резултатът е тук:
GO TO FULL VERSION