1주차 - 스택과 큐(10828, 10845)

스택(stack)

후입선출(LIFO: Last-In First-Out)
 :가장 최근에 들어온 데이터가 가장 위에 있게 되고, 또 가장 먼저 나간다.

연산

• create(size) : 크기가 size인 스택을 생성함
• push(element) : 스택에 새로운 원소를 삽입함
                       top을 먼저 증가시키고 그 위치에 원소를 삽입함
• is_full() : 스택이 가득 채워져 있는지 검사함
             가득 채워져 있으면 true, 하나라도 비어 있다면 false를 return
• pop() : 스택에서 원소 하나를 없앰
           top이 가리키는 원소를 가져오고 top을 하나 감소시킴
• is_empty() : 스택이 비어 있는지 검사함
                 스택이 비어 있으면 true, 비어 있지 않으면 false를 return

배열로 구현한 소스코드

#include <iostream>
#include <stdlib.h> 

#define MAX_STACK_SIZE 100	// 스택의 최대 크기
int stack[MAX_STACK_SIZE];	// 1차원 배열 
int top = -1;
typedef int element;	// 데이터 자료형

// 공백 상태 검출 함수
int is_empty() {
	return (top == -1);
}

// 포화 상태 검출 함수
int is_full() {
	return (top == (MAX_STACK_SIZE - 1));
}

// 삽입 함수
void push(element e) {
	if (is_full()) {
		fprintf(stderr, "스택이 포화상태입니다.\n");
		return;
	}
	else {
		stack[++top] = e;
	}
}

// 삭제 함수
element pop(){
	if (is_empty()) {
			fprintf(stderr, "스택이 공백상태입니다.\n");
			exit(1);
		}
	else {
		return stack[top--];
		}
}

---

큐(queue)

선입선출(FIFO: First-In First_Out)
 : 가장 처음에 들어온 데이터가 가장 먼저 나감
   반대쪽에 똑같은 구멍이 뚫린 스택

선형큐: 일반 배열과 비슷한 형태
          원소가 처음 들어온 자리에 고정됨
          메모리 낭비가 심함(연산할 때 모든 연소의 자리를 옮겨줘야 하는 등)

원형큐: 선형 큐를 가상으로 동그랗게 말음
          큐의 최대 범위를 넘어가면 첫번째 인덱스로 돌아가게 함

연산

• create(size) = 크기가 size인 스택을 생성
• is_full() = 스택이 가득 채워져 있는지
• is_empty() = 스택이 비어 있는지 검사
• enqueue(element) = rear에 element를 삽입
• dequeue() ::= front에 있는 elemen를 제거
• peek() ::= front에 있는 element를 읽어서 반환

원형 큐 소스코드

#include <iostream> 
#include <stdlib.h> 
using namespace std;

#define MAX_QUEUE_SIZE 100

typedef int element;
typedef struct {
	element data[MAX_QUEUE_SIZE] ; 
    int front, rear; 
} QueueType;

void enqueue(QueueType *q, element item) { 
	if (is_full(q)) { 
    	error(“큐가 포화상태입니다.”); 
	}
    else { q->rear = (q->rear + 1) %MAX_QUEUE_SIZE ; 
    q->data[rear] = item; 
    }
}

int dequeue(QueueType *q) {
	if (is_empty(q)) { 
    	error(“큐가 공백상태입니다.”);
    }else { 
    	q->front = (q->front + 1) %MAX_QUEUE_SIZE ;
        return q->data[q->front]; 
    } 
}

int peek(QueueType *q) {
	if (is_empty(q)) { 
    	error(“큐가 공백상태입니다.”);
	} else{
    	return q->data[(q->front + 1) %MAX_QUEUE_SIZE ];
    }
}

---

백준 10828번 문제: 배열을 이용한 스택 구현

https://www.acmicpc.net/problem/10828

10828번: 스택

c++에는 STL stack이 있어서 스택을 간편하게 사용할 수 있다.

#include <stack>	// 헤더파일
stack<int> stack;	// stack<데이터타입> 이름; 으로 선언

 

STL stack 기본 함수

• push(element) : top에 원소를 추가
• pop() : top에 있는 원소를 삭제
• top() : top에 있는 원소를 반환(조회)
• empty() : 스택이 비어있으면 true, 아니면 false 반환
• size() : 스택의 사이즈를 반환

이를 사용하지 않고 배열을 통해 문제를 해결한 코드는 아래와 같다.
top을 사용하지 않고 배열의 크기를 나타내는 s를 통해 코드를 구성했다.

#include<iostream>
using namespace std;
int s; // stack의 size
int a[10001];

void push(int x) {	// a[++top] = x;
	a[s] = x;   
	s++;
}

int pop() {
	if (s == 0) return -1;
	int t = a[s - 1];
	s--;
	return t;	// return a[top--]
}

int size() {
	return s;
}

int top() {
	if (s == 0) return -1;
	return a[s - 1];
}

int empty() {	// top == -1
	if (s == 0) return 1;
	else return 0;
}

int main() {
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		string command;
		cin >> command;
		if (command == "push") {
			int n;
			cin >> n;
			push(n);
		}
		if (command == "pop") {
			cout << pop() << '\n';
		}
		if (command == "top") {
			cout << top() << '\n';
		}
		if (command == "size") {
			cout << size() << '\n';
		}
		if (command == "empty") {
			cout << empty() << '\n';
		}
	}
}

 

---

백준 10845번 문제: 배열을 이용한 큐 구현

https://www.acmicpc.net/problem/10845

10845번: 큐

마찬가지로 C++의 STL queue를 이용하면 쉽게 큐를 구현할 수 있다.

#include <queue>	// 헤더파일
queue<int> q;		// queue<데이터 타입> 이름; 큐 선언

STL queue 기본 함수

• push(element) : 원소를 추가
• pop() : front에 있는 원소를 삭제
• front() : front에 있는 원소를 반환
• back() : back에 있는 원소 반환
• empty() : 큐가 비어있으면 true, 아니면 false 반환
• size() : 큐의 사이즈를 반환

선형큐이기 때문에 스택과 유사하다. 따라서 STL queue를 활용하여 코드를 구성했다.

#include <iostream>
#include <queue>
using namespace std;

int main() {

	queue<int> q;

	int n;
	cin >> n;

	for (int i = 0; i < n; i++) {
		string command;
		cin >> command;
		if (command == "push") {
			int x;
			cin >> x;
			q.push(x);
		}
		else if (command == "pop") {
			int front = -1;
			if (!q.empty()) {
				front = q.front();
				q.pop();
			}
			cout << front << endl;
		}
		else if (command == "size") {
			cout << q.size() << endl;
		}
		else if (command == "empty") {
			int empty = 0;
			if (q.empty())
				empty = 1;
			cout << empty << endl;
		}
		else if (command == "front") {
			int front = -1;
			if (!q.empty())
				front = q.front();
			cout << front << endl;
		}
		else if (command == "back") {
			int back = -1;
			if (!q.empty())
				back = q.back();
			cout << back << endl;
		}
	}
	return 0;
}