자료구조 제 13-2 강 ( 스택의 구현 )

배열을 이용한 구현

#include "statck.h"
#define MAX_CAPACITY 100

char stack[MAX_CAPACITY];	// 스택에 저장되는 데이터의 타입을 문자(char)라고 가정
int top = -1;				// index of the top element

void push(char ch) {
	if (is_full())			// 스택이 가득차면 더이상 push할 수 없다.
		return;
	top++;
	stack[top] = ch;
}

char pop() {
	char tmp = stack[top];
	top--;
	return tmp;
}

char peek() {				// peek을 호출하기 전에 먼저 empty인지 검사해야 한다.
	return stack[top];
}

int is_empty() {
	return top == -1;
}

int is_full() {
	return top == MAX_CAPACITY - 1;
}

 

연결리스트로 구현

 

• 연결리스트의 맨 앞이 노드를 삽입/삭제하기에 편하다.
• 따라서 첫번째 노드를 stack의 top으로 한다.

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

struct node {
	char* data;			// 문자열들을 저장하는 스택이라고 가정
	struct node* next;
};
typedef struct node Node;
Node* top = NULL;

void push(char* item) {
	Node* p = (Node*)malloc(sizeof(Node));	// 새로운 노드를 만듦
	p->data = item;							// 새로운 노드의 data필드에 item 저장
	p->next = top;							// p의 다음 노드는 현재의 top이 됨
	top = p;								// top은 새로 만든 p가 됨
}

char* pop() {
	if (is_empty())
		return NULL;
	char* result = top->data;
	top = top->next;
	return result;
}

char* peek() {
	if (is_empty())
		return NULL;
	return top->data;
}

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

 

 

• 만약 스택이 동시에 2개 이상 필요하다면?
• 서로 다른 타입의 데이터를 저장할 스택이 필요하다면?

-> 다음 강의에서...