Stack 이란
- 스택(Stack)과 큐(Queue)는 컴퓨터 공학에서 가장 기본이 되는 자료구조이다.
- 말 그대로 자료를 표현하고 처리하는 방법에 관한 것이다.
- 예를 들어 스택은
택배 상하차, 큐는은행창구 - 스택: 먼저 들어온 데이터가 나중에 나가는 자료구조
- 흔히 박스가 쌓인 형태를 스택(stack)이라고 한다.
- 우리가박스를쌓은뒤에꺼낼때는,가장마지막에올렸던박스부터꺼내야한다.
후입선출(LIFO: Last First-Out)
- 스택의 가장 큰 특징은
후입선출 - 가장 최근에 들어온 데이터가 가장 먼저 나간다는 의미
- 반대로 먼저 들어온 데이터가 먼저
Queue와의 가장 큰 차이점
Stack vs. Queue vs. list
스택, 큐 모두 리스트 자료구조의 특별한 경우이며, 이들 간에는 공통점과 차이점을 지닌다.
스택의 구조 & 사용
- 스택은 자료의 출력 순서가 입력 순서의 역순으로 이루어질 때 요긴하게 사용되는 자료 구조이다.
- 문서 편집기에서
undo(되돌리기)기능을 구현하면 바로 최근에 실행되었던 작업이 취소가 된다.
- 상단 (stack up) : 스택에서 입출력이 이루어지는 부분
- 하단 (stack bottom) : 반대쪽 바닥 부분
- 요소 (element) : 스택에 저장되는 것
- 공백 스택 (empty stack) : 공백 상태의 스택
- 포화 스택 (full stack) : 포화 상태의 스택(풀스택)
스택(stack) 함수 호출
1) 복귀주소 기억
: 함수의 실행이 끝나면 자신을 호출한 함수로 되돌아간다. 이 때 스택은 복귀할 주소를 기억하는대 사용. 함수는 호출된 역순으로 되돌아가야 하기 때문에.
2) 활성 레코드
: 시스템 스택에는 함수가 호출될 때마다 활성 레코드가 만들어지며, 이곳에서 복귀주소가 저장된다.
-
복귀 주소
-
프로그램 카운터
-
매개변수
-
함수 안에서 선언된 지역변수
-
사용 예시 : Undo 기능, 괄호검사, 계산기, 미로탐색 등
스택 추상자료형
- 스택을 추상 자료형으로 정의해 보았을 때, 스택은 후입선출(LIFO)의 접근방법을 유지하는 0개 이상의 요소를 지닌 선형 리스트의 일종이라고 할 수 있다.
1) 스택 ADT(추상데이터타입)
- 객체: n개의 요소(element)들의 선형 리스트
2) 스택의 연산
- 스택에 요소를 추가/ 삭제하는 연산과 현재 스택 상태를 검사하는 연산들로 구성된다.
스택의 정적/ 동적 구현
1. 스택의 정적 구현: 1차원 배열 사용
1) 스택의 생성
- top : 가장 최근에 입력되었던 자료를 가리키는 변수
- stack[0]...stack[top] : 먼저 들어온 순으로 저장
- 공백 상태: top = -1
// 1차원 배열의 사용
# define MAX_STACK_SIZE 100
int stack[MAX_STACK_SIZE];
/* top의 초기 값은 스택이 비어있을 때 -1 이다. */
int top = -1;
2) 스택의 삽입(Push)
void push(int item)
{
if (top >= MAX_STACK_SIZE - 1) {
stack_full();
return;
}
stack[++top] = item;
// top ++; stack[top] = item;
}// push(x)
if is_full(S)
then error "overflow"
else top <- top + 1
data[top] <- x
3) 스택의 삭제(Pop)
int pop() {
if (top == -1)
return stack_empty();
// int x; x = stack[top]; top--; return x;
return stack[top--];
}
// pop()
if is_empty()
then error "underflow"
else e <- data[top]
top <- top-1
return e
4) 스택의 검사 (isempty/isfull)
// 스택이 비어있는지 검사하는 함수
int isempty()
{ if (top < 0)
return(1);
else
return(0);
}
// 스택이 가득 차 있는지 검사하는 함수
int isfull()
{ if (top >= MAX_STACK_SIZE -1 )
return(1);
else
return(0);
}정리하기
let stack = [];
// 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()
stack.push(5);
stack.push(2); // [실행 결과]
stack.push(3); // [1, 3, 2, 5]
stack.push(7); // [5, 2, 3, 1]
stack.pop();
stack.push(1);
stack.push(4);
stack.pop();
let reversed = stack.slice().reverse();
console.log(reversed); // 최상단 원소부터 출력 console.log(stack);
#include <iostream> 정의
#include <stack> // stack 라이브러리 사용하겠다고 정의한 것임
using namespace std;
int main(void) {
stack<int> s; // stack 하나 만들고
s.push(7); // push 함수를 이용해 삽입
s.push(5);
s.push(4);
s.pop(); // 꺼내고
s.push(6);
s.pop();
while(!s.empty()) { // stack이 비어있을 때까지
count << s.top() << ' '; // stack 의 가장 위쪽에 있는 데이터를 출력
s.pop(); // 출력 이후 해당 데이터를 꺼내고 확인
}
return 0; // 5 7 출력
}
연결 리스트로 스택 구현
• 스택을연결리스트로구현하면,삽입과삭제에있어서𝑂 1 을보장할수있다.
• 연결 리스트로 구현할 때는 머리(head)를 가리키는 하나의 개의 포인터만 가진다.
• 머리(head): 남아있는 원소 중 가장 마지막에 들어 온 데이터를 가리키는 포인터
• 삽입할 때는 머리(head) 위치에 데이터를 넣는다.
• 삭제할 때는 머리(head) 위치에서 데이터를 꺼낸다.
• 삽입할 때는 머리(head) 위치에 데이터를 넣는다.
• 값으로 8을 갖는 새로운 데이터가 삽입되었을 때
삽입할 때는 머리(head) 위치에 데이터를 넣는다.
• 값으로 8을 갖는 새로운 데이터가 삽입되었을 때
삽입할 때는 머리(head) 위치에 데이터를 넣는다.
• 값으로 8을 갖는 새로운 데이터가 삽입되었을 때
• 삭제할 때는 머리(head) 위치에서 데이터를 꺼낸다.
• 하나의 데이터를 삭제할 때의
• 삭제할 때는 머리(head) 위치에서 데이터를 꺼낸다.
• 하나의 데이터를 삭제할 때의
