Computer Science/자료구조
2. 스택 / 큐
- -
728x90
반응형
등장 배경
이 2개의 자료구조가 등장한 배경은 연속적인 데이터를 처리하는 방식의 효율적인 처리를 하기 위함이다.
스택의 경우, LIFO(Last in First out) 구조로 후입선출이 필요할 때 사용하게 된다. 대표적인 예시로 하노이탑을 생각해보면 된다. 나중에 들어온 것이 먼저 들어온 것보다 더 먼저 처리되어야 한다.
큐의 경우, FIFO(First in First out) 구조로 선입선출이 필요할 때 사용하게 된다. 대표적인 예시로 줄 서는 것을 생각해보면 된다. 먼저 들어온 것이 더 먼저 처리되어야 한다.
기본적으로 데이터들을 순차적으로 처리하는데, 처리하는 순서의 기준이 분명한 경우 해당 자료구조를 사용하게 되면 쉽게 처리할 수 있게 된다.
구현 방법
스택과 큐를 구현하는 방법에는 연결리스트를 활용하는 방법과 배열을 활용하는 방법이 존재한다.
연결리스트 게시물에서 언급한 것처럼, 이 두 방식의 차이는 전체 input값으로 들어오는 변수의 개수를 알 수 있는지 여부이다.
배열의 단점은 최초 선언 당시 크기를 나중에 변경할 수 없다. 물론 매우 크게 배열의 크기를 잡아서 해결할 수 있지만, 이러면 데이터 누실이 많이 발생하게 된다. 다만, 이러한 단점에도 불구하고, 배열로 스택과 큐를 구현하게 되면 상대적으로 간단하게 구현할 수 있다는 장점이 있다. (그럼에도 불구하고 그렇게 추천하지는 않는다.)
1. 연결 리스트를 활용한 방법
연결리스트를 활용한 스택과 큐를 살펴보도록 하자.
// Stack by using Linked list
class CLinkedList{
public final Node header;
public int size;
public CLinkedList(){
Node newnode = new Node(-1);
newnode.prev = newnode;
newnode.next = newnode;
header = newnode;
size = 0;
}
public int empty(){
if(size == 0) return 1;
else return 0;
}
public void addNodeBack(int x) {
Node newnode = new Node(x);
newnode.next = header;
newnode.prev = header.prev;
header.prev = newnode;
size++;
}
public int deleteNodeBack() {
if(size == 0) return -1;
else {
int val = header.prev.data;
header.prev.prev.next = header;
header.prev = header.prev.prev;
size--;
return val;
}
}
public int getNodeBack() {
if(size == 0) return -1;
else return header.prev.data;
}
}
class stack{
CLinkedList list;
public stack() {
list = new CLinkedList();
}
public void push(int x) {
list.addNodeBack(x);
}
public int pop() {
return list.deleteNodeBack();
}
public int size() {
return list.size;
}
public int empty() {
return list.empty();
}
public int top() {
return list.getNodeBack();
}
}// Queue by using Linked list
class Node{
public int data;
public Node prev;
public Node next;
public Node(int x){
data = x;
prev = null;
next = null;
}
}
class linkedList{
public Node head;
public Node tail;
int size;
public linkedList(){
size = 0;
head = null;
tail = null;
}
public void inputBack(int x){
Node newnode = new Node(x);
newnode.next = null;
newnode.prev = tail;
if(tail == null){
tail = newnode;
head = newnode;
}
else{
tail.next = newnode;
tail = newnode;
}
size++;
}
public int eraseFront(){
if(head == null) return -1;
int var = head.data;
if(size == 1){
head = null;
tail = null;
}
else{
head.next.prev = null;
head = head.next;
}
size--;
return var;
}
public int isEmpty(){
if(size == 0) return 1;
else return 0;
}
public int getFrontElement(){
if(head == null) return -1;
else return head.data;
}
public int getBackElement(){
if(tail == null) return -1;
else return tail.data;
}
}
class Queue{
private linkedList list;
public Queue(){
list = new linkedList();
}
public void push(int x){
list.inputBack(x);
}
public int pop(){
return list.eraseFront();
}
public int size(){
return list.size;
}
public int empty(){
return list.isEmpty();
}
public int front(){
return list.getFrontElement();
}
public int back(){
return list.getBackElement();
}
}코드에서 볼 수 있는 것처럼, 연결리스트만 잘 구현해놓으면 큐와 스택은 쉽게 구현할 수 있다.
2. 배열을 활용한 방법
스택의 경우에는 쉽게 구현할 수 있다. 왜냐하면, LIFO 구조가 배열의 마지막 index를 기준으로 넣고 빼는 것과 근본적으로 다를 것이 없다. 따라서 어느 index까지 element가 찼는지만 컨트롤 해주면 된다.
// Stack by using Array
class stack{
public final int[] data;
public int size;
public int cur;
public stack(int x){
data = new int[x];
size = x;
cur = -1; // data가 안들어가있는 것을 명시적으로 표시
}
public void push(int x){
data[cur + 1] = x;
size++;
cur++;
}
public int pop(){
if(cur == -1) return -1;
else{
size--;
return data[cur--];
}
}
public int size(){
return cur + 1;
}
public int empty(){
if(cur == -1) return 1;
else return 0;
}
public int top(){
if(cur == -1) return -1;
else{
return data[cur];
}
}
}큐의 경우에는 상당히 그 양상이 복잡하다.
왜냐하면, 빼는 것은 배열 기준 앞쪽 부분이고 넣는 것은 배열 기준 뒤쪽 부분이기 때문이다. 즉 스택과 달리 넣는 부분과 뺴는 부분의 위치가 다르기 때문에 넣는 부분과 빼는 부분의 index를 둘 다 관리해주어야 한다.
그리고, 추가적인 문제가 존재하는데 삭제가 반복됨에 따라서 저장할 수 있는 공간이 감소하게 된다는 것이다.
전체 배열의 크기가 5라고 하면, 점차적으로 data가 나가는 부분의 index가 커짐에 따라서 결과적으로 넣을 수 있는 데이터들의 범위가 감소하게 된다. 이 부분은 circular Linked list에서처럼 Array를 circular로 이어주면 된다. 즉 enqueue함에 따라서 front가 한칸 증가하고, dequeue함에 따라서 rear가 한칸 감소하는 경향성을 띄게 된다.
즉, 배열이 빈 경우 rear이 front가 한칸 더 뒤쪽에 있게 된다.
다만, 위 사진에서 보이는 것처럼, Circular를 단순히 구현하는 방식으로는 데이터가 다 들어간 상태와 초기의 하나도 없는 상태를 구분하지 못한다.
즉, 이 상태를 구분하기 위해서 1개의 array index를 추가적으로 더 잡는 것이다.
따라서 빈 상태는 front 바로 뒤에 rear가 있는 경우이고, 꽉 차 있는 상태는 front 2칸 뒤에 rear가 있는 상황이다.
input값이 들어와서 rear가 밀리는 것에 제한을 걸게되면, front 바로 뒤에 rear가 오는 경우는 rear가 밀려서 만들어지는 상태가 아니라 front가 앞으로 이동함에 따라 형성되는 결과이므로 무조건적으로 empty queue임을 보장할 수 있다.
// Queue by using Array
class Queue{
public int[] data;
public int front, rear; // Rear : Empty상태가 아니면, 가장 최근에 들어온 element의 index
public int size;
public int cur_size;
public Queue(int x){
x++;
data = new int[x];
size = x;
front = 0;
rear = size - 1;
}
public int empty(){
if((rear + 1) % size == front) return 1;
else return 0;
}
public boolean full(){
return ((rear + 2) % size == front);
}
public void push(int x){
if(!full()){
rear = (rear + 1) % size;
data[rear] = x;
}
}
public int pop(){
if(empty() == 1) return -1;
else{
int ret = data[front];
front = (front + 1) % size;
return ret;
}
}
public int front(){
if(empty() == 1) return -1;
else{
return data[front];
}
}
public int back(){
if(empty() == 1) return -1;
else{
return data[rear];
}
}
public int size(){
if(empty() == 1) return 0;
if(front <= rear){
return rear - front + 1;
}
else{
return size - (front - rear - 1);
}
}
}
들어있는 데이터의 양을 구하기 위해서 size()를 짤 때, 적당히 이런 방식으로 짜도 되기는 하는데
연결 리스트에서 그랬던 것처럼 따로 element의 개수를 관리하는 member variable을 하나 잡는 편이 더 유용하다.
단지, 사용하지 않은 이유는 수업 때 해당 내용을 다루지 않았기 때문이기도 하고 또한 굳이 배열 공간을 1개 더 추가적으로 잡은 목적을 부각시키기 위함도 있다. 만약 들어간 element의 개수를 관리하는 변수를 추가하게 되면 위에서 언급한 2케이스 상황을 쉽게 구분할 수 있다.
반응형
Contents
소중한 공감 감사합니다