본문 바로가기

분류 전체보기216

원형큐 선형큐의 문제점- front와 rear의 값이 계속 증가만 하기 때문에 언젠가는 배열의 끝에 도달- 배열의 앞부분이 비어 있더라도 사용하지 못함- 따라서 주기적으로 모든 요소를 왼쪽으로 이동시켜야 함- 이와 같은 문제를 해결하기 위해 원형 배열을 고려 원형큐- front와 rear의 값이 배열의 끝인 (MAX_QUEUE_SIZE-1)에 도달하면 다음에 증가되는 값이 0이 되도록 함- 처음과 끝이 연결된 원형 배열을 상정- 원형큐에서 front와 rear의 초기값은 -1이 아닌 0- front는 항상 큐의 첫 번째 요소의 하나 앞을, rear는 마지막 요소를 가리킴- 데이터가 삽입 시 rear가 먼저 증가되고, 증가된 위치에 데이터 삽입- 데이터 삭제 시 front가 먼저 증가되고, 증가된 위치에서 데이터.. 2024. 7. 14.
선형큐 1차원 정수 배열을 사용하여 정수를 저장하는 큐 작성- 1차원 정수 배열을 정의하고- 삽입, 삭제를 위한 변수인 front와 rear 생성- front는 큐의 첫 번째 요소를 가리키고, rear는 큐의 마지막 요소를 가리킴#include #include #define MAX_QUEUE_SIZE 100typedef int element;typedef struct { int front; int rear; element data[MAX_QUEUE_SIZE];} QueueType;//오류 함수void error(char* message) { fprintf(stderr, "%s\n", message); exit(1);}void init_queue(QueueType* q) { q->front = -1; q->rea.. 2024. 7. 14.
큐 큐(queue)- 선입선출(FIFO, First-In First-Out) 구조- 뒤에서 새로운 데이터가 추가되고 앞에서 데이터가 하나씩 삭제되는 구조- 스택과 달리 큐에서는 삽입과 삭제가 다른 쪽에서 일어남- 삽입이 일어나는 곳은 후단(rear), 삭제가 일어나는 곳은 전단(front)- 추상 자료형 큐의 연산들은 추상 자료형 스택과 매우 유사- is_empty 연산은 큐가 비어 있을 때 TRUE를, 그렇지 않으면 FALSE를 반환- is_full 연산은 큐가 가득 찼으면 TRUE를, 그렇지 않으면 FALSE를 반환- enqueue 연산은 큐의 맨 뒤에 새로운 요소를 추가- dequeue 연산은 큐의 맨 앞에 있는 요소를 꺼내서 외부로 반환- 스택과 달리 삽입, 삭제가 큐의 양 끝에서 일어남- 스택에서 .. 2024. 7. 14.
백준 4949: 균형잡힌 세상(java) 문제풀이 BufferedReader로 입력받은 값을 toCharArray() 메소드를 이용해 문자 배열 inputChar에 저장하고, inputChar의 길이가 1이고 inputChar[0]이 '.'이면 전체 반복을 종료하도록 한다. 그 외의 경우, 입력 문자가 왼쪽 괄호('(', '[')이면 스택에 입력값을 push하고, 오른쪽 괄호(')', ']')이면 pop한 값과 비교해 옳은 입력인지 판단한다.왼쪽 괄호의 개수와 오른쪽 괄호의 개수가 동일한지(stack.empty())방금 입력된 괄호가 스택에 가장 최근에 삽입된 괄호와 쌍이 맞는지만 검사하면 되므로, 괄호가 아닌 문자에 대해서는 따로 연산할 필요가 없다.import java.io.BufferedReader;import java.io.IOExcep.. 2024. 7. 12.
백준 10773: 제로(java) 문제풀이 '가장 최근에 쓴 수' 라는 표현에 주목하자. 가장 최근에 입력된 값을 불러오려면 당연히 후입선출 구조의 스택을 사용해야 한다.정수가 0일 경우에 가장 최근에 쓴 수를 지우는 것은 pop, 아닐 경우 해당 수를 쓰는 것은 push이다.스택을 완성한 뒤, for문과 get() 메소드를 이용해 스택 내부 모든 원소들의 합을 구해 출력한다.import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Stack;public class Main { public static void main(String[] args) throws IOException{ BufferedRead.. 2024. 7. 12.
백준 28278: 스택 2(java) 문제문제에는 스택을 구현하라고 돼 있지만 자바 기본 Stack 클래스를 사용해도 될 것 같다.직접 구현하려면 아래 링크 참조풀이 명령이 줄글로 되어 있지만, 1번은 push(), 2번은 pop(), 4번은 empty(), 5번은 peek()와 동일하다.모두 Stack 클래스의 기본 메소드로 제공되는 것들이다.Stack 클래스는 Vector 클래스를 상속받으므로 size() 메소드를 사용해 3번 또한 해결할 수 있다.아래는 기타 설명 링크들Stack 클래스에 대한 더 자세한 설명 링크Stack을 직접 구현하는 방법 링크자료구조-스택 개념 설명 링크 늘 그렇듯 BufferedReader로 문자열을 입력받아 StringTokenizer로 분리하였다. 명령은 cmd, 입력값은 num에 저장하였고(num은 1번 .. 2024. 7. 12.

티스토리툴바