자료구조

[자료구조 기초] Stack, 스택

aliceintr 2021. 4. 14. 11:08
반응형

 

이번에는 자료구조 중에서 스택에 대해 알아보자 한다.

스택은 쌓아 올린 더미를 표현한 것이며

데이터의 삽입과 삭제가 위 쪽 즉, 한쪽면에서만 이루어진다.

stack을 사용하는 이유

출처 : 나무 위키

비전공자가 가장 와 닿는 영역은 undo. 그러니까 Ctrl + Z 그것. 가장 최근에 실행한 명령어를 취소해야 하기 때문에 마지막에 들어간 자료가 먼저 나오는 스택 구조가 효율적이다.

대부분의 현대 CPU는 어셈블리어에 스택 영역을 제어하는 명령이 있다. 한 프로그램이 사용하는 스택 영역은 기본적으로 크기가 고정되어 있다. 실행되거나 기다리고 있는 여러 함수 등 각 분기점에서, 함수에서 사용되는 변수와 같은 정보를 이러한 명령어를 통해 추가하고 삭제한다. 이를 이해하지 못하고 스택 영역 변수나 메모리를 함부로 사용하면 잘못된 데이터가 씌워져 이상한 값을 출력하거나 문제를 일으킬 수 있다.

이를 좀 더 쉽게 설명해보자. 어떤 함수든 호출되는 순간 스택에 그 함수를 위한 영역(스택 프레임 stack frame)이 할당되는데, 어떤 함수 foo()가 호출된 상태에서 foo()가 다시 다른 함수 bar()를 호출하는 상황을 생각해 보자. 우선 스택 내부 foo()에 해당되는 프레임에 데이터가 쌓여 있을 것이다. bar()가 호출되면 우선 bar가 받는 인수들이 푸시되고, 그다음 bar의 리턴 값을 받을 공간이 푸시된다. 그 위로 bar에 해당하는 새로운 스택 프레임이 할당되고, 그 프레임 내부에 bar의 내부 변수들이 푸시 된다. 즉, 함수 호출에서 복귀 주소를 기억하는 데 사용

그런 뒤 bar에 해당하는 연산이 종료되고 bar의 스택 프레임 내부의 값들이 하나씩 빠져나오면서 끝으로 출력 데이터가 리턴 값을 받기 위한 공간으로 들어오게 된다. 다시 말해 함수가 호출될 때마다 스택에 값들이 쌓이고, 계산이 끝나면 다시 하나씩 빼면서 출력 값이 가장 밑에 있던 리턴 공간으로 돌아오는 것이다. 이 개념을 잘 이해하면 재귀가 연산속도에서 불리한 점이 발생함을 알 수 있다. 재귀도 일반 함수 호출과 다를 것 없이 한번 재귀 호출이 이루어질 때마다 계속 스택을 쌓아나가므로 최종 결괏값을 되돌려 받으려면 쌓인 스택을 전부 다시 빼내야 하기 때문이다. 따라서 재귀 알고리즘을 사용할 때는 반드시 재귀 알고리즘이 필요한지 설계를 먼저 정확히 하는 것이 중요하다.

굳이 리스트나 배열이 있는데 한쪽이 막힌 스택을 사용하는 이유는 abstract 자료구조의 특징 때문이며, 인터페이스로 실제 코드를 숨기며 에러 발생률을 낮출 수 있다.

프로그램 코딩 과정에서 {} 이 제대로 닫혀있는지 확인할 때도 스택을 많이 사용한다

미로 찾기 프로그램에서도 사용

stack의 원리

Last In First Out LIFO 리스트라고 할 수 있다. = First In Last Out 이와 반대되는 개념이 큐(Queue)이다.

아래의 그림과 같이 마지막으로 삽입된 원소가 가장 먼저 나온다. 접시를 쌓는 것을 생각하면 될 것 같다.

 

https://images.app.goo.gl/aei6cALjvUhK2WN86

stack over flow 란

프로그램 호출 stack에서 이용 가능한 공간 이상을 사용하려고 할 때 스택 오버플로우가 발생. 이 경우 프로그램 동작이 중단됨

stack의 삽입

push(value) - Array

