스택 자료구조

삽입/삭제가 제한된 자료구조

• 자료 성질에 따라, 삽입, 삭제하는 방법이 다름
• 프로그램에 내장된 자료구조가 아님

• 자료를 차곡차곡 쌓아 올린 형태 순서리스트의 특별한 자료구조
• 후입선출(LIFO : Last in First out) 프로토콜을 구현하는 자료구조
• 스택의 주소를 알여주는 포인터(top 위치에서만 원소를 삽입하므로 먼저 삽입한 원소는 밑에 쌓임
• 스택에 저장된 원소는 top로 정한 곳에서만 접근 가능
• 스택의 밑에서부터 스택의 크기까지의 범위를 가짐

 

스택의 ADT

ADT Stack
데이터
0개 이상의 원소를 가진 유한 순서리스트
연산자 및 연산내용 //s∈Stack, e∈Element
Stack createStack() //공백 스택을 생성
Stack push(s, e) //스택의 top에 원소 e를 삽입
Boolean isEmpty(s) //스택이 공백이면 true, 그렇지 않으면 false를 반환
Element pop(s) //스택이 공백이면 underflow,
//그렇지 않으면 스택의 top 원소 e를 삭제
Element peek(s) //스택이 공백이면 underflow,
//그렇지 않으면 스택의 top 원소 e를 반환
End Stack

 

스택의 삽입

- 스택 S = (a0, a1... an-1)  a0 : bottom원소, an-1 : top원소, ai : 스택 원소

- 삽입은 리스트의 마지막에서 이루어짐 - push()

push(s, e){
	if (top == SiZE) stack-overflow;
	top=top+1; ①
	stack[top]=e; ②
}

 

스택의 삭제

삭제도 리스트의 마지막에서 이루어짐 - pop()

pop(s) {
	if (top == 0) stack-underflow;
	e=stack[top];①
	top=top-1;②
	return e;
}

스택의 순차 표현

1차원 배열을 이용한 스택 구현

- 스택을 표현하는 가장 간단한 방법

• n = 스택에 저장할 수 있는 최대 원소 수
• top = 스택의 최상위 원소
• 공백 상태 => top = -1(초기값), 포화상태 => top = n-1

- 스택도 배열에 의해 저장되므로 배열의 속성을 가짐

• 동일한 자료형만 저장
• 배열의 크기에 의해 원소 개수의 제한을 받음

- 크기가 5인 1차원 배열의 스택에서 연산 수행

스택의 1차원 배열 표현의 장,단점

• 장점 - 순차 자료구조인 1차원 배열을 사용해 쉽게 구현 가능
• 단점 - 물리적 크기가 고정된 배열을 사용하므로 스택 크기 변경이 어려움

 

스택 연산 구현

스택의 삽입/삭제

1차원 배열 크기 stack[8]에서 오버플로와 언더플로를 검사하는 프로그램

#include <stdio.h>
int MAXSIZE = 8;
int stack[8];
int top = -1;
int isempty(){
	if(top == -1 )
		return 1;
	else
		return 0;
}
int isfull() {
	if(top == MAXSIZE)
		return 1;
	else
		return 0;
}

1차원 배열의 크기 (stack[8])에 원소를 삽입/삭제하는 프로그램

int peek(){
	return stack[top]; }
int push(int data){
	if(!isfull()){
		top = top + 1;
		stack[top] = data;
} else{
		printf("Could not insert data, Stack is full.\n"); }
}
int pop(){
	int data;
	if(!isempty()){
		data = stack[top];
		top = top- 1;
		return data;
	} else{
		printf("Could not retrieve data, Stack is empty.\n"); }
}

int main(){ // push items on to the stack
	push(3 );
	push(5 );
	push(9);
	push(1 );
	push(12 );
	push(15 );
	printf("Element at top of the stack: %d	\n" ,peek());
	printf("Elements:	\n");
	// print stack data
	while(!isempty()){
		int data = pop();
		printf("%d\n", data);
	}
	printf("Stack full: %s\n" , isfull()?"true":"false");
	printf("Stack empty: %s\n" , isempty()?"true":"false");
	return 0;
}

 

반응형

 

result
Element at top of the stack: 15
Elements:
15
12
1
9
5
3
Stack full: false
Stack empty: true

 

스택 응용 : 시스템 스택

시스템 스택(system stack) / 실행시간 스택(runtime stack)

- 기억공간의 데이터들을 효율적으로 관리하기 위한 데이터 참조 방식의 자료구조

• 프로그램 실행 시 시스템이 사용하는 대표적인 스택(기억공간)
• 실행 스택(execution stack), 제어 스택 (control stack), 런타임 스택(run-time)스택, 기계 스택(machine stack)이라고도 함

- 함수간의 호출과 복귀에 따른 실행순서관리를 위한 제어

• 함수 호출 시 시스템은 호출한 함수 수행에 필요한 지역변수, 매개변수 및 수행 후 복귀할 주소 등의 정보를 활성화 레코드(activation record) 또는 스택 프레임 (stack frame)을 만들어 스택에 삽입

 

프로그램에서의 호출과 복귀에 따른 수행 순서 과정

 

스택의 응용 : 문자열 역순/괄호검사

 

 

문자열 역순 출력 방법 및 예

1. 문자열을 읽어 문자열 끝까지 차례대로 스택에 삽입(push)
2. 스택이 비워질(empty)때까지 문자들을 삭제(pop)

문자열 역순 출력 방법 및 예

#include <stdio.h>
#include <string.h>
#define MAX 100 //최대 문자열의 길이
int top=-1; // 스택 변수
int item;
char stack_string[MAX];
void pushChar(char item);
char popChar(void);
int isEmpty(void);
int isFull(void);

문자열 computer science를 역순으로 출력하는 프로그램

int main(){
	char str[MAX];
	int i;
	printf("Input a string: ");
	scanf("%[^\n]s", str); // 문자열 입력
	for(i=0; i<strlen(str); i++)
		pushChar(str[i]);
	for(i=0; i<strlen(str); i++)
		str[i]=popChar();
	printf("Reversed String is: %s\n", str);
	return 0;
}

void pushChar(char item){
	if(isFull()){
		printf("\nStack is FULL !!!\n");
	return;
}
	top=top+1;
	stack_string[top]=item;
}
char popChar(){
	if(isEmpty()){
	printf("\nStack is EMPTY!!!\n");
	return 0;
	}
	item = stack_string[top];
	top=top-1;
	return item;
}

int isEmpty(){
	if(top==-1 )
		return 1;
	else
	return 0;
}
int isFull(){
	if(top==MAX-1 )
		return 1;
	else
		return 0;
}

result
Input a string: computer science
Reversed String is: ecneics retupmoc

 

괄호 검사

• 괄호((, ), {, }, [, ])가 서로 대응하며 적절하게 내포되었는지 파악하는 검사를 말함 – 컴파일러에서 구문 체크 시 활용
• 수식에 포함되어있는 괄호는 가장 마지막에 열린 괄호를 가장 먼저 닫아 주어야 하는 LIFO 구조로 구성되어있음

괄호 검사 방법

1. 입력 문자열(수식)에서 현재의 문자가 시작 괄호('(' , '{' , '[') 이면 스택에 삽입함(push)
2. 현재의 문자가 닫는 괄호(‘)', ‘}' , ‘]') 이면 스택에서 삭제(pop)
3. 입력 문자열의 마지막 문자까지 읽었을 때 스택에 시작 괄호가 남아 있으면 균형을 이루지 못함, 즉 괄호가 닫히지 않음

