자료구조 - 연결 리스트(3)
[연결 리스트로 구현한 스택]
이렇게 연결 리스트로 구현된 스택은 연결된 스택(linked stack)이라고 합니다.
배열로 구현하나 연결 리스트로 구현하나 외부 인터페이스는 동일합니다.
하지만 내부에서 구현에 차이가 있는데, 우선 연결 리스트를 사용해서 배열을 만들면 크기가 제한되지 않는다는 장점이 있습니다.
물론 단점도 있는데 동적 메모리 할당이나 해제를 해야하므로 배열로 구현한 스택에 비해 삽입과 삭제에 시간이 더 걸립니다.
노드의 구조 정의
struct Node
{
int data; // 데이터 필드
Node* next; // 다음 노드를 가리키는 포인터
Node(int val)
{
data = val;
next = nullptr;
}
};
[노드의 삽입과 삭제 연산]
연결된 스택에서 삽입 연산(push)
// 스택에 원소를 삽입하는 메서드 (Push)
void push(int value)
{
Node* newNode = new Node(value);
if (top == nullptr)
{
// 스택이 비어 있는 경우
top = newNode;
}
else
{
// 새로운 노드를 스택의 맨 위에 추가
newNode->next = top;
top = newNode;
}
cout << "Pushed " << value << " onto the stack." << endl;
}
(1) 새로운 노드를 생성합니다.
(2) 스택이 비어 있는 경우, 새 노드를 top으로 설정합니다.
(3) 스택이 비어 있지 않은 경우, 새 노드의 next를 현재 top으로 설정하고 top을 새 노드로 업데이트합니다.
연결된 스택에서 삭제 연산(pop)
// 스택에서 원소를 제거하는 메서드 (Pop)
void pop()
{
if (top == nullptr)
{
// 스택이 비어 있는 경우
cout << "Stack is empty. Cannot pop." << endl;
return;
}
else
{
// 스택의 맨 위 원소를 제거
Node* temp = top;
top = top->next;
cout << "Popped " << temp->data << " from the stack." << endl;
delete temp;
}
}
(1) 스택이 비어 있는 경우, 스택이 비어 있음을 알리는 메시지를 출력합니다.
(2) 스택이 비어 있지 않은 경우, top 노드를 임시 포인터에 저장하고 top을 다음 노드로 업데이트합니다
(3) 임시 포인터에 저장된 노드를 삭제합니다.
[연결된 스택 코드]
#include <iostream>
using namespace std;
// 노드 구조 정의
struct Node
{
int data; // 데이터 필드
Node* next; // 다음 노드를 가리키는 포인터
Node(int val)
{
data = val;
next = nullptr;
}
};
// 스택 클래스 정의
class Stack
{
private:
Node* top; // 스택의 맨 위를 가리키는 포인터
public:
Stack()
{
top = nullptr;
}
// 스택에 원소를 삽입하는 메서드 (Push)
void push(int value)
{
Node* newNode = new Node(value);
if (top == nullptr)
{
// 스택이 비어 있는 경우
top = newNode;
}
else
{
// 새로운 노드를 스택의 맨 위에 추가
newNode->next = top;
top = newNode;
}
cout << "Pushed " << value << " onto the stack." << endl;
}
// 스택에서 원소를 제거하는 메서드 (Pop)
void pop()
{
if (top == nullptr)
{
// 스택이 비어 있는 경우
cout << "Stack is empty. Cannot pop." << endl;
return;
}
else
{
// 스택의 맨 위 원소를 제거
Node* temp = top;
top = top->next;
cout << "Popped " << temp->data << " from the stack." << endl;
delete temp;
}
}
// 스택을 출력하는 메서드
void display()
{
if (top == nullptr)
{
cout << "Stack is empty." << endl;
return;
}
Node* temp = top;
cout << "Stack elements: ";
while (temp != nullptr)
{
cout << temp->data << " ";
temp = temp->next;
}
cout << endl;
}
};
int main()
{
Stack stack;
// 스택에 원소 삽입
stack.push(10);
stack.push(20);
stack.push(30);
// 스택 출력
stack.display(); // 출력: Stack elements: 30 20 10
// 스택에서 원소 제거
stack.pop();
stack.pop();
// 스택 출력
stack.display(); // 출력: Stack elements: 10
// 스택에서 원소 제거
stack.pop();
stack.pop(); // 스택이 비어 있어 더 이상 제거할 수 없음
return 0;
}
[연결 리스트로 구현한 큐]
연결 리스트로 만들어진 큐를 연결된 큐(linked queue)라고 합니다.
배열로 구현한 큐에 비해 크기가 제한되지 않는다는 장점을 가지고 있으나, 링크 필드 때문에 메모리 공간을 더 많이 사용합니다.
노드의 구조 정의
struct Node
{
int data; // 데이터 필드
Node* next; // 다음 노드를 가리키는 포인터
Node(int val)
{
data = val;
next = nullptr;
}
};
[노드의 삽입과 삭제 연산]
연결된 큐에서 삽입 연산(enqueue)
void enqueue(int value)
{
Node* newNode = new Node(value);
if (rear == nullptr)
{
front = newNode;
rear = newNode;
}
else
{
rear->next = newNode;
rear = newNode;
}
cout << "Enqueued " << value << " into the queue." << endl;
}
(1) 새로운 노드를 생성합니다.
(2) 큐가 비어 있는 경우, 새 노드를 front 와 rear로 설정합니다.
(3) 스택이 비어 있지 않은 경우, rear의 next를 새 노드로 설정하고 rear을 새 노드로 업데이트합니다.
연결된 큐에서 삭제 연산(dequeue)
void dequeue()
{
if (front == nullptr)
{
cout << "Queue is empty. Cannot dequeue." << endl;
return;
}
else
{
Node* temp = front;
front = front->next;
if (front == nullptr)
{
rear = nullptr;
}
cout << "Dequeued " << temp->data << " from the queue." << endl;
delete temp;
}
}
(1) 큐가 비어 있는 경우, 큐가 비어 있음을 알리는 메시지를 출력합니다.
(2) 큐가 비어 있지 않은 경우, front 노드를 임시 포인터에 저장하고, front를 다음 노드로 업데이트합니다.
(3) front가 nullptr 인 경우, rear도 nullptr로 설정합니다.
(4) 임시 포인터에 저장된 노드를 삭제합니다.
[연결된 큐 코드]
#include <iostream>
using namespace std;
// 노드 구조 정의
struct Node
{
int data; // 데이터 필드
Node* next; // 다음 노드를 가리키는 포인터
Node(int val)
{
data = val;
next = nullptr;
}
};
// 큐 클래스 정의
class Queue
{
private:
Node* front; // 큐의 맨 앞을 가리키는 포인터
Node* rear; // 큐의 맨 끝을 가리키는 포인터
public:
Queue()
{
front = nullptr;
rear = nullptr;
}
// 큐에 원소를 삽입하는 메서드 (Enqueue)
void enqueue(int value)
{
Node* newNode = new Node(value);
if (rear == nullptr)
{
// 큐가 비어 있는 경우
front = newNode;
rear = newNode;
}
else
{
// 새로운 노드를 큐의 맨 끝에 추가
rear->next = newNode;
rear = newNode;
}
cout << "Enqueued " << value << " into the queue." << endl;
}
// 큐에서 원소를 제거하는 메서드 (Dequeue)
void dequeue()
{
if (front == nullptr)
{
// 큐가 비어 있는 경우
cout << "Queue is empty. Cannot dequeue." << endl;
return;
}
else
{
// 큐의 맨 앞 원소를 제거
Node* temp = front;
front = front->next;
if (front == nullptr) {
// 큐가 비어 있는 경우 rear도 nullptr로 설정
rear = nullptr;
}
cout << "Dequeued " << temp->data << " from the queue." << endl;
delete temp;
}
}
// 큐를 출력하는 메서드
void display()
{
if (front == nullptr)
{
cout << "Queue is empty." << endl;
return;
}
Node* temp = front;
cout << "Queue elements: ";
while (temp != nullptr) {
cout << temp->data << " ";
temp = temp->next;
}
cout << endl;
}
};
int main()
{
Queue queue;
// 큐에 원소 삽입
queue.enqueue(10);
queue.enqueue(20);
queue.enqueue(30);
// 큐 출력
queue.display(); // 출력: Queue elements: 10 20 30
// 큐에서 원소 제거
queue.dequeue();
queue.dequeue();
// 큐 출력
queue.display(); // 출력: Queue elements: 30
// 큐에서 원소 제거
queue.dequeue();
queue.dequeue(); // 큐가 비어 있어 더 이상 제거할 수 없음
return 0;
}