개요

top에서 후입선출(LIFO)로 삽입/삭제가 이루어지는 ADT

메소드

• push(e) : 삽입
• element pop() : 가장 최근에 삽입된 원소 삭제 후 반환
• element top() : 가장 최근에 삽입된 원소 반환
• integer size() : 저장된 원소 개수 반환
• boolean isEmpty()
• iterator elements() : 스택원소 전체 반환

예외

• emptyStackException() : 빈 스택에 pop, top시도
• fullStackException() : 가득 찬 스택에 push 시도

스택 구현

배열 기반 구현

• 구성요소

  • 크기 N의 배열 S
  • top원소의 첨자 t

• 의사코드

Alg init()
  input stack S, size N, top t
  output empty stack S
1. t ← -1
2. return

Alg push(e)
  input stack S, size N, top t, element e
  output none
1. if(t = N-1)
     fullStackException()
2. t ← t + 1
3. S[t] ← e
4. return

Alg pop()
  input stack S, size N, top t
  output element e
1. if(t = -1)
     emptyStackException()
2. t ← t-1
3. return S[t+1]

• C언어 구현

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

typedef struct _Stack {
	int N;
	int t;
	int* Memory;
} Stack;

void push(Stack* S, int e) {
	if (S->t == S->N - 1) 
		return; // Full Exception
	S->t += 1;
	S->Memory[S->t] = e;
}

int pop(Stack* S) {
	if (S->t == -1)
		return NULL; // Empty Exception
	S->t -= 1;
	return S->Memory[S->t + 1];
}

void print(Stack* S) {
	for (int i = 0; i <= S->t; i++)
		printf("%d ", S->Memory[i]);
	printf("\n");
}

int main() {
	int N;
	scanf("%d", &N); // 배열크기

	// init
	Stack* S = (Stack*)malloc(sizeof(Stack));
	S->Memory = (int*)malloc(sizeof(int) * N);
	S->t = -1;

	// action
	push(S, 5);
	push(S, 3);
	print(S); // 5 3
	pop(S);
	print(S); // 5
}

연결리스트 기반 구현

• 의사코드

Alg init()
  input top t
  output empty stack
1. t ← NULL
2. return

Alg push()
  input top t, element e
  output none
1. p ← getNode()
2. p.elem ← e
3. p.next ← t
4. t ← p
5. return

Alg pop()
  input top t
  output element e
1. if(t = NULL)
     emptyStackException()
2. e ← t.elem
3. p ← t
4. t ← t.next
5. putNode(p)
6. return e

• C언어 구현

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

typedef struct _Node {
	struct _Node* next;
	int elem;
} Node;

Node* getNode() {
	Node* p = (Node*)malloc(sizeof(Node));
	p->next = NULL;
	return p;
}

void push(Node** S, int e) {
	Node* p = getNode();
	p->next = *S;
	p->elem = e;
	(*S) = p;
}

int pop(Node** S) {
	Node* q = *S;
	int e = q->elem;

	(*S) = (*S)->next;
	free(q);
	return e;
}

void print(Node* S) {
	Node* p = S;
	while (p != NULL) {
		printf("%d ", p->elem);
		p = p->next;
	}
	printf("\n");
}

int main() {
	// init
	Node* S = NULL;

	// action
	push(&S, 5);
	push(&S, 3);
	print(S); // 3 5
	pop(&S);
	print(S); // 5
}

괄호균형

괄호 짝이 맞는지 검사

구현

• 의사코드

Alg balance()
  input string str
1. S ← empty stack
2. while(true)
     ch ← getNextChar()
     if(ch == isOpenSymbol())
       S.push(ch)
     else
       if(S.isEmpty())
         return False
       e ← S.pop()
       if(!isPair(e, ch))
         return False
3. return S.isEmpty()

• C언어

 <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct _Node {
	struct _Node* next;
	char elem;
} Node;

Node* getNode() {
	Node* p = (Node*)malloc(sizeof(Node));
	p->next = NULL;
	return p;
}

void push(Node** S, char e) {
	Node* p = getNode();
	p->next = *S;
	p->elem = e;
	(*S) = p;
}

char pop(Node** S) {
	Node* q = *S;
	char e = q->elem;

	(*S) = (*S)->next;
	free(q);
	return e;
}

