[자료구조] Stack & Queue 개념 정리 및 구현

Stack/Queue

Stack과 Queue는 통상적으로 List 자료구조를 배운 이후에 학습을 진행하기 때문에, 자료구조라는 말 뜻을 아실 거라고 생각합니다.

두 자료구조 역시 선형 자료구조 중 하나인데, 스택과 큐는 오직 한 방향에서의 데이터의 삽입과 삭제를 진행하는 자료구조입니다.

 

두 자료구조를 가장 잘 나타낼 수 있는 말이 있죠.

Stack : 후입선출(後入先出)

Queue : 선입선출(先入先出)

말 그대로, 스택은 가장 마지막에 삽입한 데이터가 가장 먼저 추출되고, 큐는 가장 먼저 들어온 데이터가 가장 먼저 추출되는 형식입니다.

실생활을 예로 들자면, 후입 선출 알고리즘은 실행 취소(Ctrl+z, undo)로 예를 들 수 있고, 선입선출은 일반적으로 음식점에서 채소 및 재료를 꺼낼 때 먼저 들어온 재료를 먼저 꺼내도록 하고 있죠. 

이를 코드로 구현하면 됩니다.

 

시간 복잡도

- 조회(가장 앞, 뒤)

  O(n)

- 삽입, 삭제(가장 앞, 뒤)

  O(1)

 

List 자료구조의 조회, 삽입, 삭제와 시간 복잡도가 동일하죠?

조회는 한 방향으로부터 하나씩 하나씩 데이터를 찾아 나가야 하므로, 최악의 경우  O(n)이 되는 것이고,

삽입과 삭제는 언제나 한 방향에서 첫 번째 값을 추출하기 때문에 O(1)이 나오게 됩니다.

 

메커니즘

자료구조들은 주로 포인터를 사용하는 C 또는 C++을 사용하는 것이 제맛이지만..

다른 자료구조/알고리즘 학습 시 일관성을 위해 Java로 구현하도록 하겠습니다.

 

기능 설명 및 구현을 하기 전에, 삽입과 삭제에 대한 메커니즘을 확실하게 할 필요가 있을 것 같습니다.

그러기 위해 다음과 같이 저장되어 있는 자료를 Stack, Queue 각각에서 어떻게 삽입/추출하는지 맞추어 보세요.

 

문제 1. Stack

 

문제 2. Queue

 

 

 

 

답 1. Stack

답 2. Queue

쉽게 맞추셨거나, 한눈에 보면 어떻게 저장되고 삭제되는지 눈에 들어오실 것 같아요.

 

다음은 기능 목록을 기술할 예정인데, Stack과 Queue는 방향성이라는 한 끝 차이이므로, 기능 및 구현은 Stack 자료구조를 기준으로 기술하겠습니다.

또한, 편의를 위해 저장되는 자료는 int형으로 진행했습니다.

기능

- void push(int data)

배열의 가장 마지막에 data 삽입

 

- int pop()

배열의 가장 마지막 data 삭제 및 반환

 

- int peek()

배열의 가장 마지막 data 반환

 

- void clear()

전체 자료 삭제

 

- String toString()

저장된 자료들을 문자열로 만들어 반환

 

구현

package Stack_Queue;

// Stack
// 편의를 위해 int 자료형만 저장 가능한 형태
public class Stack {
	private static final int maxCount = 100;
	private int size; // 총 크기이자 size를 가리키는 변수
	private int[] values;

	// 생성자를 통한 초기화
	public Stack() {
		size = 0;
		values = new int[maxCount];
	}

	// 가장 위에 값 삽입
	public void push(int data) {
		values[size++] = data;
	}

	// 가장 위에 있는 값 추출
	public int pop() {
		int rData = values[size];
		values[size--] = 0;

		return rData;
	}

	// 가장 위에 있는 값 조회
	public int peek() {
		if (size > 0) {
			return values[size - 1];
		} else {
			return -1;
		}

	}

	// 모든 값 삭제
	public void clear() {
		for (int i = 0; i < size; i++) {
			pop();
		}
		size = 0;
	}

	// 출력을 위한 String 반환
	public String toString() {
		String str = "";
		if (size > 0) {
			str = String.valueOf(values[size - 1]);
			for (int i = size - 2; i >= 0; i--) {
				str += ", " + String.valueOf(values[i]);
			}
		}else {
			str = "No Data";
		}

		return str;
	}
}

 

Github : https://github.com/WOOOOOOOONG/Learning-Algorithm

WOOOOOOOONG/Learning-Algorithm

Learning Data-Structure and Algorithm. Contribute to WOOOOOOOONG/Learning-Algorithm development by creating an account on GitHub.

github.com

틀린 내용 또는 질문 있으시면, 편하게 댓글 남겨주시면 감사하겠습니다.