스택(Stack)



스택(Stack)?

스택은 LIFO(Last In First Out)구조로 


가장 나중에 들어간 값이 가장먼저 나오는 구조입니다.


삽입하는 PUSH와 삭제하는 POP 동작이 있습니다.


1. 스택 형태


2. PUSH


3. POP




배열을 이용한 예제


스택으로 사용할 int형 배열 선언 및 초기화 함수


#include "stdio.h"
#define MAX 10


int stack[MAX];
int top;


void init_stack(void){
top = -1;
}


스택에 push하는 함수


스택 크기보다 크면 오버플로우 발생


int push(int t){
if(top >=MAX-1){
printf("########### STACK OVER FLOW ###########\n");
return -1;
}else{
stack[++top] = t;
return t;
}
}


스택에서 pop하는 함수


스택 크기보다 작으면 오버플로우 발생


int pop(void){
if(top<0){
printf("########### STACK UNDER FLOW ###########\n");
return -1;
}
return stack[top--];
}

스택의 값을 출력하는 함수


void print_stack(void){
printf("PRINT STACK \n");
for(int i=top; i>=0; i--){
printf("%-6d",stack[i]);
}
printf("\n");
}

메인함수

11개의 값을 push할 경우 10개는 정상적으로 push 되지만,
나머지 1개의 값은 스택 오버플로우가 발생합니다.

두번째 pop을 수행할 때 5개의 값은 정상적으로 pop 되지만,
나머지 1개의 값은 스택 언더플로우가 발생합니다.

void main(){
init_stack();
printf("########### PUSH ###########\n");
for(int i=0; i<11; i++){
push(i);
}
print_stack();
printf("########### POP ###########\n");
for(int i=0; i<5; i++){
pop();
}
print_stack();
for(int i=0; i<6; i++){
pop();
}
}

실행 결과


참고 : C로 배우는 알고리즘 (이재규)






'언어 > Data Strcuture' 카테고리의 다른 글

[C] 삽입 정렬(Insertion Sort)  (0) 2019.04.19
[C] 선택 정렬(Selection Sort)  (0) 2019.04.19
[C] 트리(Tree)  (0) 2019.04.07
[C] 큐(Queue)  (2) 2019.04.01
[C] 연결리스트(LinkedList)  (0) 2019.03.28

리스트와 리스트 메소드



- 리스트

 앞에서 공부하면서 사용했던 리스트에 대해 알아보겠습니다. 리스트는 문자형처럼 시퀀스 자료형이지만 문자열과는 다르게 변경이 가능한 자료형입니다. 인덱싱, 슬라이싱, 연결, 반복, 멤버십 테스트 연산이 가능합니다.

 다음은 리스트의 추가, 삭제 예시입니다.

----------------------------------------------------------------------------------------

l1=range(10) # 0부터 9까지의 리스트 생성
print l1

del l1[2] # 2번째 인덱스 삭제
print l1

Sun,Mon,Tue,Wed,Thu,Fri,Sat=range(7) # 여러 변수에 한번에 리스트 생성 가능
print Sun,Mon,Tue,Wed,Thu,Fri,Sat
----------------------------------------------------------------------------------------
(실행 결과)
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[0, 1, 3, 4, 5, 6, 7, 8, 9]
0 1 2 3 4 5 6
----------------------------------------------------------------------------------------

- 중첩 리스트
 중첩 리스트는 리스트를 인자로 가지는 리스트를 말합니다. 다음과 같이 사용합니다.
----------------------------------------------------------------------------------------
s=[2,3,4]
t=[1,s,5] # 리스트 s를 인자로 사용
print t
print t[1][1] # t리스트의 1번째 인덱스의 1번째 인덱스
----------------------------------------------------------------------------------------
(실행 결과)
[1, [2, 3, 4], 5]
3
----------------------------------------------------------------------------------------