//----
int balance(char* str) {
	Node* S = NULL; // empty stack
	
	for (int i = 0; i < strlen(str); i++) {
		char ch = str[i];
		if (ch == '(' || ch == '[') {
			push(&S, ch);
		}
		else {
			if (S == NULL)
				return -1;

			char e = pop(&S);
			if ((ch==')' && e!='(') || (ch==']' && e!='['))
				return -1;
		}
	}

	return S == NULL ? 1 : -1;
}

int main() {
	// input
	char strCorrect[100] = "[()(([]))]";
	char strIncorrect[100] = "(((()[)])]";

	// action
	printf("%d", balance(strCorrect)); // 1
	printf("\n%d", balance(strIncorrect)); // -1
}

후위수식

개념

• 중위수식 : A * B + C
• 전위수식 : +*ABC
• 후위수식 : AB*C+

구현

• 의사코드

Alg convert()
  input infix expression string IE
  output postfix expression string

1. S ← empty stack
2. ch ← ''
3. while( IE.lastChar != ch )
     ch ← IE.getNextChar
     
     if(isOperand(ch))
       write(ch)
     else if(ch == '(')
       S.push(ch)
     else if(ch == ')')
       while(S.top() != '(')
         write(S.pop())
       S.pop()
     else
       while( !S.isEmpty() & getPriority(ch) ≤ getPriority(S.top()))
         write(S.pop())
       S.push(ch)
3. while( !S.isEmpty() )
     wrtie(S.pop())
4. return

Alg eval()
1. S ← empty Stack
2. ch ← ''
3. while( exp.lastChar != ch )
     ch ← exp.getNextChar
     
     if(isOperand(ch))
       S.push(ch)
     else
       n1 ← S.pop()
       n2 ← S.pop()
       S.push(calculate(n1, n2, s))
4. write(S.pop())
5. return

• C언어

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

typedef struct _Node {
	struct _Node* next;
	char elem;
} Node;

typedef struct _Stack {
	Node* head;
	int size;
} Stack;

Node* getNode() {
	Node* p = (Node*)malloc(sizeof(Node));
	p->next = NULL;
	return p;
}

void putNode(Node* p) {
	free(p);
}

void push(Stack* S, char elem) {
	Node* p = getNode();
	p->next = S->head;
	p->elem = elem;
	S->head = p;

	(S->size)++;
}

char pop(Stack* S) {
	if (S->head == NULL)
		return -1;
	else {
		Node* q = S->head;
		char n = q->elem;
		S->head = (S->head)->next;
		putNode(q);
		(S->size)--;
		return n;
	}
}

char top(Stack* S) {
	if (S->head == NULL)
		return -1;
	else
		return (S->head)->elem;
}

// -----------------

int getPriority(char op) {
	if (op == '+' || op == '-')
		return 1;
	else if (op == '*' || op == '/')
		return 2;
	else if (op == '(')
		return 0;
}

void getPostfixExp(char* infixExp, char* result) {
	Stack* S = (Stack*)malloc(sizeof(Stack));
	S->head = NULL;

	//char result[100];
	int cur = 0;

	for (int i = 0; i < strlen(infixExp); i++) {
		char ch = infixExp[i];
		if (ch != '+' && ch != '-' && ch != '*' && ch != '/' && ch != '(' && ch != ')') { // 피연산자 일 때
			result[cur] = ch;
			cur++;
		}
		else if (ch == '(') { // 여는괄호 일 때
			push(S, '(');
		}
		else if (ch == ')') { // 닫는괄호 일 때
			while (top(S) != '(') {
				result[cur] = pop(S);
				cur++;
			}
			pop(S);
		} else { // 연산자 + - * / 일 때
			while (S->head != NULL && (getPriority(ch)<=getPriority(top(S))) ) {
				result[cur] = pop(S);
				cur++;
			}
			push(S, ch);
		}
	}

	while (S->head != NULL) {
		result[cur] = pop(S);
		cur++;
	}

	result[cur] = '\0';

	free(S);
}

