Stack
•
Logical (or ADT) level: A stack is anordered group of homogeneous items(elements), in which the removal and addition of stack items can take place only at the top of the stack.
•
A stack is a LIFO “last in, first out” structure.
top의 최초값은 -1이고 push하기전에 +1해서 0부터 item을 삽입한다.
pop하기 전에는 top의 값에서 -1한다.
pop을 한다고 해서 item을 없애는 것이 아니라 top의 값을 변경해서 관리하고 있는 값이 아니라고 표시하는것.
void StackType::Push(ItemType newItem) {
if (IsFull())
throw FullStack() : top++;
items[top] = newItem;
}
void StackType::Pop() {
if (IsEmpty())
throw EmptyStack();
top--;
}
ItemType StackType::Top() {
if (IsEmpty())
throw EmptyStack();
return items[top];
}
C++
복사
Acutual Parameter vs Formal Parameter
acutal parameter는 실제로 함수를 호출할 때 전달하는 값이고
함수에서 형식상 있고 아직 값을 알수 없는 인자가 formal parameter이다.
template의 actual parameter는 data type이다. 컴파일러가 data type을 받아서 컴파일을 수행한다.
함수의 parameter도 local variable이다. 초기화를 하는지 안하는지의 차이밖에 없다.
& = address of operator
포인터도 주소값을 저장할 뿐인 local variable이다. 포인터의 type이 존재하는 이유는 그 주소에 존재하는 데이터의 타입을 알려주기 위한 것이다.
dereferencing operator = *ptr 그 주소에 저장된 값을 가져온다.
**두개 붙으면 dereferencing을 두번 수행한다.
Memory Allocation
런타임에 함수가 실행되면 스택에 메모리 영역 할당이 일어난다.
automatic data는 함수 내에서 사용하다가 함수 return하면 자동으로 destroy되는 데이터. 지역변수가 해당한다. automatic data의 주소는 스택포인터로부터 몇칸 떨어져있는지로 지정되며 런타임에 덧셈을 통해서 실제 주소를 계산하기 때문에 변수 엑세스 속도가 약간 더 느리다.
static은 프로그램 시작하면 할당되고 종료할때까지 가지고 있기 때문에 메모리 낭비가 심할 수 있다.
dynamic variable은 변수명이 없고 포인터로만 접근할 수 있는 anonymous variable이며 해제되지 않으면 프로그램 끝까지 살아있다.
static allocation은 메모리 공간 할당이 컴파일 타임에 수행되고 dynamic allocation은 new operator를 사용해서 런타임에 메모리 공간 할당이 수행된다.
new와 delete로 할당과 해제를 프로그래머가 직접 수행해줘야한다. 해제해주지 않으면 프로그램이 종료될 때까지 살아있다. 프로그램이 종료되면 모든 데이터나 파일 접근 권한을 운영체제에게 반환하기 때문에 사라진다.
dynamic data는 메모리 레이아웃의 heap에 할당된다. 동적 메모리는 메모리의 크기를 미리 정할 수 없을 때나 스택보다 더 큰 저장공간이 필요할 때 사용한다.
Queue
•
Logical (or ADT) level: A queue is an ordered group of homogeneous items (elements), in which new elements are added at one end (the rear), and elements are removed from the other end (the front).
•
A queue is a FIFO “first in, first out” structure.
Queue에 데이터를 삽입하는 메소드가 enqueue이고 데이터를 삭제하는 메소드가 dequeue이다
dequeue할때는 front포인터를 뒤로 한칸 보내고 enqueue할때는 rear포인터를 뒤로 한칸 보낸다.
Implementation Issues
circular queue로 구현할 때 queue가 full인지 empty인지 구분이 안가는 문제.
front와 rear포인터가 있고 각각 시작과 끝 주소를 가지고 있음.
enqueue dequeue반복하다 보면 front rear 둘다 뒤로만 오기 때문에 buffer공간을 다 쓴다.
따라서 공간을 넘어가면 맨 앞의 공간부터 다시 사용한다. 사실상 원형으로 순환하는 구조와 동일한 circular queue가 된다.
rear+1 ==front인 경우 full queue가 되는데, 마찬가지로 queue가 empty일때도 rear+1 == front인 문제가 발생한다.
front가 첫번째 element의 직전 위치를 가리키도록 하고 그 위치는 사용하지 않는 reserved공간으로 생각한다.
그럼 rear == front일때 empty queue이고 rear+1 == front일때는 full queue로 구분할 수 있다.
문제는 front가 포인팅하고 있는 공간이 reserved되므로 1칸을 낭비하게 된다는 것이다.
초기상태는 front와 rear 둘 다 -1이다.
처음에 queue를 생성할때는 maxQue를 받아서 동적으로 생성한다.
ADT Queue Operation
#include "ItemType.h" // for ItemType
template <class ItemType> class QueType {
public:
QueType();
QueType(int max); // PARAMETERIZED CONSTRUCTOR
~QueType(); // DESTRUCTOR
...bool IsFull() const;
void Enqueue(ItemType item);
void Dequeue(ItemType &item);
private:
int front;
int rear;
int maxQue;
ItemType *items; // DYNAMIC ARRAY IMPLEMENTATION
};
template <class ItemType>
QueType<ItemType>::QueType(int max) // PARAMETERIZED
{
maxQue = max + 1;
front = maxQue - 1;
rear = maxQue - 1;
items = new ItemType[maxQue]; // dynamically allocates
}
template <class ItemType> bool QueType<ItemType>::IsEmpty() {
return (rear == front)
}
template <class ItemType> QueType<ItemType>::~QueType() {
delete[] items; // deallocates array
}
template <class ItemType> bool QueType<ItemType>::IsFull() { // WRAP AROUND
return ((rear + 1) % maxQue == front)
}
template <class ItemType> void QueType<ItemType>::Enqueue(ItemType newItem) {
rear = (rear + 1) % maxQue;
items[rear] = newItem;
}
template <class ItemType> void QueType<ItemType>::Dequeue(ItemType &item) {
front = (front + 1) % maxQue;
item = items[front];
}
C++
복사
예시) Recognizing Palindromes
#include "stack.h"
#include <ctype.h>
#include <iostream.h>
#include "queue.h“
int main() {
StackType<char> s;
QueType<char> q;
char ch;
char sItem, qItem;
int mismatches = 0;
cout << "Enter string: " << endl;
while (cin.peek() != '\\n') {
cin >> ch;
if (isalpha(ch)) {
if (!s.IsFull())
s.Push(toupper(ch));
if (!q.IsFull())
q.Enqueue(toupper(ch));
}
}
while ((!q.IsEmpty()) && (!s.IsEmpty())) {
s.Pop(sItem);
q.Dequeue(qItem);
if (sItem != qItem)
++mismatches;
}
if (mismatches == 0)
cout << "That is a palindrome" << endl;
else
cout << That is not a palindrome " << endl;
return 0;
}
C++
복사
