TechCodeview

Замість використання масиву ми також можемо використовувати зв’язаний список для реалізації стека. Зв'язаний список динамічно розподіляє пам'ять. Однак часова складність в обох сценаріях однакова для всіх операцій, тобто push, pop і peek.

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

Найвищий вузол у стеку завжди містить значення null у полі адреси. Давайте обговоримо спосіб виконання кожної операції в реалізації зв’язаного списку стека.

Додавання вузла до стеку (операція Push)

Додавання вузла до стеку називається штовхати операція. Переміщення елемента в стек у реалізації пов’язаного списку відрізняється від реалізації масиву. Щоб помістити елемент у стек, потрібно виконати наступні кроки.

1. Спочатку створіть вузол і виділіть йому пам'ять.
2. Якщо список порожній, то елемент має бути надісланий як початковий вузол списку. Це включає в себе призначення значення частині даних вузла та призначення null адресній частині вузла.
3. Якщо в списку вже є кілька вузлів, то ми повинні додати новий елемент на початку списку (щоб не порушити властивість стека). Для цього призначте адресу початкового елемента до поля адреси нового вузла та зробіть новий вузол початковим вузлом списку.

Часова складність: o(1)





Реалізація C:

 void push () { int val; struct node *ptr =(struct node*)malloc(sizeof(struct node)); if(ptr == NULL) { printf('not able to push the element'); } else { printf('Enter the value'); scanf('%d',&val); if(head==NULL) { ptr->val = val; ptr -> next = NULL; head=ptr; } else { ptr->val = val; ptr->next = head; head=ptr; } printf('Item pushed'); } } 

Видалення вузла зі стеку (операція POP)

Видалення вузла з вершини стека називається поп операція. Видалення вузла з реалізації пов’язаного списку стека відрізняється від реалізації масиву. Щоб отримати елемент зі стеку, нам потрібно виконати наступні кроки:

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

Часова складність: o(n)

C реалізація

 void pop() { int item; struct node *ptr; if (head == NULL) { printf('Underflow'); } else { item = head->val; ptr = head; head = head->next; free(ptr); printf('Item popped'); } } 

Відображення вузлів (Traversing)

Щоб відобразити всі вузли стека, потрібно обійти всі вузли пов’язаного списку, організованого у формі стека. Для цього нам потрібно виконати наступні кроки.

1. Скопіюйте головний покажчик у тимчасовий покажчик.
2. Перемістіть тимчасовий вказівник через усі вузли списку та надрукуйте поле значення, додане до кожного вузла.

Часова складність: o(n)

C Реалізація

 void display() { int i; struct node *ptr; ptr=head; if(ptr == NULL) { printf('Stack is empty
'); } else { printf('Printing Stack elements 
'); while(ptr!=NULL) { printf('%d
',ptr->val); ptr = ptr->next; } } } 

Програма на C, керована меню, реалізує всі операції зі стеком за допомогою пов’язаного списку:

 #include #include void push(); void pop(); void display(); struct node { int val; struct node *next; }; struct node *head; void main () { int choice=0; printf('
*********Stack operations using linked list*********
'); printf('
----------------------------------------------
'); while(choice != 4) { printf('

Chose one from the below options...
'); printf('
1.Push
2.Pop
3.Show
4.Exit'); printf('
 Enter your choice 
'); scanf('%d',&choice); switch(choice) { case 1: { push(); break; } case 2: { pop(); break; } case 3: { display(); break; } case 4: { printf('Exiting....'); break; } default: { printf('Please Enter valid choice '); } }; } } void push () { int val; struct node *ptr = (struct node*)malloc(sizeof(struct node)); if(ptr == NULL) { printf('not able to push the element'); } else { printf('Enter the value'); scanf('%d',&val); if(head==NULL) { ptr->val = val; ptr -> next = NULL; head=ptr; } else { ptr->val = val; ptr->next = head; head=ptr; } printf('Item pushed'); } } void pop() { int item; struct node *ptr; if (head == NULL) { printf('Underflow'); } else { item = head->val; ptr = head; head = head->next; free(ptr); printf('Item popped'); } } void display() { int i; struct node *ptr; ptr=head; if(ptr == NULL) { printf('Stack is empty
'); } else { printf('Printing Stack elements 
'); while(ptr!=NULL) { printf('%d
',ptr->val); ptr = ptr->next; } } }