int evalPostfixExp(char* exp) {
	Stack* S = (Stack*)malloc(sizeof(Stack));
	S->head = NULL;

	for (int i = 0; i < strlen(exp); i++) {
		char ch = exp[i];
		if (ch != '+' && ch != '-' && ch != '*' && ch != '/') { // 피연산자 일 때
			push(S, ch - '0');
		}
		else { // 연산자일 때
			int n2 = pop(S);
			int n1 = pop(S);
			int result;
			if (ch == '+')
				result = n1 + n2;
			else if (ch == '-')
				result = n1 - n2;
			else if (ch == '*')
				result = n1 * n2;
			else if (ch == '/')
				result = n1 / n2;

			push(S, result);
		}
	}

	int result = pop(S);

	free(S);

	return result;
}

int main() {
	char infixExp_1[100] = "1+2-3";
	char infixExp_2[100] = "1+(2*(3+4))-5*4";

	char postfixExp_1[100];
	char postfixExp_2[100];
	getPostfixExp(infixExp_1, postfixExp_1);
	getPostfixExp(infixExp_2, postfixExp_2);

	printf("Infix\t%s\n", infixExp_1);
	printf("Postfix\t%s\n", postfixExp_1);
	printf("result\t%d\n", evalPostfixExp(postfixExp_1));
	printf("\n");
	printf("Infix\t%s\n", infixExp_2);
	printf("Postfix\t%s\n", postfixExp_2);
	printf("result\t%d\n", evalPostfixExp(postfixExp_2));
	/*
	Infix   1+2-3
	Postfix 12+3-
	result  0

	Infix   1+(2*(3+4))-5*4
	Postfix 1234+*+54*-
	result  -5
	*/
}

기간

구성요소

• 크기 n의 1차원 배열 V
  • n개의 데이터원소를 담는다.
• 크기 n의 1차원 배열 A
  • 각 원소에 대해 X[j]≤X[i]인 연속적인 X[j]원소의 개수를 담는다.
• 스택 S

구현

• 의사코드

Alg span()
1. S ← empty Stack
2. for i ← 0 to n-1
     while(!S.isEmpty() && V[S.top()] ≤ V[i])
       S.pop()
     if(S.isEmpty())
       A[i] ← i+1
     else
       A[i] ← i-S.top()
     S.push(i)
3. while(!S.isEmpty())
     S.pop()
4. return

• C언어

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

typedef struct _Node {
	struct _Node* next;
	char elem;
} Node;

typedef struct _Stack {
	Node* head;
	int size;
} Stack;

Node* getNode() {
	Node* p = (Node*)malloc(sizeof(Node));
	p->next = NULL;
	return p;
}

void putNode(Node* p) {
	free(p);
}

void push(Stack* S, char elem) {
	Node* p = getNode();
	p->next = S->head;
	p->elem = elem;
	S->head = p;

	(S->size)++;
}

char pop(Stack* S) {
	if (S->head == NULL)
		return -1;
	else {
		Node* q = S->head;
		char n = q->elem;
		S->head = (S->head)->next;
		putNode(q);
		(S->size)--;
		return n;
	}
}

char top(Stack* S) {
	if (S->head == NULL)
		return -1;
	else
		return (S->head)->elem;
}

// -----------------

void getSpan(int* src, int* span, int size) {
	Stack* S = (Stack*)malloc(sizeof(Stack));
	S->head = NULL;

	for (int i = 0; i < size; i++) {
		while (S->head != NULL && src[top(S)] <= src[i])
			pop(S);

		if (S->head == NULL)
			span[i] = i + 1;
		else
			span[i] = i - top(S);

		push(S, i);
	}

	// 정리
	while(S->head != NULL)
		pop(S);
	free(S);
}

int main() {
	int src[10] = { 50, 10, 20, 100, 110, 50, 60, 70, 200, 10 };
	int span[10];
	int size = 10;

	getSpan(src, span, size);

	for (int i = 0; i < 10; i++)
		printf("%d\t", i);
	printf("\n");

	for (int i = 0; i < 10; i++)
		printf("%d\t", src[i]);
	printf("\n");

	for (int i = 0; i < 10; i++)
		printf("%d\t", span[i]);
	printf("\n");

	return 0;
}

다중스택

여러개의 스택을 구현

메소드

