logo

TechCodeview

Що таке структура стекових даних? Повний підручник

Структура стекових даних це лінійна структура даних що слідує Принцип LIFO (останній прийшов, перший вийшов). , тож останній вставлений елемент є першим, що вискочить. У цій статті ми розглянемо всі основи стека, операції зі стеком, його реалізацію, переваги та недоліки, що допоможе вам вирішити всі проблеми на основі стека.

Зміст



Що таке структура стекових даних?

Стек це лінійна структура даних на основі Принцип LIFO (останній прийшов - першим вийшов). у якому вставка нового елемента та видалення існуючого елемента відбувається на тому самому кінці, що представлений зверху стека.

Щоб реалізувати стек, необхідно підтримувати покажчик на вершину стека , який є останнім елементом, який буде вставлено, оскільки ми можемо отримати доступ до елементів лише у верхній частині стека.

Представлення структури стекових даних:

Стек дотримується принципу LIFO (останній прийшов, перший вийшов), тому елемент, який надсилається останнім, виривається першим.

Стек фіксованого розміру : Як випливає з назви, стек фіксованого розміру має фіксований розмір і не може динамічно збільшуватися або зменшуватися. Якщо стек заповнений і робиться спроба додати до нього елемент, виникає помилка переповнення. Якщо стек порожній і робиться спроба видалити з нього елемент, виникає помилка недоповнення.
  • Стек динамічного розміру : стек динамічного розміру може динамічно зростати або зменшуватися. Коли стек заповнений, він автоматично збільшує його розмір для розміщення нового елемента, а коли стек порожній, він зменшує його розмір. Цей тип стека реалізовано за допомогою пов’язаного списку, оскільки він дозволяє легко змінювати розмір стека.

    • Основні операції зі стеком Структура даних :

    Для того, щоб виконувати маніпуляції в стеку, нам надаються певні операції.

    java відкриває файл
    • push() щоб вставити елемент у стек
    • поп() щоб видалити елемент зі стеку
    • топ() Повертає верхній елемент стека.
    • пусто() повертає true, якщо стек порожній, інакше false.
    • isFull() повертає true, якщо стек заповнений, else false.

    Алгоритм роботи Push:

    • Перш ніж помістити елемент у стек, ми перевіряємо, чи є стек повний .
    • Якщо стек повний (верх == місткість-1) , потім Переповнення стека і ми не можемо вставити елемент у стек.
    • В іншому випадку ми збільшуємо значення top на 1 (верх = верх + 1) і нове значення вставляється в верхня позиція .
    • Елементи можна вставляти в стек, поки ми не досягнемо місткість стека.

    Алгоритм роботи Pop:

    • Перш ніж витягти елемент зі стеку, ми перевіряємо, чи є стек порожній .
    • Якщо стек порожній (верх == -1), тоді Перетікання стека і ми не можемо видалити жоден елемент зі стеку.
    • В іншому випадку ми зберігаємо значення top, зменшуючи значення top на 1 (верх = верх – 1) і повертає збережене верхнє значення.

    Алгоритм верхньої операції:

    • Перед поверненням верхнього елемента зі стеку ми перевіряємо, чи стек порожній.
    • Якщо стек порожній (верх == -1), ми просто друкуємо стек порожній.
    • В іншому випадку ми повертаємо елемент, що зберігається в індекс = верх .

    Алгоритм для операції isEmpty :

    • Перевірте значення зверху в стеку.
    • Якщо (верх == -1) , то стек є порожній так повертайся правда .
    • В іншому випадку стек не порожній, тому поверніться помилковий .

    Алгоритм роботи isFull:

    • Перевірте значення зверху в стеку.
    • Якщо (верх == ємність-1), то стек є повний так повертайся правда .
    • В іншому випадку стек не заповнений, тому поверніться помилковий .

    Реалізація стека Структура даних :

    Основні операції, які можна виконувати зі стеком, включають push, pop і peek. Є два способи реалізації стека –

    • Використання масиву
    • Використання пов’язаного списку

    У реалізації на основі масиву операція push реалізується шляхом збільшення індексу верхнього елемента та збереження нового елемента за цим індексом. Операція pop реалізується шляхом повернення значення, що зберігається у верхньому індексі, а потім зменшення індексу верхнього елемента.

    У реалізації на основі пов’язаного списку операція push реалізується шляхом створення нового вузла з новим елементом і встановлення наступного покажчика поточного верхнього вузла на новий вузол. Операція pop реалізується встановленням наступного покажчика поточного верхнього вузла на наступний вузол і поверненням значення поточного верхнього вузла.

    /* C++ програма для реалізації базового стеку операції */ #включати #включати використовуючи простір імен станд; #define MAX 1000 клас Стек { внутр зверху; громадськість: внутр a[МАКС]; // Максимальний розмір стека Стек() { зверху = -1; } bool штовхати(внутр х); внутр поп(); внутр підглядати(); bool пусто(); }; bool Stack::push(внутр х) { якщо (зверху >= (МАКС - 1)) { cout << 'stack=''переповнення'<='' span=''>; повернення помилковий; } інше { a[++зверху] = х; cout << х << ' поміщено в стек '; повернення правда; } } внутр Stack::pop() { якщо (зверху < 0) { cout << 'Stack Underflow'; повернення 0; } інше { внутр х = a[зверху--]; повернення х; } } внутр Stack::peek() { якщо (зверху < 0) { cout << «Стопка порожня»; повернення 0; } інше { внутр х = a[зверху]; повернення х; } } bool Stack::isEmpty() { повернення (зверху < 0); } // Програма драйвера для перевірки вищезазначених функцій внутр основний() { клас Стек с; с.штовхати(10); с.штовхати(двадцять); с.штовхати(30); cout << с.поп() << ' Вискочив зі стека '; //надрукувати верхній елемент стека після видалення cout << 'Верхній елемент:' << с.підглядати() << endl; //надрукувати всі елементи в стеку: cout <<'Елементи в стеку:'; поки(!с.пусто()) { // надрукувати верхній елемент у стеку cout << с.підглядати() <<' '; // видалити верхній елемент у стеку с.поп(); } повернення 0; } //Код змінено Вінаєм ПандіC 
    // C program for array implementation of stack #include  #include  #include  // A structure to represent a stack struct Stack {  int top;  unsigned capacity;  int* array; }; // function to create a stack of given capacity. It initializes size of // stack as 0 struct Stack* createStack(unsigned capacity) {  struct Stack* stack = (struct Stack*)malloc(sizeof(struct Stack));  stack->емкость = місткість;  стек->верх = -1;  stack->array = (int*)malloc(stack->capacity * sizeof(int));  зворотний стек; } // Стек заповнений, коли top дорівнює останньому індексу int isFull(struct Stack* stack) { return stack->top == stack->capacity - 1; } // Стек порожній, коли top дорівнює -1 int isEmpty(struct Stack* stack) { return stack->top == -1; } // Функція для додавання елемента в стек. Він збільшує вершину на 1 void push(struct Stack* stack, int item) { if (isFull(stack)) return;  стек->масив[++стек->верх] = елемент;  printf('%d поміщено в стек