- 리스트가 지원하는 메소드

 리스트가 지원하는 메소드는 아래와 같습니다. java와 메소드 이름이 비슷한 것 같습니다. 

1. append() : 리스트 마지막에 원소를 추가
문자열, 튜플, 사전도 추가가능
2. insert(위치,값) : 해당하는 인덱스의 위치에 원하는 값 추가
3. index(위치) : 해당하는 원소의 인덱스가 몇인지 반환
4. count(값) : 해당하는 값이 몇개가 존재하는지 반환
5. reverse() : 리스트의 순서를 뒤바꿔 줌(값 변경)
6. sort() : 리스트의 값을 정렬해서 값을 변경
7. remove(값) : 해당하는 값을 삭제하는데, 값이 여러개일 경우 첫 번째 값 삭제
8. extend(값) : 기존의 리스트에 값 자체를 추가(병합)

----------------------------------------------------------------------------------------
# append()
ap=[1,2,3,4]
ap.append(10) # 가장 뒤에 10 추가
print ap
print '*'*50

# insert()
ins=[1,2,4,5]
ins.insert(2,3) # 2번째 자리에 3 추가
print ins
print '*'*50

# index()
ind=[1,2,3,4,5,6]
print ind.index(3) # 3에 해당하는 인덱스 값 
print '*'*50

# count()
co=[1,2,3,2,2,2,7]
print co.count(2) # 2가 몇개인지
print '*'*50

# reverse()
re=[1,2,3,4]
re.reverse() # 순서를 거꾸로
print re
print '*'*50

# sort()
so=[11,-3,4,-50]
so.sort() # 정렬
print so
print '*'*50

# remove()
rem=[11,-3,4,-50,-3]
rem.remove(-3) # -3을 제거
print rem
print '*'*50

# extend()
s=[1,2,3,4]
t=[5,6,7]
s.extend(t) # s리스트에 t리스트를 추가(병합)
print s
# extend()와 append() 비교
s2=s.append(t) # append는 리스트 자체를 추가
print s2

----------------------------------------------------------------------------------------
(실행 결과)
[1, 2, 3, 4, 10]
**************************************************
[1, 2, 3, 4, 5]
**************************************************
2
**************************************************
4
**************************************************
[4, 3, 2, 1]
**************************************************
[-50, -3, 4, 11]
**************************************************
[11, 4, -50, -3]
**************************************************
[1, 2, 3, 4, 5, 6, 7]
----------------------------------------------------------------------------------------

- 리스트를 스택, 큐로 이용

 스택은 후입선출 구조, 큐는 선입선출 구조를 가집니다. 리스트의 메소드를 이용해서 스택과 큐처럼 사용할 수 있습니다. append()메소드와 pop()메소드를 이용합니다. pop()메소드는 기본적으로 마지막 원소를 꺼내고, 인자안에 인덱스를 적어주면 해당하는 인덱스의 값을 꺼냅니다.
----------------------------------------------------------------------------------------
# stack
s=[10,20,30,40,50]
s.append(60)
print s
print s.pop()
print s
print s.pop()
print s
print '*'*50

# queue
q=[10,20,30,40,50]
q.append(60)
print q
print q.pop(0)
print q
print q.pop(0)
print q
----------------------------------------------------------------------------------------
(실행 결과)
[10, 20, 30, 40, 50, 60]
60 # 가장 마지막 원소인 60을 꺼냄
[10, 20, 30, 40, 50]
50 # 가장 마지막 원소인 50을 꺼냄
[10, 20, 30, 40]
**************************************************
[10, 20, 30, 40, 50, 60]
10 # 가장 앞의 원소인 10을 꺼냄
[20, 30, 40, 50, 60]
20 #가장 앞의 원소인 20을 꺼냄
[30, 40, 50, 60]
----------------------------------------------------------------------------------------

출처 한국기술교육대학교 온라인평생교육원 파이썬프로그래밍



+ Recent posts