• integer size()
• bool imEmpty()
• bool isFull()
• init() : n개의 스택 초기화
• push(i, e) : i번째 스택에 원소 e 삽입
• element pop(i) : i번째 스택의 최근 삽입된 원소 삭제하고 반환
• element top(i) : i번째 스택의 최근 삽입된 원소 반환

1차원 배열 구현

• 구성요소
  • n개 스택을 담는, 크기 N의 1차원배열 V
  • base 인덱스를 저장하는, 크기 n+1의 1차원배열 B (i번째 스택 시작 직전의 인덱스)
  • top인덱스를 저장하는, 크기 n의 1차원배열 T
• 의사코드

Alg init()
1. stackSize ← N/n
2. for i ← 0 to n-1
     B[i] ← stackSize * i - 1
     T[i] ← stackSize * i - 1
3. B[n] ← N-1 	{ 배열의 마지막 인덱스 }
4. return

Alg push(i, e)
1. if(T[i] = B[i+1])
     fullStackException()
2. T[i] = T[i] + 1
3. V[T[i]] = e
4. return

Alg pop(i)
1. if(T[i] = B[i])
     emptyStackException()
2. T[i] = T[i] - 1
3. return V[T[i]+1]

• c언어

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int V[9];
int base[4];
int top[3];

void push(int idx, int elem) {
	top[idx]++;
	V[top[idx]] = elem;
}

int pop(int idx) {
	top[idx]--;
	return V[top[idx] + 1];
}

void print(int idx) {
	for (int i = base[idx]+1; i <= top[idx]; i++) {
		printf("%d ", V[i]);
	}
	printf("\n");
}

int main() {
	
	int stackSize = 9 / 3; // V의 크기 9, 스택의 개수 3 ---> 스택별 크기 3
	
	// init
	for (int i = 0; i < stackSize; i++) {
		base[i] = stackSize * i - 1;
		top[i] = stackSize * i - 1;
	}
	base[3] = 9 - 1;

	// action
	push(0, 1); push(0, 2); push(0, 3);
	push(1, 10); push(1, 15);
	push(2, 20); push(2, 23); push(2, 26);
	print(0); print(1); print(2);
	/*
		1 2 3
		10 15
		20 23 26
	*/

	pop(0); pop(0); pop(0);
	pop(1);
	pop(2);
	print(0); print(1); print(2);
	/*

		10
		20 23
	*/

	return 0;
}

연결리스트의 배열 구현

• 구성요소
  • n개 스택의 top(head)노드를 담는, 크기 n의 1차원배열 T
  • n개의 연결리스트 S1, S2, S3, ..., Sn
• 의사코드

Alg init()
1. for i ← 0 to n-1
     T[i] ← ∅
2. return

Alg push(i, e)
1. p ← getNode()
2. p.elem ← e
3. p.next ← T[i]
4. T[i] ← p
5. return

Alg pop(i)
1. if(T[i] = ∅)
     emptyStackException()
2. p ← T[i]
3. removedElem ← p.elem
4. T[i] = T[i].next
5. putNode(p)
6. return removedElem

• c언어

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

typedef struct _Node {
	struct _Node* next;
	char elem;
} Node;

Node* T[3]; // 3개의 스택

void push(int idx, int elem) {
	Node* p = (Node*)malloc(sizeof(Node));
	p->next = T[idx];
	p->elem = elem;
	T[idx] = p;
}

int pop(int idx) {
	Node* q = T[idx];
	int e = q->elem;
	T[idx] = T[idx]->next;
	free(q);
	return e;
}

void print(int idx) {
	Node* p = T[idx];
	while (p != NULL) {
		printf("%d ", p->elem);
		p = p->next;
	}
	printf("\n");
}
// -----------------

int main() {
	
	// init
	for (int i = 0; i < 3; i++)
		T[i] = NULL;
	
	// action
	push(0, 1); push(0, 2); push(0, 3);
	push(1, 10); push(1, 15);
	push(2, 20); push(2, 23); push(2, 26);
	print(0); print(1); print(2);
	/*
		3 2 1
		15 10
		26 23 20
	*/

	pop(0); pop(0); pop(0);
	pop(1);
	pop(2);
	print(0); print(1); print(2);
	/*
	
		10
		23 20
	*/

	return 0;
}