', елемент); } // Функція видалення елемента зі стека. Він зменшує вершину на 1 int pop(struct Stack* stack) { if (isEmpty(stack)) return INT_MIN;  повернути стек->масив[стек->верх--]; } // Функція повернення вершини зі стеку без її видалення int peek(struct Stack* stack) { if (isEmpty(stack)) return INT_MIN;  повернути стек->масив[стек->верх]; } // Програма драйвера для тестування вищевказаних функцій int main() { struct Stack* stack = createStack(100);  push(стек, 10);  push(stack, 20);  push(стек, 30);  printf('%d вилучено зі стека
', pop(stack));  повернути 0; }>
    Java 
    /* Java program to implement basic stack operations */ class Stack {  static final int MAX = 1000;  int top;  int a[] = new int[MAX]; // Maximum size of Stack  boolean isEmpty()  {  return (top < 0);  }  Stack()  {  top = -1;  }  boolean push(int x)  {  if (top>= (MAX - 1)) { System.out.println('Переповнення стека');  повернути false;  } else { a[++top] = x;  System.out.println(x + ' поміщено в стек');  повернути істину;  } } int pop() { if (top< 0) {  System.out.println('Stack Underflow');  return 0;  }  else {  int x = a[top--];  return x;  }  }  int peek()  {  if (top < 0) {  System.out.println('Stack Underflow');  return 0;  }  else {  int x = a[top];  return x;  }  }    void print(){  for(int i = top;i>-1;i--){ System.out.print(' '+ a[i]);  } } } // Код драйвера class Main { public static void main(String args[]) { Stack s = new Stack();  s.push(10);  s.push(20);  s.push(30);  System.out.println(s.pop() + ' Витягнутий зі стека');  System.out.println('Верхній елемент:' + s.peek());  System.out.print('Елементи в стеку:');  s.print();  } } //Цей код змінено Vinay Pandey>
    Python 
    # Python program for implementation of stack # import maxsize from sys module  # Used to return -infinite when stack is empty from sys import maxsize # Function to create a stack. It initializes size of stack as 0 def createStack(): stack = [] return stack # Stack is empty when stack size is 0 def isEmpty(stack): return len(stack) == 0 # Function to add an item to stack. It increases size by 1 def push(stack, item): stack.append(item) print(item + ' pushed to stack ') # Function to remove an item from stack. It decreases size by 1 def pop(stack): if (isEmpty(stack)): return str(-maxsize -1) # return minus infinite return stack.pop() # Function to return the top from stack without removing it def peek(stack): if (isEmpty(stack)): return str(-maxsize -1) # return minus infinite return stack[len(stack) - 1] # Driver program to test above functions  stack = createStack() push(stack, str(10)) push(stack, str(20)) push(stack, str(30)) print(pop(stack) + ' popped from stack')>
    C# 
    // C# program to implement basic stack // operations using System; namespace ImplementStack { class Stack {  private int[] ele;  private int top;  private int max;  public Stack(int size)  {  ele = new int[size]; // Maximum size of Stack  top = -1;  max = size;  }  public void push(int item)  {  if (top == max - 1) {  Console.WriteLine('Stack Overflow');  return;  }  else {  ele[++top] = item;  }  }  public int pop()  {  if (top == -1) {  Console.WriteLine('Stack is Empty');  return -1;  }  else {  Console.WriteLine('{0} popped from stack ',  ele[top]);  return ele[top--];  }  }  public int peek()  {  if (top == -1) {  Console.WriteLine('Stack is Empty');  return -1;  }  else {  Console.WriteLine('{0} popped from stack ',  ele[top]);  return ele[top];  }  }  public void printStack()  {  if (top == -1) {  Console.WriteLine('Stack is Empty');  return;  }  else {  for (int i = 0; i <= top; i++) {  Console.WriteLine('{0} pushed into stack',  ele[i]);  }  }  } } // Driver program to test above functions class Program {  static void Main()  {  Stack p = new Stack(5);  p.push(10);  p.push(20);  p.push(30);  p.printStack();  p.pop();  } } }>
    Javascript 
    /* javascript program to implement basic stack operations  */  var t = -1;  var MAX = 1000;  var a = Array(MAX).fill(0); // Maximum size of Stack  function isEmpty() {  return (t < 0);  }  function push(x) {  if (t>= (МАКС - 1)) { console.log('Переповнення стека');  повернути false;  } else { t+=1;  a[t] = x;    console.log(x + ' поміщено в стек ');  повернути істину;  } } функція pop() { if (t< 0) {  console.log('Stack Underflow');  return 0;  } else {  var x = a[t];  t-=1;  return x;  }  }  function peek() {  if (t < 0) {  console.log('Stack Underflow');  return 0;  } else {  var x = a[t];  return x;  }  }  function print() {  for (i = t; i>-1; i--) { console.log(' ' + a[i]);  } } push(10);  push(20);  push(30);  console.log(pop() + ' Витягнуто зі стека');  console.log(' Верхній елемент:' + peek());  console.log(' Елементи, присутні в стеку: ');  друкувати(); // Цей код надано Rajput-Ji>>>  
      Вихід  
    10 pushed into stack 20 pushed into stack 30 pushed into stack 30 Popped from stack Top element is : 20 Elements present in stack : 20 10>
          
        Переваги реалізації масиву:    
     
    • Легко реалізувати.
    • Пам'ять зберігається, оскільки покажчики не задіяні.
        Недоліки реалізації масиву:    
     
    • Він не динамічний, тобто не зростає і не зменшується залежно від потреб під час виконання. [Але у випадку масивів динамічного розміру, таких як вектор у C++, список у Python, ArrayList у Java, стеки також можуть збільшуватися та зменшуватися за допомогою реалізації масиву].
    • Загальний розмір стека повинен бути визначений заздалегідь.

    // C++ програма для зв'язаного списку реалізації стека #включати використовуючи простір імен станд; // Структура для представлення стека клас StackNode { громадськість: внутр даних; StackNode* наступний; }; StackNode* newNode(внутр даних) { StackNode* stackNode = новий StackNode(); stackNode->даних = даних; stackNode->наступний = НУЛЬ; повернення stackNode; } внутр пусто(StackNode* корінь) { повернення !корінь; } недійсний штовхати(StackNode** корінь, внутр даних) { StackNode* stackNode = newNode(даних); stackNode->наступний = *корінь; *корінь = stackNode; cout << даних << ' pushed='' to='' стек<='' span=''> '; } внутр поп(StackNode** корінь) { якщо (пусто(*корінь)) повернення INT_MIN; StackNode* темп = *корінь; *корінь = (*корінь)->наступний; внутр вискочив = темп->даних; безкоштовно(темп); повернення вискочив; } внутр підглядати(StackNode* корінь) { якщо (пусто(корінь)) повернення INT_MIN; повернення корінь->даних; } // Код драйвера внутр основний() { StackNode* корінь = НУЛЬ; штовхати(&корінь, 10); штовхати(&корінь, двадцять); штовхати(&корінь, 30); cout << поп(&корінь) << ' вискочив зі стека '; cout << 'Верхній елемент - це' << підглядати(корінь) << endl; cout <<'Елементи в стеку:'; //надрукувати всі елементи в стеку: поки(!пусто(корінь)) { // надрукувати верхній елемент у стеку cout << підглядати(корінь) <<' '; // видалити верхній елемент у стеку поп(&корінь); } повернення 0; } // Цей код створено rathbhupendraC 
    // C program for linked list implementation of stack #include  #include  #include  // A structure to represent a stack struct StackNode {  int data;  struct StackNode* next; }; struct StackNode* newNode(int data) {  struct StackNode* stackNode =   (struct StackNode*)  malloc(sizeof(struct StackNode));  stackNode->дані = дані;  stackNode->next = NULL;  повернення stackNode; } int isEmpty(struct StackNode* root) { return !root; } void push(struct StackNode** root, int data) { struct StackNode* stackNode = newNode(data);  stackNode->next = *root;  *корінь = stackNode;  printf('%d відправлено в стек
', дані); } int pop(struct StackNode** root) { if (isEmpty(*root)) return INT_MIN;  struct StackNode* temp = *root;  *корінь = (*корінь)->наступний;  int popped = temp->data;  вільний (temp);  повернення вискочив; } int peek(struct StackNode* root) { if (isEmpty(root)) return INT_MIN;  повернути root->data; } int main() { struct StackNode* root = NULL;  push(&root, 10);  push(&root, 20);  push(&root, 30);  printf('%d вилучено зі стека
', pop(&root));  printf('Верхній елемент %d
', peek(root));  повернути 0; }>
    Java 
    // Java Code for Linked List Implementation public class StackAsLinkedList {  StackNode root;  static class StackNode {  int data;  StackNode next;  StackNode(int data) { this.data = data; }  }  public boolean isEmpty()  {  if (root == null) {  return true;  }  else  return false;  }  public void push(int data)  {  StackNode newNode = new StackNode(data);  if (root == null) {  root = newNode;  }  else {  StackNode temp = root;  root = newNode;  newNode.next = temp;  }  System.out.println(data + ' pushed to stack');  }  public int pop()  {  int popped = Integer.MIN_VALUE;  if (root == null) {  System.out.println('Stack is Empty');  }  else {  popped = root.data;  root = root.next;  }  return popped;  }  public int peek()  {  if (root == null) {  System.out.println('Stack is empty');  return Integer.MIN_VALUE;  }  else {  return root.data;  }  }  // Driver code  public static void main(String[] args)  {  StackAsLinkedList sll = new StackAsLinkedList();  sll.push(10);  sll.push(20);  sll.push(30);  System.out.println(sll.pop()  + ' popped from stack');  System.out.println('Top element is ' + sll.peek());    sll.push(10);  sll.push(20);  sll.push(30);  System.out.println(sll.pop()  + ' popped from stack');  System.out.println('Top element is ' + sll.peek());  } }>
    Python 
    # Python program for linked list implementation of stack # Class to represent a node class StackNode: # Constructor to initialize a node def __init__(self, data): self.data = data self.next = None class Stack: # Constructor to initialize the root of linked list def __init__(self): self.root = None def isEmpty(self): return True if self.root is None else False def push(self, data): newNode = StackNode(data) newNode.next = self.root self.root = newNode print ('% d pushed to stack' % (data)) def pop(self): if (self.isEmpty()): return float('-inf') temp = self.root self.root = self.root.next popped = temp.data return popped def peek(self): if self.isEmpty(): return float('-inf') return self.root.data # Driver code stack = Stack() stack.push(10) stack.push(20) stack.push(30) print ('% d popped from stack' % (stack.pop())) print ('Top element is % d ' % (stack.peek())) # This code is contributed by Nikhil Kumar Singh(nickzuck_007)>
    C# 
    // C# Code for Linked List Implementation using System; public class StackAsLinkedList {  StackNode root;  public class StackNode {  public int data;  public StackNode next;  public StackNode(int data) { this.data = data; }  }  public bool isEmpty()  {  if (root == null) {  return true;  }  else  return false;  }  public void push(int data)  {  StackNode newNode = new StackNode(data);  if (root == null) {  root = newNode;  }  else {  StackNode temp = root;  root = newNode;  newNode.next = temp;  }  Console.WriteLine(data + ' pushed to stack');  }  public int pop()  {  int popped = int.MinValue;  if (root == null) {  Console.WriteLine('Stack is Empty');  }  else {  popped = root.data;  root = root.next;  }  return popped;  }  public int peek()  {  if (root == null) {  Console.WriteLine('Stack is empty');  return int.MinValue;  }  else {  return root.data;  }  }  // Driver code  public static void Main(String[] args)  {  StackAsLinkedList sll = new StackAsLinkedList();  sll.push(10);  sll.push(20);  sll.push(30);  Console.WriteLine(sll.pop() + ' popped from stack');  Console.WriteLine('Top element is ' + sll.peek());  } } /* This code contributed by PrinciRaj1992 */>
    Javascript 
    >
    Вихід Переваги впровадження пов’язаного списку:

    • Реалізація зв’язаного списку стека може збільшуватися та зменшуватися відповідно до потреб під час виконання.
    • Він використовується в багатьох віртуальних машинах, таких як JVM.

    Недоліки реалізації пов’язаного списку:

    • Вимагає додаткової пам'яті через залучення покажчиків.
    • Довільний доступ неможливий у стеку.

    Аналіз складності операцій над структурою даних стека:

    Операції Часова складність

    Космічна складність

    push() О(1)

    О(1)

    поп() О(1)

    О(1)

    sql порядок за датою

    top() або пописати k()

    О(1)

    О(1)

    пусто()О(1)

    О(1)

    isFull()О(1)

    О(1)

    Переваги Stack Структура даних :

    • Простота: Стеки є простою та легкою для розуміння структурою даних, що робить їх придатними для широкого спектру програм.
    • Ефективність: Операції push і pop на стеку можна виконувати в постійному часі (O(1)) , забезпечуючи ефективний доступ до даних.
    • Останній увійшов, перший вийшов (LIFO): Стеки відповідають принципу LIFO, гарантуючи, що останній елемент, доданий до стека, є першим видаленим. Така поведінка корисна в багатьох сценаріях, таких як виклики функцій і оцінка виразів.
    • Обмежене використання пам'яті: Стекам потрібно зберігати лише ті елементи, які були вставлені в них, що робить їх ефективнішими за використання пам’яті порівняно з іншими структурами даних.

    Недоліки Stack Структура даних :

    • Обмежений доступ: Доступ до елементів у стеку можливий лише зверху, що ускладнює отримання або зміну елементів у середині стека.
    • Можливість переповнення: Якщо в стек буде розміщено більше елементів, ніж він може вмістити, виникне помилка переповнення, що призведе до втрати даних.
    • Не підходить для довільного доступу: Стек s не дозволяють довільний доступ до елементів, що робить їх непридатними для додатків, де доступ до елементів потрібно здійснювати в певному порядку.
    • Обмежена місткість: Стеки мають фіксовану місткість, що може бути обмеженням, якщо кількість елементів, які потрібно зберігати, невідома або сильно змінюється.

    Застосування структури стекових даних:

    • Інфікс до постфіксу /Префіксне перетворення
    • Функції повторного скасування в багатьох місцях, як-от редактори, Photoshop.
    • Функції прямого та зворотного перегляду у веб-браузерах
    • У управлінні пам’яттю будь-який сучасний комп’ютер використовує стек як основне керування для цілей роботи. Кожна програма, яка виконується в комп’ютерній системі, має власний розподіл пам’яті.
    • Стек також допомагає реалізувати виклик функцій на комп’ютерах. Остання викликана функція завжди виконується першою.

    Пов'язані статті:

    • Реалізуйте стек за допомогою однозв’язаного списку
    • Основні операції в структурі стекових даних із реалізаціями
    • 50 найпоширеніших проблем зі структурою стекових даних в інтерв’ю SDE
    • Застосування, переваги та недоліки Stack
    • Стек для конкурентного програмування