728x90
728x90
https://www.acmicpc.net/problem/10773
난이도: solved.ac 실버 4
이번에는 연결 리스트(Linked List)를 이용해 스택을 구현해보았다
이전에 배열(Array)를 이용해 풀었던 스택 구현 문제 (아래 링크 참고)
https://jangkunstory.tistory.com/2
Linked List로 구현할 때는 push와 pop 모두 Linked List의 head에서 일어난다
새로운 노드를 추가할 때 그 노드가 head가 되게 하고
노드를 제거할 때는 head에서 꺼내는 식이다
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
typedef struct _Node {
int data;
struct _Node* next;
} Node;
typedef struct _Stack {
Node* head;
} Stack;
int main() {
int K, i, j;
int num, sum = 0;
scanf("%d", &K);
/* 스택 초기화 */
Stack stack;
stack.head = NULL;
for (i = 0; i < K; i++) {
scanf("%d", &num);
if (num == 0) { // 스택의 Node를 하나 지움 (pop)
Node* delNode;
int del; // 지울 수
del = stack.head->data;
delNode = stack.head;
sum -= del;
/* 노드 삭제 과정 */
stack.head = stack.head->next;
free(delNode);
}
else { // 스택에 Node를 추가 (push)
sum += num;
Node* newNode = (Node*)malloc(sizeof(Node)); // 새로운 노드 생성
newNode->data = num; // 새로운 노드의 data에 입력 받은 수를 저장
newNode->next = stack.head; // 새로운 노드가 이전의 head를 가리키도록 함
stack.head = newNode; // 새로운 노드를 새로운 head로 임명
}
}
printf("%d", sum);
return 0;
}
반응형