{ ( a + b ) / [ { ( c - d ) / 2 } × e ] } 의 괄호를 검사하는 프로그램

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 20
struct stack{
	char stk[MAX];
	int top;
}s;

void push(char item){
	if (s.top == (MAX- 1 ))
		printf ("Stack is Full\n");
else{
	s.top = s.top + 1; // 포인터를 1 증가후 괄호를 삽입
	s.stk[s.top] = item;
	}
}

void pop(){
	if (s.top == - 1 ){
		printf ("Stack is Empty\n");
	}
	else{
		s.top = s.top - 1; // 괄호를 삭제 후 포인터 감소
	}
}
int main(){
	char exp[MAX];
	int i = 0;
	s.top = -1;
	printf("\n입력 식 : ");
	scanf("%s", exp);

for(i = 0;i < strlen(exp);i++){
	if(exp[i] == '(' || exp[i] == '[' || exp[i] == '{'){
		push(exp[i]); // 시작 괄호를 스택에 삽입
		continue;
	}
	else if(exp[i] == ')' || exp[i] == ']' || exp[i] == '}'){
		if(exp[i] == ')'){//닫는 괄호이면 스택에서 삭제
			if(s.stk[s.top] == '('){
				pop();
			}
			else{
            printf("\n괄호의 균형을 이루지 못한 수식\n");
			break;
		}
		}
        if(exp[i] == ']'){
			if(s.stk[s.top] == '['){
				pop();
			}
			else{
				printf("\nUNBALANCED EXPRESSION\n");
				break;
			}
		}
		if(exp[i] == '}'){
			if(s.stk[s.top] == '{'){
				pop();
			}
			else{
				printf("\nUNBALANCED EXPRESSION\n");
				break;
			}
		}
	}
}

	if(s.top == -1 ){ //stack이 empty이면 balanced함
		printf("\n입력식의 괄호 개수가 BALANCED이다.\n");
	}
}

result
입력 식 : {(a+b)/[{(c-d)/2}*2]}
입력식의 괄호 개수가 BALANCED이다

 

학습정리

• 스택은 후입선출(LIFO: Last-In-First-Out) 프로토콜을 구현하는 자료구조로 스택의 삽입/삭제 위치를 알려주는 포인터(top)가 있어야 하며, 삽입 시에는 포인터를 먼저 증가(top=top+1 )한 후 삽입이 이루어진다. 반면에 삭제는 원소값을 삭제한 후 포인터를 감소(top=top-1 )한다
• 시스템 스택은 기억공간의 데이터들을 효율적으로 관리하기 위한 데이터 참조 방식의 자료구조이며 프로그램 실행 시 시스템이 사용하는 대표적인 기억공간으로서 함수간의 호출과 복귀에 따른 실행순서관리를 제어하기 위해 사용된다.