스택(Stacks) & 큐(Queue) 자료구조

추상 데이터 타입(Abstract Data Types, ADTs)

- 추상 데이터 타입은 추상적인 데이터 구조임.

- 추상 데이터 타입은 데이터를 저장하고 , 데이터를 연산하고 , 연산과 관련된 에러 조건을 구체화함.

 

EX ) 간단한 주식 매매 시스템을 ADT Modeling 한다고 가정하자.

데이터 저장 : 매수 / 매도 명령 데이터가 저장된다.

데이터 연산 : 연산들은 구매(stock, shares, price) / 판매(stock, shares, price) / 취소(order) 등을 지원한다.

에러 조건 : 존재하지 않는 주식에 대한 매수 / 매도 명령 , 존재하지 않는 명령에 대한 취소 등이 있을 것이다.

 

스택(Stacks) ADT

- Stack의 ADT는 임의의 객체들을 저장한다.

- 삽입과 삭제연산을 LIFO(Last-In-First-Out) 구조로 수행한다.

- 메인 스택 연산

push(object) - 원소를 삽입한다.

object pop() - 마지막에 삽입된 원소를 제거한다.

object top() - 마지막에 삽입된 원소를 제거하지 않고 리턴한다.

int size() - 원소가 저장된 개수를 리턴한다.

boolean empty() - 저장된 원소가 없는지(스택이 비었는지) 확인한다.

 

간단한 코드로 스택을 확인해 본다면 ,

template <typename E>
class Stack {
public:
	int size() const;
    bool empty() const;
    const E& top() const;
    	throw(StackEmpty);
    void push(const E& e);
    void pop() throw(StackEmpty);
    }

- 스택의 종류에는 배열을 활용한 스택과 링크드리스트를 활용한 스택이 있다.

- 스택에서 공간은 O(n)을 사용 / 각 연산에 대한 시간복잡도는 O(1)

- 스택의 제약은 최대 크기가 반드시 정의되어야 하고, 바꿀 수 없음.

- 꽉 찬 스택에 새 원소를 push하는 것은 특정 실행 예외를 발생시킴.

 

큐(Queue) ADT

- 큐 ADT는 임의의 객체를 저장함.

- 삽입과 삭제연산을 FIFO(First-In-First-Out) 구조로 수행함.

- 삽입은 큐의 rear(맨 뒤)에 이루어지고, 삭제는 큐의 front(맨 앞)에서 이루어짐.

- 메인 큐 연산

enqueue(object) - 큐의 끝에 원소를 삽입.

dequeue() - 큐의 맨 앞 원소를 삭제

object front() - 제거하지 않고 맨 앞 객체를 리턴.

int size() - 저장된 원소의 갯수를 리턴.

boolean empty() - 큐가 비었는지 확인.

 

간단한 코드로 큐를 확인해 본다면 ,

template <typename E>
class Queue {
public:
	int size() const;
    bool empty() const;
    const E& front() const;
    	throw(QueueEmpty);
    void enqueue(const E& e);
    void dequeue()
    	throw(QueueEmpty);
};

- 큐의 종류에는 배열을 활용한 큐(환형배열)와 , 싱글 링크드 리스트를 활용한 큐가 있다.

- 싱글 링크드 리스트를 활용한 큐의 공간은 O(n)을 사용하고, 각 연산에 대한 시간복잡도는 O(1) 이다.