[자료구조와 알고리즘] Stack and Queues

9 분 소요

Stacks and Queues

Stack ADT

Stacks

stack은 부엌에서 접시를 쌓는 것과 유사한 방식으로 data를 저장하는 자료구조이다.

스택의 제일 윗 부분(top)에 접시를 둘 수 있고, 접시가 필요할 때 이 스택의 제일 윗 부분(top)에서 가져올 수 있다. 스택에 추가되는 마지막 접시는 그 스택으로부터 제일 먼저 집어 들어지는 것이다.

이와 유사하게 stack data structure는 우리로 하여금 one end로부터 data를 읽고 저장할 수 있도록 하고 마지막에 추가되는 element가 첫 번째로 집어진다.

따라서, stack은 last in, first out(즉, LIFO) 구조라고 한다.

Basic operations

stack구조에서 INSERT(삽입) operation은 Push라고 불리고 DELETE operation은 element 인자를 받지않는 것으로 POP이라고 불린다.

Stack implementation using Linked list

class Node:
    def __init__(self, data=None):
        self.data = data
        self.next = None
        
        
class Stack:
    def __init__(self):
        self.top = None
        self.size = 0

Stack을 사용하기 위해서는 Stack object(instance)를 만들고 해당 object로 stack class의 변수 및 함수에 접근한다.

Push operation

self가 의미하는 것은 현재 method가 갖고 있는 object를 의미한다.

def push(self, data):
        node = Node(data)
        
        if self.top: #스택이 비어있지 않다면
            node.next = self.top # 1
        self.top = node # 2
        sefl.size += 1

가장 먼저 저장할 data를 가지고 있는 Node object를 하나 만든다.
이제 이 node를 stack 구조에 넣어야 할 차례이다.
if self.top이 의미하는 것은 스택이 현재 비어 있지 않는지를 물어보는 것이다.
- 만약 비어있지 않다면 top을 새로 생성한 node의 next pointer가 가리키도록 한다.
- 만약 비어있다면 top이 새로 만든 node를 가리키게 한다.

Pop operation

def pop(self):
	if self.size == 0:
        return None
    
    data = self.top.data # 1
    self.top = self.top.next # 2
    self.size -= 1 
    return data

Peek operation

def peek(self):
    if self.size == 0:
        return None
    return self.top.data

스택의 구조를 바꾸지 않고 top의 값은 read해 오기만 한다.

전체 코드

class Node:
    def __init__(self, data=None):
        self.data = data
        self.next = None
        
        
class Stack:
    def __init__(self):
        self.top = None
        self.size = 0
        
	def push(self, data):
        node = Node(data)
        
        if self.top: #스택이 비어있지 않다면
            node.next = self.top # 1
        self.top = node # 2
        sefl.size += 1
        
	def pop(self):
        if self.size == 0:
            return None

        data = self.top.data # 1
        self.top = self.top.next # 2
        self.size -= 1 
        return data   
    
    def peek(self):
        if self.size == 0:
            return None
        return self.top.data

Bracket-matching application

이제 stack 구현을 어떻게 할 수 있는지를 보여주기 위한 예제를 살펴보자

괄호 검사

def check_brackets(statement):
    stack = Stack()
    for ch in statement:
        if ch in ('{', "[", '('):
            stack.push(ch)
        if ch in ('}', ']', ')'):
            last = stack.pop()
            if last == '{' and ch == '}':
                continue
            elif last == '[' and ch == ']':
				continue
            elif last == '(' and ch == ')':
                continue
            else:
                return False
    if stack.size > 0:
        return False
    else:
        return True
            

sl = ("{(foo)(bar)}[hello](((this)is)a)test",
      "{(foo)(bar)}[hello](((this)is)a test)",
      "{(foo)(bar)}[hello](((this)is)a)test((")

for s in sl:
    m = check_brackets(s)
    print("{}: {}".format(s, m))

