Меню

Урок за стека на Java: Внедряване на клас на стека с примери

  • Основен
  • Други
  • Урок за стека на Java: Внедряване на клас на стека с примери

java stack tutorial stack class implementation with examples

Опитайте Нашия Инструмент За Премахване На Проблемите

Този урок обяснява какво е Stack в Java, Java Stack Class, Stack API Methods, Stack Implementation с помощта на Array & Linked List с помощта на примери:

Стекът е подредена структура от данни, принадлежаща на Java Collection Framework. В тази колекция елементите се добавят и премахват само от единия край. Краят, в който се добавят и премахват елементите, се нарича „Top of the Stack“.

Тъй като добавянето и изтриването се извършват само в единия край, първият елемент, добавен към стека, е последният елемент, премахнат от стека. По този начин стекът се нарича структура на данни LIFO (Last-in, First-out).

=> Погледнете тук ръководството за начинаещи Java

Колекция от стекове в Java

Какво ще научите:

Колекция Java Stack

Изобразително изображение на стека е дадено по-долу.

изобразително представяне на стека

Както е показано в горната последователност на представяне, първоначално стекът е празен и горната част на стека е зададена на -1. След това инициираме операция “push”, която се използва за добавяне на елемент към стека.

често срещани въпроси за интервю за c ++

Така във второто представяне натискаме елемент 10. В този момент горната част се увеличава. Ние отново натискаме елемент 20 в стека, като по този начин увеличаваме горната част.

В последното представяне ние инициираме операция “pop”. Тази операция се използва за премахване на елемент от стека. Елемент, посочен в момента към „Top“, се премахва от операцията за изскачане.

Структурата на стека данни поддържа следните операции:

  • Натиснете: Добавя елемент към стека. В резултат на това стойността на върха се увеличава.
  • Поп: Елемент се отстранява от стека. След операцията за изскачане стойността на върха се намалява.
  • Надникнете: Тази операция се използва за търсене или търсене на елемент. Стойността на върха не се променя.

В горната част на стека, който се използва като край за добавяне / премахване на елементи от стека, също може да има различни стойности в определен момент. Ако размерът на стека е N, тогава горната част на стека ще има следните стойности при различни условия в зависимост от състоянието на стека.

Състояние на стекаНай-висока стойност
Стек празен-1
Един елемент в стека0
Стек пъленN-1
Преливане (елементи> N)н

Клас на стека в Java

Java Collection Framework предоставя клас, наречен “Stack”. Този клас на Stack разширява класа Vector и реализира функционалността на структурата на данни на Stack.

Диаграмата по-долу показва йерархията на класа Stack.

Йерархия на класа на стека в Java

Както е показано на горната диаграма, класът Stack наследява класа Vector, който от своя страна реализира интерфейса List List на Collection.

Класът Stack е част от пакета java.util. За да включим клас Stack в програмата, можем да използваме инструкцията за импортиране, както следва.

import java.util.*;

или

import java.util.Stack;

Създайте стек в Java

След като импортираме класа Stack, можем да създадем обект Stack, както е показано по-долу:

Stack mystack = new Stack();

Също така можем да създадем общ тип обект на клас Stack, както следва:

Stack myStack = new Stack;

Тук data_type може да бъде всеки валиден тип данни в Java.

Например ,можем да създадем следните обекти от клас Stack.

Stack stack_obj = new Stack(); Stack str_stack = new Stack();

Методи на API на стека в Java

Класът на стека предоставя методи за добавяне, премахване и търсене на данни в стека. Той също така предоставя метод за проверка дали стекът е празен. Ще обсъдим тези методи в раздела по-долу.

Операция за натискане на стека

Операцията за натискане се използва за избутване или добавяне на елементи в стека. След като създадем екземпляр на стека, можем да използваме операцията push, за да добавим елементите от типа обект на стека към стека.

Следващата част от кода се използва за инициализиране на цял стек със стойностите.

Stack myStack = new Stack(); myStack.push(10); myStack.push(15); myStack.push(20);

Първоначалният стек, получен в резултат на горното изпълнение на код, е показан по-долу:

начален стек

Ако изпълним друга операция с push (), както е показано по-долу,

push(25);

Полученият стек ще бъде:

Полученият стек

Операция на стек поп

Можем да премахнем елемента от стека, като използваме операцията “pop”. Понастоящем посоченият от върха елемент се изскача от стека.

Следният парче код постига това.

Stack intStack = new Stack(); intStack.push(100); intStack.push(200); int val = intStack.pop();

Променливата val ще съдържа стойността 200, тъй като е последният елемент, избутан в стека.

Представянето на стека за push и pop операция е както следва:

натискане и поп операция

Операция с надникване на стека

Операцията Peek връща горната част на стека, без да премахва елемента. В горния пример за стека “intStack.peek ()” ще върне 200.

Стекът е Празна операция

Операцията isEmpty () на класа Stack проверява дали обектът на стека е празен. Той връща true, ако стека няма елементи в него, иначе връща false.

Операция за търсене на стека

Можем да търсим елемент в стека, като използваме операцията search (). Операцията search () връща индекса на търсения елемент. Този индекс се отчита от горната част на стека.

Stack intStack = new Stack (); intStack.push (100); intStack.push (200); int index = inStack.search(100); //index will have the value 2.

Размер на стека

Размерът на обекта на стека се дава от java.util.Stack.size () метод. Той връща общия брой елементи в стека.

Следващият пример отпечатва размера на стека.

Stack myStack = new Stack(); myStack.push(100); myStack.push(200); myStack.push(300); System.out.println('Stack size:' + myStack.size()); //Stack size: 3

Печат / итерация на елементи на стека

Можем да декларираме итератор за стека и след това да преминем през целия стек, използвайки този итератор. По този начин можем да посетим и отпечатаме всеки елемент на стека един по един.

Следващата програма показва начина за итерация на Stack с помощта на итератор.

