배열을 사용하는 대신 연결리스트를 사용하여 스택을 구현할 수도 있습니다. 연결리스트는 메모리를 동적으로 할당합니다. 그러나 두 시나리오의 시간 복잡도는 모든 작업, 즉 푸시, 팝, 픽에서 동일합니다.

스택의 연결 리스트 구현에서 노드는 메모리에 연속되지 않게 유지됩니다. 각 노드에는 스택의 바로 후속 노드에 대한 포인터가 포함되어 있습니다. 메모리 힙에 남은 공간이 노드를 생성하기에 충분하지 않으면 스택이 오버플로되었다고 합니다.

스택의 최상위 노드에는 항상 주소 필드에 null이 포함됩니다. 스택의 연결리스트 구현에서 각 작업이 수행되는 방식을 논의해 보겠습니다.

스택에 노드 추가(푸시 작업)

스택에 노드를 추가하는 것을 다음과 같이 합니다. 푸시 작업. 연결리스트 구현에서 스택에 요소를 푸시하는 것은 배열 구현과 다릅니다. 요소를 스택에 푸시하려면 다음 단계가 필요합니다.

인터넷이 뭐야?

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 작업)

스택의 맨 위에서 노드를 삭제하는 것을 다음과 같이 합니다. 팝 작업. 스택의 연결 리스트 구현에서 노드를 삭제하는 것은 배열 구현에서와 다릅니다. 스택에서 요소를 팝하려면 다음 단계를 따라야 합니다.

언더플로우 상태를 확인하십시오.언더플로 조건은 이미 비어 있는 스택에서 팝을 시도할 때 발생합니다. 목록의 헤드 포인터가 null을 가리키는 경우 스택은 비어 있습니다.그에 따라 헤드 포인터를 조정합니다.스택에서는 요소가 한쪽 끝에서만 팝되므로 헤드 포인터에 저장된 값을 삭제하고 노드를 해제해야 합니다. 이제 헤드 노드의 다음 노드가 헤드 노드가 됩니다.

시간 복잡도 : 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'); } } 

노드 표시(트래버싱)

스택의 모든 노드를 표시하려면 스택 형태로 구성된 연결 리스트의 모든 노드를 순회해야 합니다. 이를 위해서는 다음 단계를 따라야 합니다.

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; } } }