Меню

Підручник зі стеку Java: Реалізація класу стека на прикладах

  • Головна
  • Інший
  • Підручник зі стеку Java: Реалізація класу стека на прикладах

java stack tutorial stack class implementation with examples

Спробуйте Наш Інструмент Для Усунення Проблем

Цей посібник пояснює, що таке стек у Java, клас стека Java, методи стека API, реалізація стека за допомогою масиву та пов'язаного списку за допомогою прикладів:

Стек - це впорядкована структура даних, що належить Java Collection Framework. У цій колекції елементи додаються та видаляються лише з одного кінця. Кінець, коли елементи додаються та видаляються, називається “Top of the Stack”.

Оскільки додавання та видалення здійснюються лише з одного кінця, перший елемент, доданий у стек, є останнім елементом, вилученим із стеку. Таким чином, стек називається структурою даних LIFO (Last-in, First-out).

=> Подивіться тут посібник для початківців Java

Колекція стеків на Java

Що ви дізнаєтесь:

Колекція Java стека

Зображення стека подано нижче.

зображальне зображення стека

Як показано у наведеній вище послідовності подання, спочатку стек порожній, а верхня частина стека встановлена ​​на -1. Потім ми ініціюємо операцію “push”, яка використовується для додавання елемента в стек.

Отже, у другому поданні ми натискаємо елемент 10. У цей момент верх збільшується. Ми знову натискаємо елемент 20 в стопку, тим самим збільшуючи верхню частину.

В останньому поданні ми ініціюємо операцію “поп”. Ця операція використовується для видалення елемента зі стека. Елемент, який в даний час вказує на 'Top', видаляється операцією pop.

Структура даних стека підтримує такі операції:

  • Натисніть: Додає елемент у стек. В результаті значення верху збільшується.
  • Поп: Елемент вилучається зі стопки. Після операції pop, значення верху зменшується.
  • Загляньте: Ця операція використовується для пошуку або пошуку елемента. Значення верху не змінюється.

Верх стека, який використовується як кінець для додавання / видалення елементів зі стека, також може мати різні значення в певний момент. Якщо розмір стека дорівнює N, тоді верх стека матиме наступні значення при різних умовах, залежно від того, в якому стані знаходиться стек.

Статус стекаНайвища цінність
Стек порожній-1
Один елемент у стосі0
Стек повнийN-1
Переповнення (елементи> N)N

Клас стека в Java

Java Collection Framework пропонує клас із назвою “Стек”. Цей клас Stack розширює клас Vector і реалізує функціональність структури даних Stack.

На діаграмі нижче показано ієрархію класу Stack.

Ієрархія класу стека в Java

Як показано на наведеній вище схемі, клас Stack успадковує клас Vector, який, у свою чергу, реалізує інтерфейс List of Collection.

Клас Stack є частиною пакету java.util. Щоб включити клас Stack до програми, ми можемо використати оператор import наступним чином.

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

Клас Stack надає методи додавання, видалення та пошуку даних у Stack. Він також надає метод перевірки, чи стек порожній. Ми обговоримо ці методи в розділі нижче.

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

Операція натискання використовується для натискання або додавання елементів у стек. Після того, як ми створимо екземпляр стека, ми можемо використовувати операцію push для додавання елементів типу об’єкта стека до стеку.

Наступний фрагмент коду використовується для ініціалізації цілочисельного стека зі значеннями.

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

Початковий стек, отриманий в результаті виконання вищезазначеного фрагмента коду, показаний нижче:

початковий стек

Якщо ми виконаємо ще одну операцію push (), як показано нижче,

push(25);

Отриманий стек буде:

Отриманий стек

Стек поп-операція

Ми можемо вилучити елемент зі стека за допомогою операції “спливаюче”. Елемент, на який вказує Top в даний час, вискакує з стека.

Наступний фрагмент коду досягає цього.

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

Змінна val буде містити значення 200, оскільки це був останній елемент, всунутий у стек.

Представлення стеку для операцій push і pop є наступним:

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

Операція заглядання стека

Операція заглядання повертає верх стека, не виймаючи елемент. У наведеному вище прикладі стека “intStack.peek ()” поверне 200.

Стек isEmpty Operation

Операція 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.

Розмір стека

Розмір об'єкта Stack задається символом 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

Вивід стека

Стек за допомогою Java 8

Ми також можемо надрукувати або перекласти елементи стека, використовуючи такі функції Java 8, як Stream API, 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
Стек порожній? : помилковий

вихід - Впровадження стека

Стек для масиву в 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(); } }

Вихід:

Початковий стек порожній: true
Після натискання ...
Друк елементів стека ... ..
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->

Нова верхня частина стека: 5

вихід - реалізація стека за допомогою пов

Часті запитання

Q # 1) Що таке стеки в Java?

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

Додавання елемента в стек здійснюється за допомогою операції Push. Видалення елементів здійснюється за допомогою операції pop. У Java стек реалізований за допомогою класу Stack.

Питання 2) Чи стек є колекцією на Java?

Відповідь: Так. Стек - це застаріла колекція на Java, яка доступна від Collection API в Java 1.0 і далі. Стек успадковує клас Vector інтерфейсу List.

Q # 3) Чи є стек інтерфейсом?

Відповідь: Інтерфейсний стек - це інтерфейс, який описує структуру, що входила, виходила, і використовується для зберігання стану рекурсивних проблем.

Q # 4) Для чого використовуються стеки?

Відповідь: Ось основні програми стека:

  • Оцінка виразу та перетворення: стек використовується для перетворення виразів у постфікс, інфікс та префікс. Він також використовується для оцінки цих виразів.
  • Стек також використовується для синтаксичного аналізу дерев синтаксису.
  • Стек використовується для перевірки дужок у виразі.
  • Стек використовується для вирішення проблем зворотного відстеження.
  • Виклики функцій обчислюються за допомогою стеків.

Q # 5) Які переваги стека?

Відповідь: Змінні, що зберігаються в стеку, автоматично повертаються при поверненні. Стеки є кращим вибором, коли пам’ять виділяється та вивільняється. Стеки також очищають пам’ять. Окрім цього, стеки можна ефективно використовувати для оцінки виразів та синтаксичного аналізу виразів.

Висновок

На цьому наш підручник зі стеків у Java завершено. Клас стека є частиною API колекції та підтримує операції push, pop, peek та пошуку. Елементи додаються або видаляються в / зі стеку лише з одного кінця. Цей кінець називається вершиною стека.

У цьому посібнику ми побачили всі методи, що підтримуються класом стека. Ми також реалізували стек, використовуючи масиви та пов'язані списки.

Ми будемо продовжувати інші класи колекцій у наступних підручниках.

=> Прочитайте серію Easy Java Training

Рекомендована література

^