import java.util.*; public class Main { public static void main(String() args) { //declare and initialize a stack object Stack stack = new Stack(); stack.push('PUNE'); stack.push('MUMBAI'); stack.push('NASHIK'); System.out.println('Stack elements:'); //get an iterator for the stack Iterator iterator = stack.iterator(); //traverse the stack using iterator in a loop and print each element while(iterator.hasNext()){ System.out.print(iterator.next() + ' '); } } }

Изход:

Елементи на стека:
ПУН МУМБАЙ НАШИК

Изход на стека

Стек, използващ Java 8

Можем също да отпечатваме или пресичаме елементите на стека, като използваме Java 8 функции като Stream APIs, forEach и forEachRemaining конструкции.

Следващата програма демонстрира използването на Java 8 конструкции за преминаване през стека.

import java.util.*; import java.util.stream.*; public class Main { public static void main(String() args) { //declare and initialize a stack object Stack stack = new Stack(); stack.push('PUNE'); stack.push('MUMBAI'); stack.push('NASHIK'); System.out.println('Stack elements using Java 8 forEach:'); //get a stream for the stack Stream stream = stack.stream(); //traverse though each stream object using forEach construct of Java 8 stream.forEach((element) -> { System.out.print(element + ' '); // print element }); System.out.println(' Stack elements using Java 8 forEachRemaining:'); //define an iterator for the stack Iterator stackIterator = stack.iterator(); //use forEachRemaining construct to print each stack element stackIterator.forEachRemaining(val -> { System.out.print(val + ' '); }); } }

Изход:

Елементи на стека с помощта на Java 8 forEach:
ПУН МУМБАЙ НАШИК
Стек елементи с Java 8 forEachRemaining:
ПУН МУМБАЙ НАШИК

изход - стек, използващ Java 8

Внедряване на стека в Java

Следващата програма изпълнява подробния стек, демонстриращ различните операции на стека.

import java.util.Stack; public class Main { public static void main(String a()){ //declare a stack object Stack stack = new Stack(); //print initial stack System.out.println('Initial stack : ' + stack); //isEmpty () System.out.println('Is stack Empty? : ' + stack.isEmpty()); //push () operation stack.push(10); stack.push(20); stack.push(30); stack.push(40); //print non-empty stack System.out.println('Stack after push operation: ' + stack); //pop () operation System.out.println('Element popped out:' + stack.pop()); System.out.println('Stack after Pop Operation : ' + stack); //search () operation System.out.println('Element 10 found at position: ' + stack.search(10)); System.out.println('Is Stack empty? : ' + stack.isEmpty()); } }

Изход:

Първоначален стек: ()
Празен ли е стекът? : вярно
Стек след операция с натискане: (10, 20, 30, 40)
Изскочи елемент: 40
Стек след поп операция: (10, 20, 30)
Елемент 10, намерен на позиция: 3
Стекът е празен? : невярно

изход - изпълнение на стека

как да стартирам jar файлове на Windows 10

Стек за масив в Java

Структурата на данните за стека може да бъде преобразувана в масив, използвайки метода ‘toArray ()’ от класа Stack.

Следващата програма демонстрира това преобразуване.

import java.util.*; import java.util.stream.*; public class Main { public static void main(String() args) { //declare and initialize a stack object Stack stack = new Stack(); stack.push('PUNE'); stack.push('MUMBAI'); stack.push('NASHIK'); //print the stack System.out.println('The Stack contents: ' + stack); // Create the array and use toArray() method to convert stack to array Object() strArray = stack.toArray(); //print the array System.out.println('The Array contents:'); for (int j = 0; j

Изход:

Съдържанието на стека: (PUNE, MUMBAI, NASHIK)
Съдържанието на масива:
ПУН МУМБАЙ НАШИК

изход - СЛЕД В МАСИВ В ЯВА

Внедряване на стека в Java с помощта на масив

Стекът може да бъде реализиран с помощта на масив. Всички операции на стека се извършват с помощта на масив.

Програмата по-долу демонстрира изпълнението на стека с помощта на масив.

import java.util.*; //Stack class class Stack { int top; //define top of stack int maxsize = 5; //max size of the stack int() stack_arry = new int(maxsize); //define array that will hold stack elements Stack(){ //stack constructor; initially top = -1 top = -1; } boolean isEmpty(){ //isEmpty () method return (top <0); } boolean push (int val){ //push () method if(top == maxsize-1) { System.out.println('Stack Overflow !!'); return false; } else { top++; stack_arry(top)=val; return true; } } boolean pop () { //pop () method if (top == -1) { System.out.println('Stack Underflow !!'); return false; } else { System.out.println(' Item popped: ' + stack_arry(top--)); return true; } } void display () { //print the stack elements System.out.println('Printing stack elements .....'); for(int i = top; i>=0;i--) { System.out.print(stack_arry(i) + ' '); } } } public class Main { public static void main(String() args) { //define a stack object Stack stck = new Stack(); System.out.println('Initial Stack Empty : ' + stck.isEmpty()); //push elements stck.push(10); stck.push(20); stck.push(30); stck.push(40); System.out.println('After Push Operation...'); //print the elements stck.display(); //pop two elements from stack stck.pop(); stck.pop(); System.out.println('After Pop Operation...'); //print the stack again stck.display(); } }

Изход:

Първоначален стек празен: вярно
След операция с натискане ...
Печат на елементи на стека ...
40 30 20 10
Изскачащ елемент: 40

Изскачащ елемент: 30
След поп операция ...
Печат на елементи на стека ...
20 10

изход - изпълнение на стека в java с помощта на масив

Внедряване на стека с помощта на свързан списък

Стекът също може да бъде реализиран с помощта на свързан списък, точно както сме направили с помощта на масиви. Едно от предимствата на използването на свързан списък за внедряване на стека е, че той може да расте или да се свива динамично. Не е необходимо да имаме ограничение за максимален размер, както в масивите.

Следващата програма реализира свързан списък за извършване на операции на стека.

import static java.lang.System.exit; // Stack class using LinkedList class Stack_Linkedlist { // Define Node of LinkedList private class Node { int data; // node data Node nlink; // Node link } // top of the stack Node top; // stack class Constructor Stack_Linkedlist() { this.top = null; } // push () operation public void push(int val) { // create a new node Node temp = new Node(); // checks if the stack is full if (temp == null) { System.out.print(' Stack Overflow'); return; } // assign val to node temp.data = val; // set top of the stack to node link temp.nlink = top; // update top top = temp; } // isEmpty () operation public boolean isEmpty() { return top == null; } // peek () operation public int peek() { // check if the stack is empty if (!isEmpty()) { return top.data; } else { System.out.println('Stack is empty!'); return -1; } } // pop () operation public void pop() { // check if stack is out of elements if (top == null) { System.out.print(' Stack Underflow!!'); return; } // set top to point to next node top = (top).nlink; } //print stack contents public void display() { // check for stack underflow if (top == null) { System.out.printf(' Stack Underflow!!'); exit(1); } else { Node temp = top; System.out.println('Stack elements:'); while (temp != null) { // print node data System.out.print(temp.data + '->'); // assign temp link to temp temp = temp.nlink; } } } } public class Main { public static void main(String() args) { // Create a stack class object Stack_Linkedlist stack_obj = new Stack_Linkedlist(); // push values into the stack stack_obj.push(9); stack_obj.push(7); stack_obj.push(5); stack_obj.push(3); stack_obj.push(1); // print Stack elements stack_obj.display(); // print current stack top System.out.println(' Stack top : ' + stack_obj.peek()); // Pop elements twice System.out.println('Pop two elements'); stack_obj.pop(); stack_obj.pop(); // print Stack elements stack_obj.display(); // print new stack top System.out.println(' New Stack top:' + stack_obj.peek()); } }

Изход:

Елементи на стека:
1-> 3-> 5-> 7-> 9->

Стек отгоре: 1
Поп два елемента
Елементи на стека:
5-> 7-> 9->

най-добрият безплатен регистър за почистване на Windows 10

Нов стек отгоре: 5

изход - изпълнение на стека с помощта на свързан списък

често задавани въпроси

В # 1) Какво представляват стековете в Java?

Отговор: Стекът е LIFO (Last in, First out) структура от данни за съхранение на елементи. Елементите на стека се добавят или премахват от стека от единия край, наречен Top of the stack.

Добавянето на елемент към стека се извършва с помощта на операцията Push. Изтриването на елементи се извършва с помощта на операция pop. В Java стекът е реализиран с помощта на класа Stack.

В # 2) Стек ли е колекция в Java?

Отговор: Да. Стекът е наследствена колекция в Java, която се предлага от API на Collection в Java 1.0 нататък. Stack наследява класа Vector на интерфейса List.

В # 3) Стекът интерфейс ли е?

Отговор: Интерфейсният стек е интерфейс, който описва структурата за последно влизане и излизане и се използва за съхраняване на състоянието на рекурсивни проблеми.

В # 4) За какво се използват стекове?

Отговор: Следват основните приложения на стека:

  • Оценка и преобразуване на изрази: стекът се използва за преобразуване на изрази в постфикс, инфикс и префикс. Използва се и за оценка на тези изрази.
  • Стекът се използва и за синтактичен анализ на синтаксисните дървета.
  • Стекът се използва за проверка на скоби в израз.
  • Стекът се използва за решаване на проблеми с обратното проследяване.
  • Извикванията на функции се оценяват с помощта на стекове.

В # 5) Какви са предимствата на стека?

Отговор: Променливите, съхранени в стека, се унищожават автоматично при връщане. Стековете са по-добър избор, когато паметта се разпределя и освобождава. Стековете също почистват паметта. Отделно от това стековете могат да се използват ефективно за оценка на изрази и анализиране на изразите.

Заключение

Това завършва нашия урок за стекове в Java. Класът на стека е част от API за събиране и поддържа операции за натискане, изскачане, надникване и търсене. Елементите се добавят или премахват към / от стека само в единия край. Този край се нарича горната част на стека.

В този урок видяхме всички методи, поддържани от класа на стека. Също така внедрихме стека, използвайки масиви и свързани списъци.

Ще продължим с други класове за събиране в следващите уроци.

=> Прочетете серията Easy Training Training

Препоръчително четене

^