Stack

스택

LIFO(Last In First Out : 후입선출구조 :나중에 들어간 것이 먼저 나옴)

서브루틴에서 사용할 반환 주소, 매개 변수, 지역변수 등을 추적할 때 사용

*서브루틴 : 메모리 점유율이 높은 매크로 대신에 사용(함수라고 보면 될 듯).

   

배열이 추가 될 때마다 필요에 따라 크기가 달라지는 동적 배열(Vector)이나 연결리스트를 사용해 스택을 구현하면 됨.

동적배열(Vector)의 장점

1. 배열 원소에 대한 임의의 접근이 가능하다(index로 접근 가능)
2. 배열 원소에 대한 임의의 접근 속도가 빠르다.

동적배열(Vector)의 단점

1. 배열의 끝(마지막에 넣은 데이터)에서만 연산이 이루어지기 때문에 동적배열의 의미가 별로 없을수도…
2. 동적 배열이 커짐에 따라 크기를 조절해야 하고, 그 과정에서 기존 배열의 모든 원소들을 새 배열로 옮겨야 함으로 시간이 오래 걸릴 수도 있다. (Vector의 용량보다 클 경우)

   

연결리스트를 사용하면 각 원소마다 메모리를 동적으로 할당하며 크기가 작은 연결리스트를 다룰때는 그에 따른 오버헤드가 꽤나 부담스러울수도 있다.

또한 동적배열을 사용하는것보다 속도가 떨어질수도 있다.

   

일반적으로 동적배열을 기반으로 한 스택이 연결리스트를 기반으로 하는 스택에 비해 대체로 빠른편이다.

   

면접용 구현에는 연결리스트가 편할수도…

   

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63

#include <iostream> using namespace std;       struct Node {     int data;     Node* before; };       int main() {     Node* head = NULL;     Node* beforeHead = NULL;           Node* newNode = NULL;           for (int i = 0; i < 10; i++)     {         newNode = new Node();         newNode->data = i;                     if (beforeHead == NULL)             beforeHead = newNode;               else         {             beforeHead = head;             newNode->before = beforeHead;         }               head = newNode;     }           Node* cur = head;           while (cur->before != NULL)     {         cout << cur->data << endl;         head = head->before;         cur = head;     }           cout << cur->data << endl;                 Node* deleteBefore;     Node* deleteNode = head;           while (deleteNode->before != NULL)     {         deleteBefore = deleteNode;               delete(deleteNode);     }           delete(deleteNode);           return 0;          }             Colored by Color Scripter

cs

   

단방향 연결리스트로 만든 스택

호호호호호 싱남 연결리스트가 좀 손에 익은 느낌이랄까