void push(stackType* Sptr, int Item)
{     
	if (isFull(Sptr)) 
		printf("Stack is already Full !!!\n");
    else {
		//data[Top+1]에 데이터 삽입, Top을 1증가
        Sptr->data[Sptr->Top+1] = Item;
        Sptr->Top = Sptr->Top + 1;
	}
}

push(value) - Linked List

새로운 노드를 임시 포인터 temp 가 가리키게 하고 데이터를 저장

삽입할 노드의 링크가 Top 이 원래 가리키던 노드를 가리키도록 함

Top 은 새로운 노드를 가리킴

 

stack의 삭제

pop() - Array

int pop(stackType* Sptr)
{   
	int temp;
    if (isEmpty(Sptr)){
		printf("Stack is empty!!!.\n");
        return -1;
     } else {
        //data[Top]의 값을 반환, Top을 1감소
        temp = Sptr->data[Sptr->Top];
        Sptr->Top = Sptr->Top - 1;
        return temp;
    }
}

pop()- Linked List

임시 포인터 temp 가 Top이 가리키는 노드를 가리킴

Top은 그다음 노드를 가리킴

Temp 가 가리키는 노드의 메모리를 해제하고, 노드의 값을 호출한 프로그램에 반환

stack을 이용한 정렬

스택을 사용해서 리스트의 순서를 역순으로 만드는 것이 가능하다.

**NOTE : 컴퓨터는 뺄셈의 개념이 없고 단순 반복을 제일 잘한다

stack 추상 자료형

  • 0개 이상의 원소를 가진 유한 순서 리스트
  • 선형 리스트 또는 연결 리스트 사용
  • 리스트의 TOP을 가리키는 포인터가 있음

stack의 기본 연산

operation desc
init stack 초기화
push stack에 새로운 data를 삽입
pop stack에 있는 원소를 없애고 없앤값을 반환
peek(or get) Top에 잇는 데이터를 반환함
getSize 현재 stack 에 있는 element 갯수를 반환
isEmpty 스택이 비어있는지 확인
isFull 스택이 꽉찾는지 확인 (스택사이즈이상을 넘어가면 stackoverflow 발생)

Array를 이용한 stack 표현

크기가 고정된 1차원 배열을 이용하여 스택을 표현하고

가장 마지막 인덱스를 지칭하는 Top 변수가 필요하다

operation desc                                                                                                                **Top : 현재위치를 나타냄
init temp[MaxStackSize] 와 Top을 갖는 구조체 변수 선언
Top = -1의 의미는 stack 이 비워있음을 의미
push temp[Top+1] 에 데이터를 삽입, Top을 1 증가
pop temp[Top] 값을 반환,  Top을 1감소
peek(or get) Top에 잇는 데이터를 반환함
getSize Top+1을 리턴
isEmpty Top < 0 일 경우 비어있디고 판한
isFull 스택이 꽉찾는지 확인 (스택사이즈이상을 넘어가면 stackoverflow 발생)
Top >= MaxStackSize -1 일 경우 stack 이 꽉찬것임

Top을 표시하는 변수가 원소를 저장하는 배열 변수를 묶어서 stackType 구조체로 선언함

stack_array.h

#define MaxStackSize 10       //스택의 최대 크기

typedef struct {
     int Top;           	  //스택의 탑을 표시하는 변수
     int data[MaxStackSize];  //스택의 원소를 저장하는 배열
} stackType;

void init(stackType* Sptr)
{      
  // 탑 인덱스를 -1으로 빈스택을 표시
  Sptr->Top = -1;        
}

int isEmpty(stackType* Sptr)
{     
  // Top < 0 일 경우 비어있다고 판단
  return (Sptr->Top < 0);
}

int  isFull(stackType* Sptr)
{     
   // Top >= MaxStackSize-1 일 경우 꽉 차 있다고 판단
   return (Sptr->Top >= MaxStackSize-1);
}

int getSize(stackType* Sptr)
{
	return (Sptr->Top+1);
}

void push(stackType* Sptr, int Item)
{     
	if (isFull(Sptr)) 
		printf("더이상 넣을 수 없습니다.!!!\n");
    else {
		//data[Top+1]에 데이터 삽입, Top을 1증가
        Sptr->data[Sptr->Top+1] = Item;
        Sptr->Top = Sptr->Top + 1;
	}
}