{(foo)(bar)}[hello](((this)is)a)test: True
{(foo)(bar)}[hello](((this)is)a test): True
{(foo)(bar)}[hello](((this)is)a)test((: False

Stack implementation using Python list

data = "nse*a*qys** **eu***ot*i***"

stack = []
for ch in data:
	if ch == '*':
        print(stack.pop(), end='')
    else:
        stack.append(ch)

python의 list와 관련된 method를 적절히 사용하여 stack구조를 충분히 구현해 낼 수 있다.

관련된 문제

백준 9012 괄호

def solution():
    stack = []
    string = input()

    for i in string:
        if len(stack) == 0 and i == ')':
            print("NO")
            return

        if i == '(':
            
            stack.append(i)

        elif i == ')' and len(stack) != 0:
            stack.pop()

    if len(stack) == 0:
        print("YES")
        return

    else:
        print("NO")
        return

test_case = int(input())

for _ in range(test_case):
    solution()

tc = int(input())

for _ in range(tc):
    s = Stack()
    test = input()
    
    for ch in test:
        if ch == '(':
            s.push(ch)
        elif ch == ')' and s.size != 0:
            s.pop()
        
    if s.size == 0:
        print("YES")
    else:
        print("NO")

스택을 계속해서 만들기 때문에 메모리 낭비일 것 같다고 스택을 새로 만들지 않고 쓰던 걸 계속 사용하면 스택 안에 값이 남아있게 되는 문제가 발생할 수 있다.
한 test case를 진행 할 때마다 Stack()를 만들어주는 이유는 한 스택을 계속해서 사용하게 되면 스택이 비어있지 않은 경우가 발생할 수 있기 때문이다.

Stack Implementation in C

Array implementation

아래 그림에서 볼 수 있듯이, S[1…n] 배열에서 최대 n element의 stack을 구현할 수 있다.

S 스택의 배열 구현.
스택 원소는 옅게 칠해진 위치에만 보인다.
index는 1부터 시작
(a)
- Stack S는 4개의 element를 가진다.
- top element는 9
(b)
- Push(S, 17)와 Push(S, 3) 를 호출한 후의 Stack S 모습이다.
(c)
- Pop(S)을 호출한 후 Stack S는 가장 최근에 pushed 된 요소 3을 반환하였다.
- 비록 배열에 3이라는 요소가 여전히 보이겠지만, 얘는 더 이상 stack 안에 있는 것이 아니다.
- top element는 17
즉, pop이라는 method는 배열 안의 값을 실제로 삭제할 필요없이 top의 위치만으로 기능을 구현할 수 있는 것이다. (top 이후의 index에는 값이 있더라도 없는 것처럼 생각하는 것이다.)

top = 0 일 때, stack은 어떠한 element도 포함하지 않고 비어있는 것이다.

query operation 인 STACK-EMPTY에 의해 stack이 비어 있는지 테스트해 볼 수 있다. 만약, 빈 stack을 pop하려고 시도하면 stack이 underflow 되었다고 하고 이는 보통 error로 다루어 진다.

또한 만약 top이 n을 초과하였다면 stack은 overflows 되었다고 하고 이 역시도 error로 다루어 진다.

#include <stdio.h>
#include <stdlib.h>

#define N 100
char stack[N + 1];
int top = 0;

int is_empty();
{
    return top == 0;
}

int is_full();
{
    return top = N;
}

void push(char item){
    if (is_full()) {
        printf("stack overflow\n");
        exit(1);
    }
    stack[++top] = item;
}

char pop() {
    if (is_empty()) {
        printf("stack underflow\n");
        exit(1);
    }
    return stack[top--];
}

int main()
{
    char *data = "nse*a*qys** **eu***ot*i***";
    
    for (; *data; data++) {
        if (*data == '*')
            printf("%c", pop());
        else
            push(*data);
    }
    printf("\n");
    return 0;
}

nsea qyseyutoi

Linked-list implementation

push

pop

삭제할 노드를 del이라는 변수로 지칭하여 해당 노드 next 노드를 top이 가리킨다.

#include <stdio.h>
#include <stdlib.h>

typedef struct _Node {
    char data;
    struct _Node *next;
} Node;

Node *top = NULL; //stack top

int is_empty()
{
    return top == NULL;
}

void push(char item)
{
    Node *ins;
    
    ins = (Node *) malloc(sizeof(Node));
    ins -> data = item;
    ins -> next = NULL;
    
    if(!is_empty())
        ins -> next = top;
    top = ins;
}

char pop()
{
    Node *del;
    char item;
    
    if (is_empty()) {
        printf("stack underflow!\n");
        exit(1);
    }
    
    item = top->data;
    del = top;
    top = del->next;
    free(del);
    
    return item;
}

Queue ADT

Queues

queue는 다음과 같이 동작한다.

queue에 참석한 첫 번째 사람은 대게 첫 번째로 음식을 받는다.
그리고 모든사람은 그들 각자가 queue에 어떻게 참가했는지의 순서에 따라 음식을 받을 것이다.
FIFO가 queue의 개념을 가장 잘 설명한다.
- FIFO: first in, first out(선입 선출)

Basic operation

Queue implementation using Linked list

Linked list로 구현하는 Queue는 tail을 이용하여 데이터를 집어넣고(enqueue) head를 통해 데이터를 제거한다.(dequeue)

class Node:
    def __init__(self, data=None):
        self.data = data
        self.next = None
        
        
class Queue:
    def __init__(self):
        self.head = None
        self.tail = None
        self.size = 0

The enqueue operation

def enqueue(self, data):
    node = Node(data)
    
    if self.size == 0: # 큐가 비어있는 경우
        self.head = node
        self.tail = node
    else:
        self.tail.next = node
        self.tail = node
    self.size += 1

node 변수가 data를 가진 노드 instance를 가리킨다.
큐가 비어있는 경우
- head 노드와 tail노드 모두 생성한 노드를 가리킨다.
그렇지 않은 경우
- tail 노드의 next pointer가 노드를 새 노드를 가리킨다.
- tail 노드를 새 노드로 바꾼다.
size 1 증가

The dequeue operation

def dequeue(self):
    if self.size == 0:
        return None
    self.size -= 1
    
    data = self.head.data
    self.head = self.head.next
    
    return data

큐가 빈 경우 당연하게 None 리턴
그렇지 않은 경우
- size 1 감소
- data 변수에 head 노드의 data 대입
- head 노드의 next 노드를 head 노드로 변경
data 반환

Python Deque

from collections import deque

deq = deque([1, 2, 3])

deq.append(4)
deq.appendleft(5)
print(deq)

print(deq.pop())
print(deq.popleft())

deque([5, 1, 2, 3, 4])
4
5

list의 경우 삽입과 삭제의 경우 리스트의 값들을 한 칸씩 밀어야 되기 때문에 O(n)의 시간 복잡도를 갖고

deque의 경우 linked list로 구현이 되어 있기 때문에 노드들 간의 연결만 바꾸어 주면 되므로 O(1)의 시간 복잡도를 갖는다.

Queue implementation using Python deque

from collections import deque

data = "ea*sy **q*ue***st*i*on****"

queue = deque()
for ch in data:
    if ch == '*' and len(queue) > 0:
        print(queue.popleft(), end='')
        
    else:
        queue.append(ch)

easy question

백준 문제

백준 2164번 카드 2

from collections import deque

n = int(input())

a = [i for i in range(1, n + 1)]
q = deque(a)

while len(q) != 1:

    q.popleft()
    num = q.popleft()

    q.append(num)

print(a[0])

Queue implementation in C

Array implementation

queue안의 element들은 head, head+1, ….. tail - 1 과같은 주소에 위치하고 있고 그러한 구조에서 우리는 location 1이 location n을 바로 뒤따라 가고 있는 circular order 라는 것을 이해하면 된다.

head=tail 일 때, queue는 비어있다. 처음에 우리는 head = tail = 1로 설정한다. 만약 빈 queue로부터 element를 dequeue하려고 한다면, queue underflows가 발생한다.

head = tail + 1일 때, queue는 가득 차 있고 만약 element를 enqueue하려고 한다면 queue는 overflows가 발생한다.

우리는 array1의 size를 client가 queue에서 보기 원하는 element의 최대값보다 더 크도록 만든다.

#include <stdio.h>
#include <stdlib.h>

#define N 10
int queue[N + 1];
int head, tail;

int is_empty()
{
    return (head == tail);
}

int is_full()
{
    //queue에서 한 공간만 남았을 때를 꽉찼다고 하는데 이는 배열이 실제로 꽉차게 되면 head와 tail이 같아져 빈 queue와 구분할 방법이 없기 때문이다.
    //modulo 대신에 tail == N인 경우에 1로 되도록 하는 ternary operator를 사용하였다.
    //head == tail + 1
    return (head == ((tail == N) ? 1: (tail + 1)));

}

int q_size()
{
    int count = 0;
    int temp = head;
    
    while (temp != tail) {
        count++;
        temp = (temp == N) ? 1 : (temp + 1); //circular 구조를 고려
    }
    return count;
}

void enqueue(int item)
{
    if (is_full()) {
        printf("queue overflow\n");
        exit(1);
    }
    
    queue[tail] = item;
    tail = (tail == N) ? 1 : (tail + 1); //circular 고려한 tail += 1
}

int dequeue()
{
    int item;
    
    if (is_empty()) {
        printf("queue underflow\n");
        exit(1);
    }
    
    item = queue[head];
    head = (head == N) ? 1 : (head + 1); //head 노드를 이제 그 다음 노드로 바꿔야 한다.
    return item;
}

백준 문제(요세푸스 문제)

백준 1158번 요세푸스 문제

입력: 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다.

#include <stdio.h>
#include <stdlib.h>

#define N 10
int queue[N + 1];
int head, tail;

int is_empty()
{
    return (head == tail);
}

int is_full()
{
    //queue에서 한 공간만 남았을 때를 꽉찼다고 하는데 이는 배열이 실제로 꽉차게 되면 head와 tail이 같아져 빈 queue와 구분할 방법이 없기 때문이다.
    //modulo 대신에 tail == N인 경우에 1로 되도록 하는 ternary operator를 사용하였다.
    //head == tail + 1
    return (head == ((tail == N) ? 1: (tail + 1)));

}

int q_size()
{
    int count = 0;
    int temp = head;
    
    while (temp != tail) {
        count++;
        temp = (temp == N) ? 1 : (temp + 1); //circular 구조를 고려
    }
    return count;
}

void enqueue(int item)
{
    if (is_full()) {
        printf("queue overflow\n");
        exit(0);
    }
    
    queue[tail] = item;
    tail = (tail == N) ? 1 : (tail + 1); //circular 고려한 tail += 1
}

int dequeue()
{
    int item;
    
    if (is_empty()) {
        printf("queue underflow\n");
        exit(0);
    }
    
    item = queue[head];
    head = (head == N) ? 1 : (head + 1); //head 노드를 이제 그 다음 노드로 바꿔야 한다.
    return item;
}

int main()
{
    int M, K, item, i, j, index;
    
    scanf("%d %d", &M, &K);
    head = tail = 1;
    for (i = 1; i<=M; i++)
        enqueue(i);
    
    index = 0;
    printf("<");
    while (q_size() > 1)
    {	
        index += K - 1;
        if (q_size() <= index)
            index %= q_size();
        
        if (q_size() > 1)
            printf("%d, ",dequeue());
        else
            printf("%d",dequeue());
    }
    printf(">");
    return 0;
}

n, k = map(int, input().split())

jo = []
for i in range(1, n+1):
    jo.append(i)
    
print('<', end='')

index = 0

while len(jo) > 0:
    index += k - 1
    if len(jo) <= index:
        index %= len(jo)

    if len(jo) > 1:
        print(jo.pop(index), end=', ')
    else:
        print(jo.pop(index), end='')

print('>', end='') 

Twitter Facebook LinkedIn

Kang Chang Ryong

[자료구조와 알고리즘] Stack and Queues

Stacks and Queues

Stack ADT

Basic operations

Stack implementation using Linked list

Push operation

Pop operation

Peek operation

Bracket-matching application

Stack implementation using Python list

Stack Implementation in C

Array implementation

Linked-list implementation

push

pop

Queue ADT

Queues

Basic operation

Queue implementation using Linked list

The enqueue operation

The dequeue operation

Python Deque

Queue implementation using Python deque

백준 문제

Queue implementation in C

Array implementation

백준 문제(요세푸스 문제)

공유하기

댓글남기기

참고

[OS] Virtual Memory

[HCI] 10. Universal Design-Multi-Sensory Systems

[HCI] 9. Dialogue Notations and Design 2

[HCI] 9. Dialogue Notations and Design 1