스택에 대해 알아보도록 하겠습니다.
스택은 자료구조에서 아주 기초이자 중요한 개념입니다. 개념부터 설명하겠습니다.
스택 개념
stack은 사전적 의미는 "쌓다" 입니다. 상자 BOX를 생각하면 쉽게 이해할 수 있습니다.
박스에 책을 쌓는다고 가정하겠습니다. 책은 바닥부터 차례대로 쌓아지겠죠?? 책을 꺼내려면 어떻게 해야할까요!
아마 제일 최근에 쌓은 책을 처음 꺼낼 수 있고, 맨 처음에 넣은 책은 마지막에 꺼낼 수 있을것 같습니다.
그림으로 보면 아래와 같아요!
제일 먼저 넣은 데이터는 1번이고, 제일 마지막에 넣은 데이터는 4번입니다.
데이터를 꺼낼때는 반대로 4번이 제일 처음 나오고 1번이 마지막으로 나올 것입니다
그래서 스택을 "선입후출" , "후입선출" 의 특징을 가지고 있다고 말합니다!
어디에 쓰일까?
그럼 이 스택이라는 자료구조는 어디에 쓰일 수 있을까요??
지금 이 글을 보고 계시는 여러분은 웹사이트를 통해 보고 있을겁니다.
뒤로가기 버튼을 누르면 어떻게 되나요?! 아마 제일 최근에 방문했던 사이트로 이동될것입니다.
즉, 지금 보고 계신 웹사이트주소가 스택의 가장 상단!에 있다고 할 수 있고, 바로 이전에 봤던 사이트주소가 스택에 쌓여있다고 할 수 있죠.
가장 위에 있는 주소를 삭제하고 바로 그 아래 있는 주소를 확인하면, 전 페이지로 갈 수 있는 주소가 나오고 이렇게 뒤로가기를 구현할 수 있습니다!
스택 사용법
스택은 크게 삽입(Push) , 삭제(Pop) , 읽기(Peek) , 스택크기(Size) 로 구성되어 있습니다.
(1) 삽입 (Push)
상자의 맨 위에 데이터를 추가하는 것을 말합니다. 다음 그림을 통해 설명하겠습니다.
현재 3까지 저장되어 있는 스택에 새로운 4를 삽입하는 과정입니다.
구현은 어떻게 하면 될까요? 배열로 구현했다고 가정한다면, 맨 위를 가리키는 인덱스 top을 1증가하고, 그 자리에 새로운 데이터 4를 넣으면 될 것 같습니다.
자세한 구현설명은 아래에서 하겠습니다.
(2) 삭제 (Pop)
스택의 맨 위에 있는 데이터를 삭제하는 과정입니다. 아래 그림을 보면 쉽게 이해할 수 있습니다.
이 역시 구현은 아래에서 설명하겠습니다.
(3) 읽기 (Peek)
맨 상단의 데이터를 확인하는 작업입니다. 만약 아래와 같은 스택이 있다면 Peek을 했을 때 return값은 4가 되겠죠??
(4) 스택크기 (Size)
현재 스택에 몇개의 데이터가 있는지 알고 싶은 경우가 있을 겁니다. 아래와 같은 경우 스택 사이즈는 4개가 되겠네요.
스택은 맨 상단의 데이터만 읽을수 있기 때문에(Peek), 따로 size 변수를 만들어 놓거나 배열로 구현한 경우 맨 상단을 가리키는 top 변수를 이용해서 스택의 크기를 알 수 있습니다.
스택의 구현
스택의 구현 방법은 배열과 연결리스트가 있습니다. 연결리스트에 대해 공부하고 싶은 분은 다음 링크를 통해 확인해주세요!
그럼 언제 배열을 쓰고, 언제 연결리스트를 사용할까요?
이것은 배열과 연결리스트의 장,단점을 확인한 후 정할 수 있습니다.
배열과 연결리스트의 장,단점을 다시 한번 확인하겠습니다.
여러 장, 단점이 있지만 스택에 있어서 두 자료구조의 가장 차이점은 스택의 크기입니다.
위에서 사용한 스택 그림을 다시 한번 확인해보시길 바랍니다.
데이터를 4가지 쌓았는데, 상자가 거의 꽉! 차고 말았습니다. 이와 같이 배열로 구현을 하면 스택의 크기가 제한적이라고 할 수 있습니다.
스택의 최대크기를 알고 있을 때, 최대크기가 너무 크지 않을 때! 배열을 통해 스택을 구현할 수 있습니다.
반대로 연결리스트를 사용하면 스택의 크기에 상관없이 구현할 수 있습니다!
그럼 단점은...? 배열에 비해 구현하기가 번거롭습니다..
어떤 자료구조를 이용해 구현할지는 여러분에게 맡기겠습니다.
(1) 배열을 이용한 스택의 구현
바로 코드를 통해 설명하겠습니다.
#include <iostream>
using namespace std;
#define MAX_SIZE 1000 // 배열의 최대 사이즈를 설정합니다.
void Stack_push(int *stack,int val,int *top){
stack[*top] = val;
*top += 1;
}
int Stack_pop(int *stack, int *top){
*top -= 1;
return stack[*top];
}
int main(){
//Array_stack
int stack[MAX_SIZE];
int top = 0;
int n,val;
cin>>n;
for(int i=0;i<n;i++){
cin>>val;
if(top>=MAX_SIZE){
cout<<"Out of range\n";
cout<<"Cannot Push anymore\n";
}
else{
//STACK_PUSH
Stack_push(stack,val,&top);
cout<<val<<" Push completed\n";
}
}
cout"------------------\n"
for(int i=0;i<n;i++){
// Print current Stack Size
cout<<"Stack Size is : "<<top<<'\n';
if(top>0){
int popvalue = Stack_pop(stack,&top);
cout<<popvalue<<" is removed\n";
}
}
return 0;
}
아마 쉽게 이해하실 수 있을겁니다.
Push할때는 현재 top에 값을 넣고, top의 크기를 1개 늘려주면 됩니다.
반대로 Pop은 top의 크기를 하나 줄여주면 끝입니다!
구현은 쉽지만, 미리 언급 했던것 처럼 다음과 같은 단점이 존재합니다.
- 스택의 사이즈가 제한적
- 스택의 사이즈가 정해져있기 때문에 사용하지 않을 경우 메모리 낭비
그러나 구현하기가 쉬워서 저는 자주 사용합니다!
(2) 연결리스트를 이용한 스택의 구현
단순 연결리스트 데이터 삽입 구현 방법 중 "리스트의 맨 앞에 삽입하기"가 있었습니다.
Push의 구현은 이와 똑같이 하면 됩니다.
다만 삭제(Pop)할 때 무조건 맨 앞에 있는 데이터를 삭제한다고 보면 됩니다.
코드를 통해 설명하겠습니다.
//
// Stack_by_linkedlist.cpp
// Algorithm
//
// Created by seungyun cho on 2017. 11. 12..
// Copyright © 2017년 seungyun cho. All rights reserved.
//
#include <iostream>
using namespace std;
typedef struct Node{
int data;
Node *next;
}Node;
Node *head;
int size_stack = 0;
void Stack_push(int val){
//새로운 노드를 만들고
Node *newNode = new Node;
newNode->data = val;
//리스트의 맨 앞(head)에 연결합니다.
newNode->next = head->next;
head->next = newNode;
size_stack++;
}
int Stack_pop(){
int popvalue;
if(size_stack<1){
return -1;
}
//temp 배열에 맨앞에 노드의 주소를 저장합니다.
Node *temp = head->next;
popvalue = temp->data;
//head를 두번째 노드에 연결시키고
head->next = temp->next;
//첫번째 노드를 삭제합니다.
free(temp);
size_stack--;
return popvalue;
}
int main(){
//head 초기화
head = new Node;
int n;
int val;
cin>>n;
for(int i=0;i<n;i++){
cin>>val;
Stack_push(val);
cout<<val<<" is added\n";
}
cout<<"------------------------------\n";
for(int i=0;i<n;i++){
cout<<"Current stack size is : "<<size_stack<<'\n';
int popvalue = Stack_pop();
if(popvalue==-1){
cout<<"Stack is empty\n";
}
else{
cout<<popvalue<<" is removed\n";
}
}
return 0;
}
위와 같이 구현할 수 있습니다.
stack 사이즈의 경우 리스트를 모두 탐색하려면 시간이 오래 걸리기 때문에 size_stack 변수를 선언하여 push될때 1씩 증가하고, pop될때 1씩 감소하도록 했습니다.
두 가지 구현방법에 대해 알아보았습니다.
설명이 부족했거나 이해가 안되는 부분 있으면 답변 달아주시길 바랍니다.
감사합니다!
'알고리즘 > 자료구조' 카테고리의 다른 글
| 자료구조 : 연결리스트 (Linked list) (1) | 2017.11.08 |
|---|---|
| 다익스트라 알고리즘(Dijkstra) (0) | 2017.10.06 |