int pop(stackType* Sptr)
{   
	int temp;
    if (isEmpty(Sptr)){
		printf("스택이 비어있습니다.\n");
        return -1;
     } else {
        //data[Top]의 값을 반환, Top을 1감소
        temp = Sptr->data[Sptr->Top];
        Sptr->Top = Sptr->Top - 1;
        return temp;
    }
}

int peek(stackType* Sptr)
{   
	int temp;
    if (isEmpty(Sptr)){
		printf("스택이 비어있습니다.\n");
        return -1;
     } else {
        //data[Top]의 값을 반환, Top을 1감소
        temp = Sptr->data[Sptr->Top];
        return temp;
    }
}

/*void printStack(stackType* Sptr)
{
	if (isEmpty(Sptr))
		printf("스택이 비어있습니다.\n");
	else {
		printf("스택의 총 원소 수는 %d입니다.\n", getSize(Sptr));
		
		for (int i = 0; i <= Sptr->Top; i++)
			printf("스택의 %d번째 원소는 %d입니다.\n", i + 1, Sptr->data[i]);
	}
}*/

void stackPrint(stackType* Sptr)
{
	if(!isEmpty(Sptr)){
		printf("Here is the stack information -----------------\n");
		printf("-----------------------------------------------\n");
		
		for (int i=0; i<= Sptr->Top; i++){
		    printf("stack : index %d\n",i+1);
			printf("-----\n");
			printf("| %d | \n",Sptr->data[i]);
			printf("-----\n");
		}
	}else{
		printf("This stack is empty , please check \n");
	}
}

stack_array.c

#include <stdio.h>
#include "stack_array.h"

void main()
{
	stackType st1;	// 스택 생성
    init(&st1);    	// 스택 초기화

	// 스택에 원소 넣기
    push(&st1, 1); 	push(&st1, 2); 	push(&st1, 3); 
	push(&st1, 4); 	push(&st1, 5);  push(&st1, 6); 
	push(&st1, 7); 	push(&st1, 8); 	push(&st1, 9); 
	push(&st1, 10);	
	push(&st1, 11);	    // Stack is already Full.!!!
    //printStack(&st1); // 스택 내용 전체 출력
	stackPrint(&st1);
	/*
	Here is the stack information -----------------
	-----------------------------------------------
	stack : index 1
	-----
	| 1 |
	-----
	stack : index 2
	-----
	| 2 |
	-----
	stack : index 3
	-----
	| 3 |
	-----
	stack : index 4
	-----
	| 4 |
	-----
	stack : index 5
	-----
	| 5 |
	-----
	stack : index 6
	-----
	| 6 |
	-----
	stack : index 7
	-----
	| 7 |
	-----
	stack : index 8
	-----
	| 8 |
	-----
	stack : index 9
	-----
	| 9 |
	-----
	stack : index 10
	-----
	| 10 |
	-----
	*/

	// 스택 원소 꺼내기
	printf("스택에서 %d을 꺼냈습니다.\n", pop(&st1));	
    printf("스택에서 %d을 꺼냈습니다.\n", pop(&st1));
    printf("스택에서 %d을 꺼냈습니다.\n", pop(&st1));
    printf("스택에서 %d을 꺼냈습니다.\n", pop(&st1));
	stackPrint(&st1);	
	/*
	스택에서 10을 꺼냈습니다.
	스택에서 9을 꺼냈습니다.
	스택에서 8을 꺼냈습니다.
	스택에서 7을 꺼냈습니다.
	Here is the stack information -----------------
	-----------------------------------------------
	stack : index 1
	-----
	| 1 |
	-----
	stack : index 2
	-----
	| 2 |
	-----
	stack : index 3
	-----
	| 3 |
	-----
	stack : index 4
	-----
	| 4 |
	-----
	stack : index 5
	-----
	| 5 |
	-----
	stack : index 6
	-----
	| 6 |
	-----
	*/
	
}

 

Linked List를 이용한 stack 표현

동적으로 생선 된 노드를 연결하는 형태로 스택을 구현

항상 첫 번째 노드가 top이 되도록 함

배열처럼 별도로 top 인덱스를 저장할 필요가 없으므로, 스택 타입을 구조체로 선언하지 않고 노드만 구조체로 선언한다.

https://images.app.goo.gl/eh6w3NVmjoWDYZZf6

