KyungRyeol Yoon KyungRyeol Yoon
CS · Algorithms & Data Structures ·

[Data Structures | C++] Stack : 스택

· 3분 읽기

스택(Stack) #

  • 스택은 마지막에 저장한 데이터를 가장 먼저 꺼내는 후입선출(LIFO:Last In First Out) 구조로 되어 있다.
  • 입출력이 모두 한 방향에서 이루어지는 데이터 구조이다.
  • 입출력이 가능한 쪽을 TOP, 바닥을 BOTTOM이라고 한다.
  • TOP은 출력 우선순위가 가장 높은 요소를 가리키고 있다.
  • 입출력을 할 위치를 표시하기 위해서 TOP(포인터 사용)이 필요하다.
  • TOP을 통해서 데이터를 넣는 것을 PUSH라고 하고, 꺼내는 것을 POP이라고 한다.
  • 스택을 구현하는 방법은 배열과 연결 리스트가 있다.
  • 배열의 큰 단점은 처음 생성한 크기를 바꿀 수 없다는 점이다. 그래서 순차적으로 데이터를 추가하고 삭제하는 스택은 배열리스트(Array List)와 같은 배열기반의 컬렉션 클래스가 적합하다.
  • overflow : 스택의 모든 기억장소가 꽉 채워져 있어서 더 이상 데이터를 삽입(PUSH할 때)할 수 없다.
  • underflow : 자료가 없다면(TOP포인터가 주소 0을 가지고 있다면) 스택에는 삭제(POP할 때)할 자료가 없다.

스택(Stack)의 연산 #

스택(Stack)는 LIFO(Last In First Out) 를 따른다. 즉, 가장 최근에 스택에 추가한 항목이 가장 먼저 제거될 항목이다.

  • pop() : 스택에서 가장 위에 있는 항목을 제거한다.
  • push(item) : item 하나를 스택의 가장 윗 부분에 추가한다.
  • peek() : 스택의 가장 위에 있는 항목을 반환한다.
  • isEmpty() : 스택이 비어 있을 때에 true를 반환한다.

스택의 단점 #

  • 먼저 들어온 것이 나중에 출력되는 후입선출의 구조로 우선순위에 관련된 문제가 생길 수 있다.
  • 새로운 입력이 들어오면 바닥에 있는 데이터가 오랫동안 잔류하게 되는 경우가 생긴다.

스택의 용도 #

재귀 알고리즘을 사용하는 경우 스택이 유용하다.

  • 재귀 알고리즘
    • 재귀적으로 함수를 호출해야 하는 경우에 임시 데이터를 스택에 넣어준다.
    • 재귀함수를 빠져 나와 퇴각 검색(backtrack)을 할 때는 스택에 넣어 두었던 임시 데이터를 빼 줘야 한다.
    • 스택은 이런 일련의 행위를 직관적으로 가능하게 해 준다.
    • 또한 스택은 재귀 알고리즘을 반복적 형태(iterative)를 통해서 구현할 수 있게 해준다.
  • 웹 브라우저 방문기록 (뒤로가기)
  • 실행 취소 (undo)
  • 역순 문자열 만들기
  • 수식의 괄호 검사 (연산자 우선순위 표현을 위한 괄호 검사)
    • Ex) 올바른 괄호 문자열(VPS, Valid Parenthesis String) 판단하기
  • 후위 표기법 계산
  • 지역변수 저장
  • 함수의 콜스택
  • 문자열을 역순으로 출력할 때, 연산자 후위표기법 등
  • 임시데이터 백업
  • 함수 호출의 순서 제어
  • 인터럽트 처리
  • 수식계산

C++로 구현한 스택 (Stack) #

 1class Stack
 2{
 3private:
 4	DoubleList *doublelist;
 5public:
 6	Stack();
 7	~Stack();
 8
 9	DoubleList *getdouble() { return doublelist; }
10
11	void Push(int data, int position);
12	void Pop(int position);
13	void display();
14};
15
16#include "Stack.h"
17
18Stack::Stack()
19{
20	doublelist = new DoubleList;
21}
22
23Stack::~Stack()
24{
25}
26
27void Stack::Push(int data, int position) {
28	doublelist->insertNode(data, position);
29}
30
31void Stack::Pop(int position) {
32	doublelist->delNode(position);
33}
34
35void Stack::display() {
36	doublelist->displayNode();
37}
38
39//Manager.cpp
40void Manager::StackRun() {
41	int menu = 0;
42	int _data = 0;
43
44	while (true)
45	{
46		cout << "1.삽입\n2.반환\n3.출력\n입력 : ";
47		cin >> menu;
48
49		switch (menu)
50		{
51		case INSERT:
52			cout << "추가 할 데이터 : ";
53			cin >> _data;
54			stack->Push(_data, 0);
55			stack->display();
56			break;
57		case DEL:
58			stack->Pop(0);
59			stack->display();
60			break;
61		case COUT:
62			if (stack->getdouble()->getHead() == NULL) {
63				cout << "데이터가 없습니다." << endl << endl;
64			}
65			else {
66				stack->display();
67			}
68			break;
69		default:
70			break;
71		}
72	}
73}
Advertisement
관련 글