operation desc                                                                                                               
init stack node를 가리키는 변수 Top 의 선언 및 NULL 로 초기화
push stack top pointer가 가리키는 위치에 노드 삽입후 top pointer 를 새 노드로 향하게 이동
pop stack top pointer가 가리키는 위치에 있는 노드 삭제 후 top pointer 를 삭제한 다음 노드로 향하게 이동
peek(or get) Top -> data 값을 반환
getSize Top 부터 노드들을 따라가며 노드 갯수를 반환, 배열에 비하면 시간이 오래걸림
isEmpty Top 이 Null 일 경우 True
isFull 개수의 제약은 없음 (동적할당도가능) 프로그램을 짜는 사람에 따라 MAX 사이즈 제한 가능

 

stack_linkedlist.h

#define MaxStackSize 100

typedef struct node{
	char data;
	struct node* next;
}nodeType;

//Top을 가리키는 포인터 선언
nodeType* Stack_top;

void init(){
	Stack_top = NULL;
}

int isEmpty(){
	if (Stack_top == NULL)
		return 1;
	else
		return 0;
}

int getSize(){
	nodeType *p;
	int count = 0;

	for (p=Stack_top; p!=NULL; p=p->next){
		count++;
	}

	return count;
}

int isFull(){
	return (getSize() == MaxStackSize);
}

void push(char item){
	nodeType *p = (nodeType*)malloc(sizeof(nodeType));
	p->data = item;

	p->next = Stack_top;
	Stack_top = p;
}

char pop(){
	nodeType *p;
	char item;

	if (isEmpty()){
		printf("Stack is Empth, can't pop from NODE\n");
		exit(1);
	}else{
		p = Stack_top;
		Stack_top = Stack_top->next;
		item = p->data;
		free(p);
		return (item);
	}
}


void printStack(){
	nodeType *p;
	printf("The size of Stack is %d.\n", getSize());
	for (p=Stack_top; p!=NULL; p=p->next )
		printf("%c\n",p->data);
		printf("====\n");
}

 

stack_linkedlist.c

#include <stdio.h>
#include <stdlib.h>
#include "stack_linkedlist.h"

void main(void)
{
	init();
	
	// 스택에 원소 넣기
	push('A');
	push('B');
	push('C');
	push('D');
	printStack();	
	/*
	The size of Stack is 4.
	D
	C
	B
	A
	====
	*/
	// 스택 원소 꺼내기
	printf("스택에서 %c를 꺼냈습니다.\n", pop());
	printf("스택에서 %c를 꺼냈습니다.\n", pop());
	printStack();	
	/*
	스택에서 D를 꺼냈습니다.
	스택에서 C를 꺼냈습니다.
	The size of Stack is 2.
	B
	A
	====
	*/

	// 스택에 원소 넣기
	push('Q');
	push('R');
	printStack();	
	/*
	The size of Stack is 4.
	R
	Q
	B
	A
	====
	*/
	// 스택 원소 꺼내기
	printf("스택에서 %c를 꺼냈습니다.\n", pop());
	printf("스택에서 %c를 꺼냈습니다.\n", pop());
	printf("스택에서 %c를 꺼냈습니다.\n", pop());
	printf("스택에서 %c를 꺼냈습니다.\n", pop());
	printf("스택에서 %c를 꺼냈습니다.\n", pop());
	/*
	스택에서 R를 꺼냈습니다.
	스택에서 Q를 꺼냈습니다.
	스택에서 B를 꺼냈습니다.
	스택에서 A를 꺼냈습니다.
	Stack is Empth, can't pop from NODE
	*/
}
반응형
저작자표시 비영리 변경금지

'자료구조' 카테고리의 다른 글

[자료구조 기초] 원형 연결리스트, Queue, 이중원형 연결리스트  (0) 2021.04.16
[자료구조 기초] queue , 큐  (0) 2021.04.14
[자료구조 기초] 리스트, 선형 리스트, 단순 연결리스트, Linear List, Linked List  (0) 2021.04.13
[자료구조 기초] structure, 구조체  (0) 2021.04.13
[ 자료구초 기초] Array, 배열  (0) 2021.04.13

'자료구조'의 다른글

  • 현재글[자료구조 기초] Stack, 스택

관련글

댓글

티스토리툴바